今天來講講棧
棧是什么？
老樣子，先來看一道題：
【棧】棧的基本操作
描述
棧的定義：棧是一種特殊的表這種表只在表頭進行插入和刪除操作。因此，表頭對于棧來說具有特殊的意義，稱為棧頂。相應地，表尾稱為棧底。不含任何元素的棧稱為空棧。
棧的邏輯結構：假設一個棧?SS?中從頂到底的元素為?a_n,a_{n-1},\ldots,a_1an?,an?1?,…,a1?，則稱?a_1a1??為棧底元素，a_nan??為棧頂元 素。棧中的元素按?a_1,a_2,..,a_{n-1},a_na1?,a2?,..,an?1?,an??的次序進棧。在任何時候，出棧的元素都是棧頂元素。換句話說，棧的修改是按后進先出的原則進行的。因此，棧又稱為后進先出 (Last In First Out) 表，簡稱為 LIFO 表。所以，只要問題滿足 LIFO 原則，就可以使用棧。
舉個生活中的例子，比如洗碗，先洗的碗在底層，后面洗的碗會疊在先洗的碗的上面。這樣在使用的時候，最后洗的碗就會先拿。
在程序實現上，棧也是用數組來存放的，需要一個數組下標變量來控制數據在數組的存入和讀取等操作。
由于 C++ 的 STL 本身提供了棧這種數據結構，你只要學會使用 STL 的棧操作就行了。
后面學的遞歸（回溯）算法，遞歸會調用系統棧是來實現（這個是遞歸內部實現，我們不用去操作），只是理解棧這個結構會幫助我們更好地理解遞歸這個算法。當然，棧本身在一些題目上也會用到。
首先看一下 C++ 棧的方法的基本用法：
push()：向棧內壓入一個成員；
pop()：從棧頂彈出一個成員；
empty()：如果棧為空返回true，否則返回false；
top()：返回棧頂，但不刪除成員；
size()：返回棧內元素的大小；普通棧的操作：
#include<iostream> #include<stack> //使用棧需要的頭文件 using namespace std; int x; int main(){stack <int>stk; //定義一個整數類型的棧變量 //入棧for(int i=0;i<50;i++){cin>>x;stk.push(x); // 數據入棧 }cout<<"棧的大小:"<<stk.size()<<endl;while(!stk.empty()){cout<<stk.top()<<endl; //取出棧頂數據 stk.pop(); //刪除棧頂數據，就是出棧 }cout<<"棧的大小:"<<stk.size()<<endl;return 0; }結構體棧的使用：
#include<iostream> #include<stack> //使用棧需要的頭文件 using namespace std; struct people{int sg,tz;char xb; }; people x; int n; int main(){stack <people> stk; //定義一個結構體類型的棧變量 //入棧cin>>n;for(int i=0;i<n;i++){cin>>x.sg>>x.tz>>x.xb; stk.push(x); // 結構體數據入棧 }cout<<"棧的大小:"<<stk.size()<<endl;while(!stk.empty()){x= stk.top(); //取出棧頂數據cout<<x.sg<<" "<<x.tz<<" "<<x.xb<<endl; //取出棧頂數據 stk.pop(); //刪除棧頂數據，就是出棧 }cout<<"棧的大小:"<<stk.size()<<endl;return 0; }
現給定一組棧的操作（入棧與出棧），要求按順序輸出出棧的數，和最終留在棧里的數。
輸入
一行若干個正整數，以0結尾。
操作有如下幾種：
- 1?x：表示將?x?入棧；
- 2：表示將棧頂彈出。
輸出
第一行按順序輸出出棧的數；無則輸出空行；
如果出現棧滿并且還有數據進棧則單行輸出：the stack is full!
如果出現棧空并且還有數據出棧則單行輸出：the stack is empty!
最后一行如果棧里還有數據則輸出棧里的數（注意：出現棧滿情況時也要輸出棧里剩余的數）。
輸入樣例 1?
1 3 1 2 2 1 1 2 0
輸出樣例 1
2 1 3
輸入樣例 2?
1 3 2 2 1 3 1 4 1 5 1 6 0
輸出樣例 2
3the stack is empty!
提示
對于 100%?的數據，棧的最大容量為?300，每次需要入棧的正整數小于等于?10^9。
來源
lzy
首先我來講一下展示怎么樣的東西
這里有一個羽毛球筒
|? |
|? |
|? |
|? |
—
現在我把一號球放進去：
|? |
|? |
|? |
|1|
—
現在我把二號球放進去：
|? |
|? |
|2|
|1|
—
現在我們要取出一個球，我們只能先取出2，再取出1（先進入的數字反而最后出來，也就是先進后出）（考試經常考哦）
|? |? ? ? ?——>2（取出）
|? |
|? |
|1|
—
|? |? ? ? ?——>2（取出）
|? |? ? ? ?——>1（取出）
|? |
|? |
—
這就是棧，像一個羽毛球筒
棧怎么寫？
定義是這樣的：
stack<int> q;
//其中，<>里的數據類型代表q的類型
//比如現在q為int型
//如果把int改為longlong，q就是longlong型其他的操作室這樣的：
q.size()//求q的大小（元素個數，比如棧里有1和2，元素個數就是2）
!q.empty()//判斷q是否為空（空就是沒有元素）如果空了就返回1（真），否則返回2（假）
q.top();//獲取棧頂的數字，比如剛剛的羽毛球筒，放了1和2，用這個就會返回2
q.pop();//彈出棧頂（把棧頂刪掉），將最后一個放入的2拿出，就可以用這個
q.push(x);//入棧，也就是把x跟球一樣放進棧里
//注意了！不管你怎么用，都要加個括號
//q.size()這種返回數字的東西，是可以當數字來用的
//比如if(q.size()==300) ,就是判斷q的元素個數是不是等于300
//a=q.top();就是a=棧頂的那個數字 所以我們就可以解出最開始的那道題了：
?
#include<bits/stdc++.h>
using namespace std;
int main(){stack<int> q;//定義 long long a,x;//定義（a讀的是前面的1或2） do{cin>>a;//讀入 if(a==1){//a==1說明要入棧 if(q.size()==300){//如果說棧已經滿了 cout<<endl<<"the stack is full!"<<endl;//輸出 while(!q.empty()){//循環，棧沒空就一直循環 cout<<q.top()<<" ";//輸出棧頂 q.pop();//彈出棧頂，為下一次的輸出做準備 } return 0;}//否則就可以正常入棧了 cin>>x;//讀入 q.push(x);//入棧 }else if(a==2){//如果要彈出 if(q.empty()){//如果棧空了，就彈不了了 cout<<endl<<"the stack is empty!";//輸出 return 0;}cout<<q.top()<<" ";//否則輸出棧頂 q.pop();//彈出棧頂 }}while(a!=0);//a==0就是要停止輸入了 cout<<endl;while(q.size()!=0){//循環，只要棧的元素個數！=0就一直循環 cout<<q.top()<<" ";//輸出 q.pop();//彈出 }return 0;
}你知道我寫了多久嗎？寫了20分鐘。這還不值得你給我點個贊嗎？
)
