棧與列隊(duì)
- 棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表
- 隊(duì)列是只允許在一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作的線性表
棧的定義
棧（stack）是限定僅在表尾進(jìn)行插入和刪除操作的線性表
允許插入和刪除的一端稱為棧頂（top），另一端稱為棧底（bottom），不含任何數(shù)據(jù)元素的棧稱為空棧。棧又稱為后進(jìn)先出（LastIn First Out）的線性表，簡(jiǎn)稱LIFO結(jié)構(gòu)
棧的插入操作，叫作進(jìn)棧，也稱壓棧、入棧，如下圖所示：
棧的刪除操作，叫作出棧，也有的叫作彈棧，如下圖所示：
棧的抽象數(shù)據(jù)類(lèi)型
對(duì)于棧來(lái)講，理論上線性表的操作特性它都具備，可由于它的特殊性，所以針對(duì)它在操作上會(huì)有些變化，特別是插入和刪除，push和pop操作，即壓棧和出棧
ADT 棧（stack）
Data
同線性表。元素具有相同的類(lèi)型，相鄰元素具有前驅(qū)和后繼關(guān)系。
Operation
Initstack(*S); 初始化操作，建立一個(gè)空棧S。
DestroyStack(*S); 若棧存在，則銷(xiāo)毀它。
ClearStack(*S); 將棧清空。
StackEmpty(S); 若棧為空，返回true;否則返回false。
GetTop(S,*e); 若棧存在且非空，用e返回S的棧頂元素。
Push(*S,e); 若棧S存在，插入新元素e到棧S中并成為棧頂元素。又稱：進(jìn)棧，壓棧，入棧。
Pop(*S,*e); 刪除棧S中棧頂元素，并用e返回其值。又稱：出棧，彈棧。
StackLength(S); 返回棧S的元素個(gè)數(shù)。
endADT
由于棧本身就是一個(gè)線性表，所以同樣具有線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
棧的順序存儲(chǔ)結(jié)構(gòu)
既然棧是線性表的特例，那么棧的順序存儲(chǔ)其實(shí)也是線性表順序存儲(chǔ)的簡(jiǎn)化，我們簡(jiǎn)稱為順序棧。線性表是用數(shù)組來(lái)實(shí)現(xiàn)的，那么想想看，對(duì)于棧這種只能一頭插入、刪除的線性表來(lái)說(shuō)，用數(shù)組哪一端作為棧頂和棧底比較好？
通常使用下標(biāo)為0的一端作為棧底，因?yàn)槭自囟即嬖跅５?，變化最小，所以讓它作為棧底。定義一個(gè)top變量來(lái)指示棧頂元素在數(shù)組中的位置，若存儲(chǔ)棧的長(zhǎng)度為StackSize，則棧頂位置top必須小于StackSize。當(dāng)棧存在一個(gè)元素時(shí)，top等于0，通常把空棧的判定條件定為top等于?1
棧的結(jié)構(gòu)定義
typedef int SElemType; /* SElemType類(lèi)型根據(jù)實(shí)際情況而定，這里假設(shè)為int */
typedef struct
{
SElemType data[MAXSIZE];
int top; /* 用于棧頂指針 */
}SqStack;
若現(xiàn)在有一個(gè)棧，StackSize是5，則棧普通情況、空棧和棧滿的情況示意圖如下：
進(jìn)棧操作
棧的插入，即入棧操作，入下圖：
入棧操作Push
/* 插入元素e為新的棧頂元素 */
Status Push(SqStack *S,SElemType e)
{
if(S->top == MAXSIZE -1) /* 棧滿 */
{
return ERROR;
}
S->top++; /* 棧頂指針增加一 */
S->data[S->top]=e; /* 將新插入元素賦值給棧頂空間 */
return OK;
}
出棧操作
出棧操作Pop
/* 若棧不空，則刪除S的棧頂元素，用e返回其值， 并返回OK；否則返回ERROR */
Status Pop(SqStack *S, SElemType *e)
{
if (S->top == -1) // ?？? return ERROR;
*e = S->data[S->top]; /* 將要?jiǎng)h除的棧頂元素賦值給e */
S->top--; /* 棧頂指針減一 */
return OK;
}
兩棧共享空間
其實(shí)棧的順序存儲(chǔ)還是很方便的，因?yàn)樗辉试S棧頂進(jìn)出元素，所以不存在線性表插入和刪除需要移動(dòng)元素的問(wèn)題，但是也存在一個(gè)缺陷，就是必須先確定數(shù)組存儲(chǔ)空間大小，萬(wàn)一不夠用，就需要使用編程手段進(jìn)行擴(kuò)容，很麻煩。
用一個(gè)數(shù)組來(lái)存儲(chǔ)兩個(gè)棧，數(shù)組有兩個(gè)端點(diǎn)，兩個(gè)棧有兩個(gè)棧底，讓一個(gè)棧的棧底為數(shù)組的始端，即下標(biāo)為0處，另一個(gè)棧為數(shù)組的末端，即下標(biāo)為數(shù)組長(zhǎng)度n-1處。兩個(gè)棧如果增加元素，就是兩端點(diǎn)向中間延伸
關(guān)鍵思路：它們是在數(shù)組的兩端，向中間靠攏，top1和top2是棧1和棧2的棧頂指針，只要它們倆不見(jiàn)面，兩個(gè)棧就可以一直使用。
當(dāng)棧1為空時(shí)，top1等于-1；當(dāng)棧2為空時(shí)，top2等于n。若棧2是空棧，棧1的top1等于n-1時(shí)，就是棧1滿了。反之，當(dāng)棧1為空，top2等于0時(shí)，棧2滿。但是更多數(shù)情況下是兩個(gè)棧見(jiàn)面之時(shí)，也就是兩個(gè)指針相差1，即top1+1=top2為棧滿
兩棧共享空間
/*兩棧共享空間結(jié)構(gòu) */
typedef struct
{
SElemType data[MAXSIZE];
int top1; /* 棧1棧頂指針 */
int top2; /* 棧2棧頂指針 */
} SqDoubleStack;
對(duì)于兩棧共享空間的push方法，除了要插入元素值參數(shù)外，還需要有一個(gè)判斷是棧1還是棧2的棧號(hào)參數(shù)stackNumber。
插入元素
/* 插入元素e為新的棧頂元素 */
Status Push(SqDoubleStack *S, SElemType e, int stackNumber)
{
/* 棧已滿，不能再push新元素了 */
if (S->top1 + 1 == S->top2)
return ERROR;
/* 棧1有元素進(jìn)棧 */
if (stackNumber == 1)
/* 若棧1則先top1+1后給數(shù)組元素賦值 */
S->data[++S->top1] = e;
/* 棧2有元素進(jìn)棧 */
else if (stackNumber == 2)
/* 若棧2則先top2-1后給數(shù)組元素賦值 */
S->data[--S->top2] = e;
return OK;
}
因?yàn)殚_(kāi)始我們就已經(jīng)判斷了是否有棧滿的情況，所以后面的top1+1和top2-1是不需要擔(dān)心溢出問(wèn)題的。
彈出元素
兩棧共享空間的pop方法，判斷棧1棧2的參數(shù)stackNumber即可
/* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{
if (stackNumber==1)
{
if (S->top1==-1)
return ERROR; /* 說(shuō)明棧1已經(jīng)是空棧，溢出 */
*e=S->data[S->top1--]; /* 將棧1的棧頂元素出棧 */
}
else if (stackNumber==2)
{
if (S->top2==MAXSIZE)
return ERROR; /* 說(shuō)明棧2已經(jīng)是空棧，溢出 */
*e=S->data[S->top2++]; /* 將棧2的棧頂元素出棧 */
}
return OK;
}
使用這樣的數(shù)據(jù)結(jié)構(gòu)，通常都是兩個(gè)棧的空間需求有相反關(guān)系時(shí)，也就是一個(gè)棧增長(zhǎng)另外一個(gè)?？s短的情況。這樣使用兩棧共享空間存儲(chǔ)方法才有較大的意義，否則兩個(gè)棧都在不停的增長(zhǎng)，那么很快就會(huì)因棧滿而溢出。
棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱為鏈棧
由于單鏈表有頭指針，而棧頂指針也是必須的，所以比較好的辦法是把棧頂放在單鏈表的頭部。另外，都已經(jīng)有了棧頂在頭部了，單鏈表中比較常用的頭結(jié)點(diǎn)也就失去了意義，通常對(duì)于鏈棧來(lái)說(shuō)，是不需要頭結(jié)點(diǎn)的。
對(duì)于鏈棧來(lái)說(shuō)，基本不存在棧滿的情況，除非內(nèi)存已經(jīng)沒(méi)有可以使用的空間，如果真的發(fā)生，那此時(shí)的計(jì)算機(jī)操作系統(tǒng)已經(jīng)面臨死機(jī)崩潰的情況，而不是這個(gè)鏈棧是否溢出的問(wèn)題。但對(duì)于空棧來(lái)說(shuō)，鏈表原定義是頭指針指向空，那么鏈棧的空其實(shí)就是top=NULL的時(shí)候。
鏈棧的結(jié)構(gòu)
/* 鏈棧結(jié)構(gòu) */
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
} StackNode,*LinkStackPtr;
typedef struct LinkStack
{
LinkStackPtr top;
int count;
} LinkStack;
棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——進(jìn)棧操作
對(duì)于鏈棧的進(jìn)棧push操作，假設(shè)元素值為e的新結(jié)點(diǎn)是s，top為棧頂指針，如下圖
/* 插入元素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)的直接后繼，見(jiàn)圖中1 */
S->top=s; /* 將新的結(jié)點(diǎn)s賦值給棧頂指針，見(jiàn)圖中2 */
S->count++;
return OK;
}
棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——出棧操作
假設(shè)變量p用來(lái)存儲(chǔ)要?jiǎng)h除的棧頂結(jié)點(diǎn)，將棧頂指針下移一位，最后釋放p即可
/* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */
Status Pop(LinkStack *S,SElemType *e)
{
LinkStackPtr p;
if(StackEmpty(*S))
return ERROR;
*e=S->top->data;
p=S->top; /* 將棧頂結(jié)點(diǎn)賦值給p，見(jiàn)圖中③ */
S->top=S->top->next; /* 使得棧頂指針下移一位，指向后一結(jié)點(diǎn)，見(jiàn)圖中④ */
free(p); /* 釋放結(jié)點(diǎn)p */
S->count--;
return OK;
}
鏈棧的進(jìn)棧push和出棧pop沒(méi)有任何循環(huán)操作，時(shí)間復(fù)雜度均為O(1)。
順序棧與鏈棧對(duì)比
1、它們時(shí)間復(fù)雜度上均為O(1)。
2、對(duì)于空間性能，順序棧需要事先確定一個(gè)固定的長(zhǎng)度，可能會(huì)存在內(nèi)存空間浪費(fèi)的問(wèn)題，但它的優(yōu)勢(shì)是存取時(shí)定位很方便，而鏈棧則要求每個(gè)元素都有指針域，這同時(shí)也增加了一些內(nèi)存開(kāi)銷(xiāo)，但對(duì)于棧的長(zhǎng)度無(wú)限制
3、如果棧的使用過(guò)程中元素變化不可預(yù)料，有時(shí)很小，有時(shí)非常大，那么最好是用鏈棧，如果它的變化在可控范圍內(nèi)，建議使用順序棧
棧的作用
棧的引入簡(jiǎn)化了程序設(shè)計(jì)的問(wèn)題，劃分了不同關(guān)注層次，使得思考范圍縮小，更加聚焦于要解決的問(wèn)題核心。反之，像數(shù)組等，因?yàn)橐稚⒕θタ紤]數(shù)組的下標(biāo)增減等細(xì)節(jié)問(wèn)題，反而掩蓋了問(wèn)題的本質(zhì)。
對(duì)于一些高級(jí)的語(yǔ)言，比如：Java,OC等都有對(duì)棧結(jié)構(gòu)的封裝，可以不需要關(guān)注它的實(shí)現(xiàn)細(xì)節(jié)，就可以直接使用stack的push和pop方法，非常方便。
棧的應(yīng)用-遞歸
棧有一個(gè)很重要的應(yīng)用：在程序設(shè)計(jì)語(yǔ)言中實(shí)現(xiàn)了遞歸。遞歸中的一個(gè)結(jié)點(diǎn)例子：斐波那契數(shù)列。
斐波那契數(shù)列實(shí)現(xiàn)
如果兔子在出生兩個(gè)月后就有繁殖能力，一對(duì)兔子每個(gè)月能生出一對(duì)小兔子。假設(shè)所有的兔都不死，那么一年后可以繁殖多少對(duì)兔子？
分析
第一個(gè)月兔子沒(méi)有繁殖能力，所以還是一對(duì)；第二個(gè)月也還是一對(duì)，兩個(gè)月后，生下一對(duì)兔子，小兔子總數(shù)為2；三個(gè)月后，老兔子又生下一對(duì)，因?yàn)樾⊥米幽壳斑€沒(méi)有繁殖能力，所以現(xiàn)在為3對(duì)兔子，這樣一次類(lèi)推，如下圖：
表中數(shù)字1，1，2，3，5，8，13...構(gòu)成了一個(gè)序列，而且又明顯的特點(diǎn)：前面相鄰兩項(xiàng)只和構(gòu)成后一項(xiàng)
編號(hào)①的一對(duì)兔子經(jīng)過(guò)六個(gè)月就變成8對(duì)兔子，數(shù)學(xué)函數(shù)來(lái)定義就是：
打印出前40位的斐波那契數(shù)列數(shù)。
#include "stdio.h"
int Fbi(int i) /* 斐波那契的遞歸函數(shù) */
{
if( i < 2 )
return i == 0 ? 0 : 1;
return Fbi(i - 1) + Fbi(i - 2); /* 這里Fbi就是函數(shù)自己，等于在調(diào)用自己 */
}
int main()
{
int i;
int a[40];
printf("迭代顯示斐波那契數(shù)列：\n");
a[0]=0;
a[1]=1;
printf("%d ",a[0]);
printf("%d ",a[1]);
for(i = 2;i < 40;i++)
{
a[i] = a[i-1] + a[i-2];
printf("%d ",a[i]);
}
printf("\n");
printf("遞歸顯示斐波那契數(shù)列：\n");
for(i = 0;i < 40;i++)
printf("%d ", Fbi(i));
return 0;
}
遞歸定義
把一個(gè)直接調(diào)用自己或通過(guò)一系列的調(diào)用語(yǔ)句間接地調(diào)用自己的函數(shù)，稱做遞歸函數(shù)。當(dāng)然，寫(xiě)遞歸程序最怕的就是陷入永不結(jié)束的無(wú)窮遞歸中，所以，每個(gè)遞歸定義必須至少有一個(gè)條件，滿足時(shí)遞歸不再進(jìn)行。
| 迭代 | 遞歸 |
|---|---|
| 循環(huán)結(jié)構(gòu) | 選擇結(jié)構(gòu) |
| 不需要反復(fù)調(diào)用函數(shù)和占用額外的內(nèi)存 | 使程序的結(jié)構(gòu)更清晰、更簡(jiǎn)潔、更容易讓人理解，從而減少讀懂代碼的時(shí)間。但是大量的遞歸調(diào)用會(huì)建立函數(shù)的副本，會(huì)耗費(fèi)大量的時(shí)間和內(nèi)存 |
在前行階段，對(duì)于每一層遞歸，函數(shù)的局部變量、參數(shù)值以及返回地址都被壓入棧中。在退回階段，位于棧頂?shù)木植孔兞?、參?shù)值和返回地址被彈出，用于返回調(diào)用層次中執(zhí)行代碼的其余部分，也就是恢復(fù)了調(diào)用的狀態(tài)
隊(duì)列的定義
隊(duì)列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表
隊(duì)列是一種先進(jìn)先出（First In First Out）的線性表，簡(jiǎn)稱FIFO。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。假設(shè)隊(duì)列是q=(a1，a2，...，an)，那么那么a1就是隊(duì)頭元素，而an是隊(duì)尾元素。刪除時(shí)，總是從a1開(kāi)始，而插入時(shí)，列在最后。
隊(duì)列的抽象數(shù)據(jù)類(lèi)型
ADT 隊(duì)列(Queue)
Data
同線性表。元素具有相同的類(lèi)型，相鄰元素具有前驅(qū)和后繼關(guān)系。
Operation
InitQueue(*Q): 初始化操作，建立一個(gè)空隊(duì)列Q。
DestroyQueue(*Q): 若隊(duì)列Q存在，則銷(xiāo)毀它。
ClearQueue(*Q): 將隊(duì)列Q清空。
QueueEmpty(Q): 若隊(duì)列Q為空，返回true，否則返回false。
GetHead(Q, *e): 若隊(duì)列Q存在且非空，用e返回隊(duì)列Q的隊(duì)頭元素。
EnQueue(*Q, e): 若隊(duì)列Q存在，插入新元素e到隊(duì)列Q中并成為隊(duì)尾元素。
DeQueue(*Q, *e): 刪除隊(duì)列Q中隊(duì)頭元素，并用e返回其值。
QueueLength(Q): 返回隊(duì)列Q的元素個(gè)數(shù)
endADT
循環(huán)隊(duì)列
線性表有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，棧式線性表，所以有這兩種存儲(chǔ)方式，同樣，列隊(duì)作為一種特殊的線性表，也同樣存在這兩種存儲(chǔ)方式。先看列隊(duì)的順序存儲(chǔ)結(jié)構(gòu)。
隊(duì)列順序存儲(chǔ)的不足
假設(shè)一個(gè)隊(duì)列有n個(gè)元素，則順序存儲(chǔ)的隊(duì)列需建立一個(gè)大于n的數(shù)組，并把隊(duì)列的所有元素存儲(chǔ)在數(shù)組的前n個(gè)單元，數(shù)組下標(biāo)為0的一端即是隊(duì)頭。所謂的入隊(duì)列操作就是在隊(duì)尾追加一個(gè)元素，不需要移動(dòng)任何元素，時(shí)間復(fù)雜度為O(1)，如下圖：
與棧不同的是，隊(duì)列元素的出列是在隊(duì)頭，即下標(biāo)為0的位置，隊(duì)列中的所有元素都得向前移動(dòng)，以保證隊(duì)列的隊(duì)頭，也就是下標(biāo)為0的位置不為空，此時(shí)時(shí)間復(fù)雜度為O(n)，如下圖：
可細(xì)想一下，為什么出列隊(duì)時(shí)一定要移動(dòng)全部元素？如果不去限制列隊(duì)的元素必須存儲(chǔ)在數(shù)組的前n個(gè)單元這一條件，那么出隊(duì)的性能就會(huì)大大增加，也就是說(shuō)，隊(duì)頭不需要一定在下標(biāo)為0的位置。
為了避免當(dāng)只有一個(gè)元素時(shí)，隊(duì)頭和隊(duì)尾重合使處理變得麻煩，所以引入兩個(gè)指針，front指針指向隊(duì)頭元素，rear指針指向隊(duì)尾元素的下一個(gè)位置，當(dāng)front等于rear時(shí)，此隊(duì)列不是還剩一個(gè)元素，而是空隊(duì)列。
假設(shè)是長(zhǎng)度為5的數(shù)組，初始狀態(tài)，front與rear指針均指向下標(biāo)為0的位置。然后入隊(duì)a1、a2、a3、a4，front指針依然指向下標(biāo)為0位置，而rear指針指向下標(biāo)為4的位置
出隊(duì)a1,a2，front指針指向下標(biāo)為2的位置，rear不變，再入隊(duì)a5，front指針不變，rear指針移動(dòng)到數(shù)組之外，如下圖
而且問(wèn)題還不止如此，假設(shè)這個(gè)列隊(duì)的總個(gè)數(shù)不超過(guò)5個(gè)，但是目前繼續(xù)接著入隊(duì)，因?yàn)閿?shù)組末尾元素已經(jīng)被占用，再向后加，就會(huì)產(chǎn)生數(shù)組越界。而實(shí)際上，我們列隊(duì)的下標(biāo)0和1的地方還是空閑，這是一種“假溢出”。
循環(huán)隊(duì)列定義
為了解決假溢出問(wèn)題，當(dāng)后面滿了，就再?gòu)念^開(kāi)始，也就是頭尾相接的循環(huán)。隊(duì)列的這種頭尾相接的順序存儲(chǔ)結(jié)構(gòu)稱為循環(huán)隊(duì)列。
繼續(xù)上面的例子，rear可以改為指向下標(biāo)為0的位置，這樣就不會(huì)造成指針指向不明的問(wèn)題，如下圖：
接著入隊(duì)a6，將它放置于下標(biāo)為0處，rear指針指向下標(biāo)為1處，如左圖。再入隊(duì)a7，則rear指針就與front指針重合，同時(shí)指向下標(biāo)為2的位置，如下圖
此時(shí)問(wèn)題又來(lái)了，因?yàn)榭樟嘘?duì)的時(shí)候front等于rear，現(xiàn)在當(dāng)列隊(duì)滿了，也是front等于rear，那么如何判斷此時(shí)的隊(duì)列究竟是空還是滿呢？
辦法一：設(shè)置一個(gè)標(biāo)志變量flag，當(dāng)front==rear，且flag=0時(shí)為隊(duì)列空，當(dāng)front==rear，且flag=1時(shí)為隊(duì)列滿。
辦法二：當(dāng)隊(duì)列空時(shí)，條件就是front=rear，當(dāng)隊(duì)列滿時(shí)，保留一個(gè)元素空間，如下圖。也就是說(shuō)，隊(duì)列滿時(shí)，數(shù)組中還有一個(gè)空閑單元，就認(rèn)為此隊(duì)列已經(jīng)滿了，即不允許上圖右圖情況出現(xiàn)
由于rear可能比f(wàn)ront大，也可能比f(wàn)ront小，所以盡管它們只相差一個(gè)位置時(shí)就是滿的情況，但也可能是相差整整一圈， 若隊(duì)列的最大尺寸為QueueSize，隊(duì)列滿的條件是(rear+1)%QueueSize==front
（取?！?”的目的就是為了整合rear與front大小為一個(gè)問(wèn)題）。
比如上面例子中:
QueueSize = 5,當(dāng)front=0,rear=4,(4+0) % 5=0，此時(shí)列隊(duì)滿;
又比如front=2，而rear=1。(1+1)%5=2，此時(shí)隊(duì)列也是滿的;
而front=2，rear=0,(0+1)%5=1,1≠2，此時(shí)隊(duì)列并沒(méi)有滿。
另外，當(dāng)rear>front時(shí)，隊(duì)列的長(zhǎng)度為rear-front。當(dāng)rear<front時(shí)，隊(duì)列長(zhǎng)度分為兩段，一段是QueueSize-front，另一段是0+rear，加在一起，隊(duì)列長(zhǎng)度為rear-front+Queue。因此通用的計(jì)算隊(duì)列長(zhǎng)度公式為：
(rear-front + QueueSize) % QueueSize
循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)
typedef int QElemType;
/* 循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) */
typedef struct
{
QElemType data[MAXSIZE];
int front; /* 頭指針 */
int rear; /* 尾指針，若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置 */
}SqQueue;
初始化
/* 初始化一個(gè)空隊(duì)列Q */
Status InitQueue(SqQueue *Q)
{
Q->front=0;
Q->rear=0;
return OK;
}
求隊(duì)列長(zhǎng)度
/* 返回Q的元素個(gè)數(shù)，也就是隊(duì)列的當(dāng)前長(zhǎng)度 */
int QueueLength(SqQueue Q)
{
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
入隊(duì)列操作
/* 若隊(duì)列未滿，則插入元素e為Q新的隊(duì)尾元素 */
Status EnQueue(SqQueue *Q,QElemType e)
{
if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊(duì)列滿的判斷 */
return ERROR;
Q->data[Q->rear]=e; /* 將元素e賦值給隊(duì)尾 */
Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置， */
/* 若到最后則轉(zhuǎn)到數(shù)組頭部 */
return OK;
}
出隊(duì)列操作
/* 若隊(duì)列不空，則刪除Q中隊(duì)頭元素，用e返回其值 */
Status DeQueue(SqQueue *Q,QElemType *e)
{
if (Q->front == Q->rear) /* 隊(duì)列空的判斷 */
return ERROR;
*e=Q->data[Q->front]; /* 將隊(duì)頭元素賦值給e */
Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置， */
/* 若到最后則轉(zhuǎn)到數(shù)組頭部 */
return OK;
}
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是線性表的單鏈表，只不過(guò)它只能尾進(jìn)頭出，簡(jiǎn)稱為鏈隊(duì)列。
將隊(duì)頭指針指向鏈隊(duì)列的頭結(jié)點(diǎn)，隊(duì)尾指針指向終端結(jié)點(diǎn)
空隊(duì)列時(shí)，front和rear都指向頭結(jié)點(diǎn)
鏈隊(duì)列的結(jié)構(gòu)
/* QElemType類(lèi)型根據(jù)實(shí)際情況而定，這里假設(shè)為int */
typedef int QElemType;
typedef struct QNode /* 結(jié)點(diǎn)結(jié)構(gòu) */
{
QElemType data;
struct QNode *next;
} QNode,*QueuePtr;
typedef struct /* 隊(duì)列的鏈表結(jié)構(gòu) */
{
QueuePtr front,rear; /* 隊(duì)頭、隊(duì)尾指針 */
} LinkQueue;
入隊(duì)操作
入隊(duì)操作時(shí)就是在鏈表尾部插入結(jié)點(diǎn)
/* 插入元素e為Q的新的隊(duì)尾元素 */
Status EnQueue(LinkQueue *Q,QElemType e)
{
QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
if(!s) /* 存儲(chǔ)分配失敗 */
exit(OVERFLOW);
s->data=e;
s->next=NULL;
Q->rear->next=s; /* 把擁有元素e的新結(jié)點(diǎn)s賦值給原隊(duì)尾結(jié)點(diǎn)的后繼，見(jiàn)圖中1 */
Q->rear=s; /* 把當(dāng)前的s設(shè)置為隊(duì)尾結(jié)點(diǎn)，rear指向s，見(jiàn)圖中2 */
return OK;
}
出隊(duì)操作
出隊(duì)操作時(shí)，就是頭結(jié)點(diǎn)的后繼結(jié)點(diǎn)出隊(duì)，將頭結(jié)點(diǎn)的后繼改為它后面的結(jié)點(diǎn)，若鏈表除頭結(jié)點(diǎn)外只剩一個(gè)元素時(shí)，則需將rear指向頭結(jié)點(diǎn)
/* 若隊(duì)列不空,刪除Q的隊(duì)頭元素,用e返回其值,并返回OK,否則返回ERROR */
Status DeQueue(LinkQueue *Q,QElemType *e)
{
QueuePtr p;
if(Q->front==Q->rear)
return ERROR;
p=Q->front->next; /* 將欲刪除的隊(duì)頭結(jié)點(diǎn)暫存給p，見(jiàn)圖中1 */
*e=p->data; /* 將欲刪除的隊(duì)頭結(jié)點(diǎn)的值賦值給e */
Q->front->next=p->next;/* 將原隊(duì)頭結(jié)點(diǎn)的后繼p->next賦值給頭結(jié)點(diǎn)后繼，見(jiàn)圖中2 */
if(Q->rear==p) /* 若隊(duì)頭就是隊(duì)尾，則刪除后將rear指向頭結(jié)點(diǎn)，見(jiàn)圖中3 */
Q->rear=Q->front;
free(p);
return OK;
}
循環(huán)隊(duì)列與鏈隊(duì)列
時(shí)間上，基本操作都為O(1)，不過(guò)循環(huán)隊(duì)列是事先申請(qǐng)好空間，使用期間不釋放，而對(duì)于鏈隊(duì)列，每次申請(qǐng)和釋放結(jié)點(diǎn)也會(huì)存在一些時(shí)間開(kāi)銷(xiāo)，如果入隊(duì)出隊(duì)頻繁，則兩者還是有細(xì)微差異。
空間上，循環(huán)隊(duì)列必須有一個(gè)固定的長(zhǎng)度，所以就有了存儲(chǔ)元素個(gè)數(shù)和空間浪費(fèi)的問(wèn)題。而鏈隊(duì)列不存在這個(gè)問(wèn)題，盡管它需要一個(gè)指針域，會(huì)產(chǎn)生一些空間上的開(kāi)銷(xiāo)，但也可以接受。所以在空間上，鏈隊(duì)列更加靈活。
在可以確定隊(duì)列長(zhǎng)度最大值的情況下，建議用循環(huán)隊(duì)列，如果無(wú)法預(yù)估隊(duì)列的長(zhǎng)度時(shí)，則用鏈隊(duì)列
參考
《大話數(shù)據(jù)結(jié)構(gòu)》
