第4章 棧與隊列
棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。
隊列是只允許在一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作的線性表。
棧的定義
棧（stack）是限定僅在表尾進(jìn)行插入和刪除操作的線性表邪媳。
我們把允許插入和刪除的一端稱為棧頂（top），另一端稱為棧底（bottom）叽唱，不含任何數(shù)據(jù)元素的棧稱為空棧。棧又稱為后進(jìn)先出（Last In First Out）的線性表微宝，簡稱 LIFO 結(jié)構(gòu)棺亭。
棧的插入操作，叫做進(jìn)棧蟋软，也稱壓棧镶摘、入棧嗽桩。
棧的刪除操作，叫做出棧凄敢，也有的叫彈棧碌冶。
進(jìn)棧出棧的變化形式
元素數(shù)量多個，出棧次序會有很多種可能涝缝。
棧的抽象數(shù)據(jù)類型
ADT 棧
Data
同線性表扑庞。元素具有相同的類型，相鄰元素具有前驅(qū)和后繼關(guān)系拒逮。
Operation
InitStack(*S):初始化操作罐氨，建立一個空棧S。
DestroyStack(*S):若棧存在滩援，則銷毀它栅隐。
ClearStack(*S):將棧清空。
StackEmpty(S):若棧為空狠怨，返回 true 约啊，否則返回 false邑遏。
GetTop(S,*e):若棧存在且非空佣赖，用e返回S的棧頂元素。
Push(*S,e):若棧S存在记盒，插入新元素e到棧S中并成為棧頂元素憎蛤。
Pop(*S,e):刪除棧S中的棧頂元素，并用e返回其值纪吮。
StackLength(S):返回棧S的元素個數(shù)俩檬。
endADT
棧的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)
棧的順序存儲結(jié)構(gòu)
棧的結(jié)構(gòu)定義
typedef init SElemType;
typedef struct
{
SElemType data[MAXSIZE]
int top; /* 用于棧頂指針 */
}SqStack;
棧的順序存儲結(jié)構(gòu)——進(jìn)棧操作
進(jìn)棧操作 push，其代碼如下：
Status Push (SqStack *S, SElemType e)
{
if (S->top == MAXSIZE - 1) /* 棧滿 */
{
return ERROR;
}
S->top++; /* 棧頂指針增加一 */
S->data[S->top]=e; /* 將新插入元素賦值給棧頂空間 */
return OK;
}
棧的順序存儲結(jié)構(gòu)——出棧操作
出棧操作 pop碾盟，其代碼如下：
Status Pop (SqStack *S, SElemType *e)
{
if(S->top==-1)
return ERROR;
*e=S->data[S->top]; /* 將要刪除的棧頂元素賦值給e */
S->top--; /* 棧頂指針減一 */
return OK;
}
進(jìn)棧和出棧沒有涉及到任何循環(huán)語句棚辽，因此時間復(fù)雜度均是 O(1)。
兩棧共享空間
使用這樣的數(shù)據(jù)結(jié)構(gòu)冰肴，通常都是當(dāng)兩個棧的空間需求有相反關(guān)系時屈藐，也就是一個棧增長時另一個棧在縮短的情況。
棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實(shí)現(xiàn)
棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)
棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)熙尉，簡稱為鏈棧联逻。
鏈棧的結(jié)構(gòu)代碼如下：
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode, *LinkStackPtr;
typedef struct LinkStack
{
LinkStackPtr top;
int count;
}
棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)——進(jìn)棧操作
/* 插入元素 e 為新的棧頂元素 */
Status Push (LinkStack *S, SElemType e)
{
LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
s->data = e;
s->next = s->top; /* 把當(dāng)前的棧頂元素賦值給新結(jié)點(diǎn)的直接后繼 */
S->top = s; /* 將新的結(jié)點(diǎn)s賦值給棧頂指針 */
S->count++;
return OK;
}
棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)——出棧操作
假設(shè)變量 p 用來存儲要刪除的棧頂結(jié)點(diǎn)，將棧頂指針下移一位检痰，最后釋放 p 即可包归。
Status Pop (LinkStack *S, SElemType *e)
{
LinkStackPtr p;
if (StackEmpty(*S))
return ERROR;
*e = S->top->data;
p=S->top; /* 將棧頂結(jié)點(diǎn)賦值給p */
S->top=S->top->next; /* 使得棧頂指針下移一位，指向后一結(jié)點(diǎn) */
free(p); /* 釋放結(jié)點(diǎn) p */
S->count--;
return OK;
}
鏈棧的進(jìn)棧 push 和出棧 pop 操作沒有任何循環(huán)操作铅歼，時間復(fù)雜度均為O(1)公壤。
如果棧的使用過程中元素變化不可預(yù)料换可，有時很小，有時非常大厦幅，那么最好是用鏈棧锦担，反之，如果它的變化在可控范圍內(nèi)慨削，建議使用順序棧會更好一些洞渔。
棧的作用
棧的引入簡化了程序設(shè)計的問題，劃分了不同關(guān)注層次缚态，使得思考范圍縮小磁椒，更加聚焦于我們要解決的問題核心。
棧的應(yīng)用——遞歸
斐波那切數(shù)列實(shí)現(xiàn)
int Fbi (int i)
{
if (i < 2)
return i == 0 ? 0 : 1;
return Fbi(i-1) + Fbi(i-2);
}
int main()
{
int i;
for (int i = 0;i < 40; i++)
printf("%d ", Fbi(i));
return 0;
}
遞歸定義
在高級語言中玫芦，調(diào)用自己和其他函數(shù)并沒有本質(zhì)的不同浆熔。我們把一個直接調(diào)用自己或通過一系列的調(diào)用語句間接地調(diào)用自己的函數(shù)，稱做遞歸函數(shù)桥帆。
每個遞歸定義必須至少有一個條件医增，滿足遞歸不再進(jìn)行，即不再引用自身而是返回值退出老虫。
棧的應(yīng)用——四則運(yùn)算表達(dá)式求值
將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式（棧用來進(jìn)出運(yùn)算的符號）叶骨。
將后綴表達(dá)式進(jìn)行運(yùn)算得出結(jié)果（棧用來進(jìn)出運(yùn)算的數(shù)字）。
隊列的定義
隊列（queue）是只允許在一端進(jìn)行插入操作祈匙，而在另一端進(jìn)行刪除操作的線性表忽刽。
隊列是一種先進(jìn)先出（First In First Out）的線性表，簡稱FIFO夺欲。允許插入的一端稱為隊尾跪帝，允許刪除的一端稱為隊頭。
隊列的抽象數(shù)據(jù)類型
ADT 隊列（Queue）
Data
同線性表些阅。元素具有相同的類型伞剑，相鄰元素具有前綴和后繼關(guān)系。
Operation
InitQueue(*Q):初始化操作市埋，建立一個空隊列Q黎泣。
DestroyQueue(*Q):若隊列Q存在，則銷毀它腰素。
ClearQueue(*Q):將隊列Q清空聘裁。
QueueEmpty(*Q):若隊列Q為空，返回 true弓千，否則返回 false衡便。
GetHead(Q,*e):若隊列Q存在且非空，用e返回隊列Q的隊頭元素。
EnQueue(*Q,e):若隊列Q存在镣陕，插入新元素e到隊列Q中并成為隊尾元素谴餐。
DeQueue(*Q,*e):刪除隊列Q中隊頭元素，并用e返回其值呆抑。
QueueLength(Q):返回隊列Q的元素個數(shù)岂嗓。
endADT
循環(huán)隊列
循環(huán)隊列定義
我們把隊列的這種頭尾相接的順序存儲結(jié)構(gòu)稱為循環(huán)隊列。
隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實(shí)現(xiàn)
隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)鹊碍，其實(shí)就是線性表的單鏈表厌殉，只不過它只能尾進(jìn)頭出而已，我們把它簡稱為鏈隊列侈咕。
鏈隊列的結(jié)構(gòu)為：
typedef int QElemType;
typedef struct QNode /* 節(jié)點(diǎn)結(jié)構(gòu) */
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct /* 隊列的鏈表結(jié)構(gòu) */
{
QueuePtr front,rear; /* 隊頭公罕、隊尾指針 */
}LinkQueue;
隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)——入隊操作
Status EnQueue(LinkQueue *Q, QElemType e)
{
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
if(!s) /* 存儲分配失敗 */
exit(OVERFLOW);
s->data = e;
s->next = NULL;
Q->rear->next = s; /* 把擁有元素e新結(jié)點(diǎn)s賦值給原隊尾節(jié)點(diǎn)的后繼 */
Q->rear = s; /* 把當(dāng)前的s設(shè)置為隊尾結(jié)點(diǎn)，rear指向s */
return OK;
}
隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)——出隊操作
Status DeQueue(LinkQueue *Q, QElemType *e)
{
QueuePtr p;
if(Q->front==Q->rear)
return ERROR;
p=Q->front->next; /* 將欲刪除的隊頭結(jié)點(diǎn)暫存給p */
*e=p->data; /* 將欲刪除的隊頭結(jié)點(diǎn)的值賦值給e */
Q->front->next=p->next; /* 將原隊頭結(jié)點(diǎn)后繼p->next賦值給頭結(jié)點(diǎn)后綴 */
if(Q->rear==p) /* 若隊頭是隊尾耀销，則刪除后將rear指向頭結(jié)點(diǎn) */
Q->rear=Q->front;
free(p);
return OK;
}
在可以確定隊列長度最大值的情況下楼眷，建議用循環(huán)隊列，如果你無法預(yù)估隊列的長度時熊尉，則用鏈隊列罐柳。
