棧與列隊(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ù)類型
對(duì)于棧來(lái)講，理論上線性表的操作特性它都具備霞赫，可由于它的特殊性腮介，所以針對(duì)它在操作上會(huì)有些變化，特別是插入和刪除端衰，push和pop操作叠洗，即壓棧和出棧
ADT 棧（stack）
Data
同線性表甘改。元素具有相同的類型，相鄰元素具有前驅(qū)和后繼關(guān)系灭抑。
Operation
Initstack(*S); 初始化操作十艾，建立一個(gè)空棧S。
DestroyStack(*S); 若棧存在腾节，則銷毀它忘嫉。
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)槭自囟即嬖跅５咨烫荆兓钚⊙嗫蹋宰屗鳛闂５住６x一個(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類型根據(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è)椝馄牵縮短的情況。這樣使用兩棧共享空間存儲(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)銷，但對(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ì)兔子犯眠，這樣一次類推，如下圖：
表中數(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ù)類型
ADT 隊(duì)列(Queue)
Data
同線性表微驶。元素具有相同的類型浪谴，相鄰元素具有前驅(qū)和后繼關(guān)系。
Operation
InitQueue(*Q): 初始化操作因苹，建立一個(gè)空隊(duì)列Q苟耻。
DestroyQueue(*Q): 若隊(duì)列Q存在，則銷毀它扶檐。
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類型根據(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)銷，如果入隊(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)銷菇用，但也可以接受澜驮。所以在空間上，鏈隊(duì)列更加靈活惋鸥。
在可以確定隊(duì)列長(zhǎng)度最大值的情況下杂穷，建議用循環(huán)隊(duì)列，如果無(wú)法預(yù)估隊(duì)列的長(zhǎng)度時(shí)卦绣，則用鏈隊(duì)列
參考
《大話數(shù)據(jù)結(jié)構(gòu)》
