棧：順序棧和鍊式棧

    前面已經介紹了“連結清單”，包括順序連結清單和鍊式連結清單。連結清單和棧都屬于線性表，隻是棧是一種特殊的線性表，其“隻能夠從一端（棧頂）進出”，必須遵循“先進後出”的原則。下面，我們簡要學習一下順序棧和鍊式棧。

（1）順序棧

        與順序存儲的連結清單一樣，順序棧也是采用“數組”來存儲。其資料結構如下：

[cpp]  view plain copy

1. #define MAXSIZE 20  
2. typedef int Elemtype;  
3. typedef struct  
4. {  
5.      Elemtype data[MAXSIZE];  
6.      int top;  
7. }sqStack;  

        這裡我們看出，棧和連結清單的資料結構幾乎一模一樣，隻是裡面的成員含義不同而已。在順序連結清單裡面，定義的是一個長度length，表示所能夠存儲的最大資料的個數，這個值是不能變化的；而順序棧中定義的是棧頂元素的下标，這個值可以變化。

       對于棧的操作來說，最重要的是“入棧”和“出棧”。這兩個操作都必須遵循“FILO”的原則，其具體實作如下：

[cpp]  view plain copy

1. //入棧  
2. bool Push(sqStack *S, Elemtype e)  
3. {  
4.       if(S->top >= MAXSIZE - 1)  
5.                 return false;  
6.       S->top++;    //要細心，不能單獨用top，而是引用結構體中的元素  
7.       S->data[s->top] = e;  
8.       return true;  
9. }  
10. //出棧  
11. bool Pop(sqStack *S, Elemtype *e)  
12. {  
13.       if(S->top == 0)  
14.              return false;  
15.        *e = S->data[S->top];  
16.        S->top--;  
17.        return true;  
18. }  

        從上面的知識中，可以知道，順序棧的操作很友善，但其最大的不足在于，必須事先确定資料存儲的最大空間。這裡，我們擴充一下知識，下面介紹一下如何做到兩個順序棧共享資料空間。這個方法的基本思想為：數組空間有兩個端點，兩個棧有兩個棧底；讓一個棧的棧底位于數組的起始端（下标為0處），讓另一個棧的棧底位于數組的末端（下标為N-1處）；如果要向棧裡面添加元素，那麼使棧頂向數組中間移動即可。

資料結構如下：

[cpp]  view plain copy

1. typedef struct   
2. {  
3.       Elemtype data[MAXSIZE];  
4.       int top1;  
5.       int top2;  
6. }sqDoubleStack;  

入棧操作：

[cpp]  view plain copy

1. bool Push(sqDoubleStack *S, Elemtype e, int stackNumber)  
2. {  
3.       if(S->top1+1 == S->top2)//特别注意，如果棧滿了，top1和top2不是相等的，而是兩者前後相鄰，是以要加1  
4.            return false;  
5.       if(stackNumber == 1)  
6.       {  
7.               S->top1++;  
8.               S->data[S->top1] = e;  
9.               return true;  
10.       }    
11.       if(stackNumber == 2)  
12.       {  
13.               S->top2++;  
14.               S->data[S->top2] = e;  
15.               return true;  
16.       }      
17. }  

（2）鍊式棧

        鍊式存儲的棧就不會存在“棧滿”的現象。是以，在進行入棧、出棧的時候，就不用再判斷是否滿棧了。在對鍊式棧進行操作時，始終要把握一點：首先看到的是整個棧，而不每一個結點；對于整個棧，隻有兩個名額——棧頂指針（top）和棧元素個數（count）；這樣，我們就能夠通過棧頂指針（top）來取到棧頂的一個結點，進而擷取其中的資料data，并可以建立指針，移動指針位置，周遊棧中的各個元素。也就是說，我們必須“從棧（top、count），再到結點（data、next）”。

其資料解結構可以定義為：

[cpp]  view plain copy

1. typedef struct StackNode  
2. {  
3.      Elemtype data;  
4.      struct StackNode * next;  
5. }StackNode, *LinkStackPtr;  
6. typedef struct LinkStack  
7. {  
8.      LinkStackPtr top;//這裡top是一個stack結點類型的指針，指向Stack結點（棧頂）  
9.      int count;  
10. }LinkStack;  

入棧操作：

[cpp]  view plain copy

1. bool Push(LinkStack *S, Elemtype e)  
2. {  
3.       LinkStackPtr tmp = (LinkStackPtr)malloc(sizeof(StackNode));  
4.       tmp->data = e;  
5.       tmp->next = S->top;  
6.       S->top = tmp;  
7.       S->count++;  
8.        return true;  
9. }  

出棧操作：

[cpp]  view plain copy

1. bool Pop(LinkStack *S, Elemtype *e)  
2. {  
3.       LinkStack p;  
4.       *e = S->top->data;  
5.       p = S->top;  
6.       S->top = S->top->next;  
7.       free(p);  
8.       S->count--:  
9.       return true;  
10. }