C++ 中的堆栈实现

目录

这篇文章是关于在 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 的全部内容。