棧作為一種受限的線性表，同樣可以劃分為順序結構存儲的棧（這里簡稱順序棧）和鏈式結構存儲的棧（這里簡稱鏈棧）。 ## 一.順序棧 ### 1.1定義 棧的順序存儲稱為順序棧，是利用一組地址連續的存儲單元存放從棧底到棧頂的元素，同時附設一個指針（top）指示當前棧頂的位置。如圖所示：  棧的順序存儲類型則可以描述為： ~~~ typedef struct{ ElemType data[MaxSize]; int top; }SqStack; ~~~ 這里對順序棧的判斷條件進行說明。 > - 棧空條件：top==-1 > - 棧滿條件：top==MaxSize-1 > - 棧長：top+1 ### 1.2基本操作 ### 1.2.1初始化操作 完成對棧頂指針的復位操作。 ~~~ void InitStack(SqStack* s) { s->top=-1; } ~~~ ### 1.2.2判空操作 如果棧為空，則返回0；如果棧不為空，則返回-1。 ~~~ int StackEmpty(SqStack* s) { if(s->top==-1){ return 0; }else{ return -1; } } ~~~ ### 1.2.3入棧操作 首先判斷棧是否已滿，如果棧已經滿了，則返回-1；如若沒有滿，則在棧頂中插入元素，并返回0。 ~~~ int Push(SqStack* s, ElemType x) { if(s->top==MaxSize-1){ return -1; } s->data[++s->top]=x; return 0; } ~~~ ### 1.2.4出棧操作 首先判斷棧是否為空，如果已經為空，則返回-1；如果不為 空，則取得棧頂元素，并返回0。 ~~~ int Pop(SqStack* s, ElemType* x) { if(s->top==-1){ return -1; } *x=s->data[s->top--]; return 0; } ~~~ ### 1.2.5讀棧頂元素 首先判斷棧是否為空，如果為空，則返回-1；如果不為空，則返回棧頂元素，并返回0。 ~~~ int GetTop(SqStack* s, ElemType *x) { if(s->top==-1){ return -1; } *x=s->data[s->top]; return 0; } ~~~ ## 二.共享棧 ### 2.1定義 利用棧底位置相對不變的特性，可以讓兩個順序棧共享一個一維數據空間，將兩個棧的棧底分別設置在共享空間的兩端，兩個棧頂向共享空間中間延伸。如圖所示：  則共享棧的數據結構可以描述為： ~~~ typedef struct{ ElemType data[MaxSize]; int top[2]; }SqStack; ~~~ 這里對共享棧的判斷條件進行說明。 > - 棧空條件：0號棧【top[0]==-1】；1號棧【top[1]==MaxSize】 > - 棧滿條件：top1-top0=1 ### 2.2基本操作 ### 2.2.1初始化操作 完成對棧頂指針的復位操作，按照上述規定，0#棧為空，則top[0]==-1；若1#棧為空，則top[1]==MaxSize; ~~~ void InitStack(SqStack *s) { s->top[0]=-1; s->top[1]=MaxSize; } ~~~ ### 2.2.2判空操作 同樣根據上述規定，0#棧為空，則top[0]==-1；若1#棧為空，則top[1]==MaxSize；那么若兩個棧均為空則返回0；如果棧不為空，則返回-1。 ~~~ int StackEmpty(SqStack* s) { if(s[0]->top==-1&&s[1]->top==MaxSize){ return 0; }else{ return -1; } } ~~~ ### 1.2.3入棧操作 先確定棧號是否合法，然后查看是對0#棧還是1#棧進行操作，入棧操作和順序棧的入棧操作并無太大不同。選定之后進行入棧操作。這里應該注意此共享棧是否已滿，如果已滿則不能進行入棧操作。如若入棧成功則返回0；入棧失敗則返回-1。 ~~~ int Push(SqStack*s, ElemType x, int n) { if(n<0||n>1){ printf("The stack number is false!\n"); return -1; } if(s->top[1]-s->top[0]==1){ printf("The stack is full!\n"); return -1; } switch(n){ case 0:s->data[++s->top[0]]=x;break; case 1:s->data[--s->top[1]]=x;break; } return 0; } ~~~ ### 2.2.4出棧操作 先確定棧號是否合法，然后查看是對0#棧還是1#棧進行操作，出棧操作和順序棧的出棧操作并無太大不同。選定之后進行出棧操作。如果出棧成功返回0；出棧失敗返回-1。 ~~~ int Pop(SqStack *s, ElemType* x,int n) { if(n<0||n>1){ printf("The stack number is false!\n"); return -1; } switch(n){ case 0: if(s->top[0]==-1){ printf("The stack[0] is empty!\n"); } *x=s->data[s->top[0]--]; break; case 1: if(s->top[1]==MaxSize){ printf("The stack[1] is empty!\n"); } *x=s->data[s->top[1]++]; break; } return 0; } ~~~ ## 三.鏈棧 ### 3.1定義 采用鏈式存儲的棧稱為鏈棧。 鏈棧的優點便是便于多個棧共享存儲空間和提高其效率，而且不存在棧滿上溢的情況。通常采用單鏈表實現，并規定所有的操作都是在單鏈表的表頭進行的，這里規定鏈棧沒有頭節點。如圖所示：  鏈棧的數據結構的描述如下： ~~~ typedef struct LinkNode{ ElemType data; struct LinkNode *next; }LinkStack; ~~~ 因為采用鏈式存儲時的棧與[第1章的單鏈表](http://blog.csdn.net/u013595419/article/details/50481785)操作類似，這里便不再詳細說明。但應當注意區分帶頭結點的單鏈表與不帶頭結點的單鏈表操作略有不同。 注：在棧的操作中，經常會求到對于n個不同的元素進棧，則出棧序列的個數為多少？ 對于這種題，我們可以引入[卡特蘭（Catalan）數](http://baike.baidu.com/link?url=9WJdSO-OKxLm_8wzl8D36hgpYKLRgKx053fSa_cteOBDaO_1YLwbVKV29CreU3Vo7Osopzf00xgGVEEgqLCuXa)進行解決。答案為：1n+1(2nn)