目录
这篇文章是关于在 C++ 中使用数组实现堆栈的。
堆栈作为抽象数据类型
Stack 是一种有序的数据结构，用于以LIFO（后进先出）顺序存储数据类型。这
意味着最后进入的元素首先退出（已处理）。这就像一个同心圆塔，
一个接一个。当然，当我们开始将
它们一一移除时，将首先选择最后一个（例如：河内之塔）。堆栈是一种类似的数据结构（抽象
数据类型，简称 ADT），其中插入和删除都在同一端完成，即
顶部。堆栈只保存相似的数据类型。
插入过程命名为Push
删除过程命名为Pop
堆栈操作
Type_t = 任何数据类型
基本操作：
Push(Type_t data)：将数据类型 Type_t 的数据插入堆栈
Type_t Pop()：从堆栈中移除最顶部的元素并返回
其他操作：
type_t top()：返回最顶层元素
bool isEmpty()：如果堆栈为空，则返回 true，否则返回 false
bool isFull()：如果堆栈已满，则返回 true，否则返回 false
int size()：返回堆栈的大小
例子：
让插入的元素是
1, 2, 3, 4
在 C++ 中使用数组实现堆栈
先决条件：
1. top 变量
2. 一个数组，即stack_array
所以要实现一个带有数组的堆栈，我们需要做的是实现这些操作。
下面是详细代码。
#include <bits/stdc++.h>
using namespace std;
#define MAX_SIZE 1024
//declare our pre-reuisites
int stack_array[MAX_SIZE]; //globally declared array to act like stack
int top=-1; //top variavle initialized to -1 for empty stack
//implement stack operations
//1. implement isEmpty()
bool isEmpty(){
if(top==-1) //empty stack
return true;
else
return false;
}
//2. Implement isFull()
bool isFull(){
if(top==MAX_SIZE-1)
return true;
else
return false;
}
//3. Implement push operation
void push(int data){
if(isFull()){
cout<<"Stack is full\n";
return;
}
else{
stack_array[++top]=data;//first top is increased by 1 and then stack[top]=data
cout<<data<<" is pushed\n";
}
}
//4. Implement Pop operation
int pop(){
if(isEmpty()){
cout<<"Stack is empty\n";
return INT_MIN;
}
else{
return stack_array[top--]; //top is decreased after popping
}
}
//5. implement size function
int size(){
return top+1;
}
//6. implement top
int top_stack(){
if(isEmpty()){
cout<<"stack is empty\n";
return INT_MIN;
}
else
return stack_array[top];
}
//main function
int main(){
//menu for operations
//press 1 for push (with data)
//press 2 for pop()
//press 3 for top()
//press 4 for size()
//press 0 to exit()
cout<<"press 1 for push\n";
cout<<"press 2 for pop()\n";
cout<<"press 3 for top()\n";
cout<<"press 4 for size()\n";
cout<<"press 0 for exit\n";
int choice;
cout<<"press your choice\n";
cin>>choice;
while(choice){
if(choice==1){
int data;
cout<<"Enter element\n";
cin>>data;
push(data);
}
else if(choice==2){
int item=pop();
if(item==INT_MIN){}
else
cout<<"Popped element: "<<item<<endl;
}
else if(choice==3){
int item=top_stack();
if(item==INT_MIN){}
else
cout<<"Top element: "<<item<<endl;
}
else if(choice==4){
cout<<"Size is: "<<size()<<endl;
}
else
cout<<"Invalid number, try again!\n";
cout<<"press your choice\n";
cin>>choice;
}
cout<<"Exiting...\n";
return 0;
}
输出：
press 1 for push press 2 for pop() press 3 for top() press 4 for size() press 0 for exit press your choice 1 Enter element 2 2 is pushed press your choice 1 Enter element 5 5 is pushed press your choice 3 Top element: 5 press your choice 4 Size is: 2 press your choice 1 Enter element 3 3 is pushed press your choice 2 Popped element: 3 press your choice 2 Popped element: 5 press your choice 2 Popped element: 2 press your choice 2 Stack is empty press your choice 2 Stack is empty press your choice 0 Exiting…
这就是在 C++ 中使用数组实现 Stack 的全部内容。
