栈(stack)是一种特殊的线性表。
举一个简单的例子,我们将3本书,三本书取名为123,并按照这个顺序依次放入收纳箱中
取书的时候,最后放进去的3最先取出,第一个放进去的1最后取出
也就是:后进栈的先出栈
因为我们没法从收纳箱的底部放入书(除非你非要把收纳箱底部砸个洞)
所以,其所有的插入和删除操作均是限定在线性表的一端进行的
允许插入和删除的一端称栈顶(Top),不允许插入和删除的一端称栈底(Bottom)
若给定一个栈S=(a, b,c……z),则称a为栈底元素,z为栈顶元素,元素b位于元素a之上
栈中元素按a,b,c……z 的次序依次进栈
并依次按照z,y,x……a 的次序依次出栈
也就是说,栈中元素的进出是按后进先出的原则进行,这是栈结构的重要特征
栈一般有两种的典型的存储表示,基于数组的存储表示和基于链表的存储表示
这里以基于数组的表示为例
#include<iostream> using namespace std; const int n = 10;//栈溢出的时候,用于扩展栈的大小 class Stack { private : int *data;//存放栈里所有元素的数组 int size;//栈里面最大可以容纳的元素个数 int top;//栈顶的指针,表示最后加入的元素的存储位置 bool overflow();//栈的溢出处理 public: Stack(int sz = 3);//构造函数 ~Stack();//析构函数 bool push(int x);//进栈 int pop();//出栈 bool isEmpty();//判断栈是否为空 bool isFull();//判断栈是否已满 int getTop();//获得当前栈顶的指针 }; int Stack :: getTop() { return top ; } Stack :: Stack(int sz) { size = sz; data = new int[size]; top = -1; } Stack :: ~Stack() { delete[] data; } bool Stack :: isEmpty() { return top == -1; } bool Stack :: isFull() { return top ==size - 1; } bool Stack :: overflow() { cout<< "大哥,我要扩充栈的空间了\n"<< endl; int *newData = new int [size + n]; for(int i = 0; i <= top; i++) { newData[i] = data[i]; } size += n; delete []data; data = newData; } bool Stack :: push(int x) { if(isFull()) { cout << "大哥,栈慢了"<< endl; overflow(); } data[++top] = x; cout << "将"<< x <<"存入栈,Top = " << top << endl; return true; } int Stack :: pop() { if(isEmpty()) { cout << "大哥,我都被你榨干了"<< endl; return false; } return data[top --];; } int main() { int sz; int num; cout<< "请输入栈的大小"<< endl; cin >> sz ; Stack s(sz); for(int i = 0; i <= sz; i++) {// <= 是为了测试时溢出 cout<< "请输入第" << i + 1<< "个数" << endl; cin >> num; s.push(num); } cout << "开始出栈啦"<< endl; int n = s.getTop() + 1; for(int i = 0; i < n ;i++) { cout << s.pop() ; } }
请登录之后再进行评论