棧

基本概念

棧是一種特殊的資料儲存結構，採用先進後出的規則，先入棧的元素被後入棧的元素「擠壓」在下面，出棧的時候只能等「壓在它身上」的元素都出去以後，它才能出去。就像把東西放進一個豎桶：

如圖，1是最先進去的，所以只有別的元素都出去了，它才出得去

STL中的棧

C++的庫裡其實給我們寫好了棧這一資料結構，直接呼叫就可以

#include <iostream>
#include <stack> //STL中棧的標頭檔案
using namespace std;
stack<int> s; //宣告一個int型的棧
int main()
{
    int n,a[100];
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        s.push(a[i]); //a[i]入棧
    }
    while (!s.empty()){ //判斷棧是不是空的，如果棧空，empty函數返回1
        cout<<s.top()<<" "; //top函數——返回棧頂元素，但不出棧
        s.pop(); //pop函數——棧頂元素出棧
    }
    return 0;
}

輸入：

5
1 2 3 4 5

輸出：

5 4 3 2 1

STL雖好，可不要貪杯哦
老師會查程式碼，所以就算你用STL過了，估計也得涼涼
畢竟是初學，為了更好地熟悉棧的基本操作，我們還是需要手寫一下的！

順序棧

就是用順序表實現棧這一資料結構

基本結構

#include <iostream>
#define maxSize 1000 //用來規定棧的大小
using namespace std;

struct Stack{
    int data[maxSize]; //順序表
    int top; //記錄目前的棧頂元素下標
};

初始化

top用來記錄目前棧頂元素的下標，所以它的取值範圍應該是0~maxSize-1。

初始化時，將top初始化為-1，這樣以後判斷棧是不是空的，就可以用if(s.top==-1)來判斷。

void initStack(Stack &s){
    s.top=-1;
}

入棧

將一個元素入棧，需要有兩個步驟：

• 將元素存入順序表data
• 改變top

void push(Stack &s,int value){
    s.top++; //先操作top，便於利用下標修改順序表
    s.data[s.top]=value;
}

出棧

出棧時很簡單，只要top--就可以了，因為順序表完全依賴top進行存取，所以即使top--後，原來的資料還是存在順序表裡，並沒有受到影響，但一旦有新的元素入棧，在top的影響下新元素會自動覆蓋老元素

void pop(Stack &s){
    s.top--;
}

取棧頂元素

直接返回即可

int top(Stack s){
    return s.data[s.top];
}

基本遍歷

while (!empty(head)){
        cout<<top(head)<<endl;
        pop(head);
}

判斷棧空

對於判斷棧空的函數，一般的設計規則是棧空則返回1（真），棧非空則返回0（假）。所以只需要這樣寫：

bool empty(Stack s){ 
    return s.top==-1; //非空：empty=0，類比Matlab裡面畫衝激函數的思想
}

ps. bool是一種變數型別，就像int一樣，但不同的是int型別的變數取值範圍很大，可以是任何一個整數（不超儲存範圍的前提下），但bool型的變數只有兩種可能的取值——1或0，即true或false

---

鏈棧

鏈棧就是用連結串列實現棧的儲存結構，還是連結串列那一套操作，甚至它比連結串列簡單——它白白加了一個先進後出的限制，搞得你不必考慮尾插法/頭插法建表，不必考慮不刪除情況下的遍歷，只要會一些基本連結串列操作即可

ps. 我寫完才發現，書上給的鏈棧沒有頭結點，它第一個結點就開始儲存資料了，而我套用的是連結串列的模版，所以我給的程式碼是有頭結點的，大家如果有把兩個結合著看的，注意一下這一點！

pps. 鏈棧跟順序棧的區別其實就是換了個載體，所以順序棧的基本思路講解完全可以搬到下面的鏈棧裡來，我就不多寫一遍啦！

基本結構

struct LinkStack{
    int data;
    LinkStack *next;
};

初始化

void initLinkStack(LinkStack *&head){
    head=new LinkStack ();
}

銷燬

void destoryLinkStack(LinkStack *&head){
    LinkStack *pre=head,*p=head->next;
    while (p!=NULL){
        delete pre;
        pre=p;
        p=p->next;
    }
    delete pre;
}

入棧

void push(LinkStack *&head,int value){
    LinkStack *p=new LinkStack();
    p->data=value;
    p->next=head->next;
    head->next=p;
}

出棧

void pop(LinkStack *&head){
    LinkStack *p=new LinkStack();
    p=head->next;
    head->next=p->next;
    delete p;
}

取棧頂元素

int top(LinkStack *head){
    return head->next->data;
}

判斷棧空

bool empty(LinkStack *head){
    return head->next==NULL;
}