六、隊(duì)列的實(shí)現(xiàn)

隊(duì)列的定義及實(shí)現(xiàn)

?隊(duì)列的定義
??隊(duì)列是一種特殊的線性表
??隊(duì)列僅在線性表的兩端進(jìn)行操作
???隊(duì)頭(Front)：取出數(shù)據(jù)元素的一端
???隊(duì)尾(Rear)：插入數(shù)據(jù)元素的一端
?隊(duì)列的性質(zhì)
??先進(jìn)先出(FIFO,First In First Out)

?隊(duì)列的一些常用操作
??創(chuàng)建隊(duì)列
??銷毀隊(duì)列
??清空隊(duì)列
??進(jìn)隊(duì)列
??出隊(duì)列
??獲取隊(duì)頭元素
??獲取隊(duì)列的長度
?隊(duì)列的順序存儲(chǔ)實(shí)現(xiàn)

實(shí)現(xiàn)代碼：附件中SeqQue文件夾
?隊(duì)列的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)

實(shí)現(xiàn)代碼：附件中ListQue文件夾

隊(duì)列的優(yōu)化實(shí)現(xiàn)

?順序隊(duì)列
??線性表的第一個(gè)元素作為隊(duì)頭
??線性表的最后一個(gè)元素作為隊(duì)尾
?入隊(duì)的新元素是在線性表的最后,時(shí)間復(fù)雜度為O(1)
?出隊(duì)時(shí)需要將后續(xù)的所有元素向前移動(dòng)，時(shí)間復(fù)雜度O(n)
問題：如何將出隊(duì)操作的時(shí)間復(fù)雜度降低到O(1)?
順序隊(duì)列的優(yōu)化方案
?定義front使其始終代表隊(duì)頭的下標(biāo)
??出隊(duì)時(shí)將隊(duì)頭元素返回，且front++
?定義rear使其始終代表隊(duì)尾下一個(gè)元素的下標(biāo)
??入隊(duì)時(shí)將新元素插入，且rear++
?沒有必要只將下標(biāo)為0的位置定義為隊(duì)頭

順序隊(duì)列的關(guān)鍵狀態(tài)
?初始狀態(tài)：length == 0, front == 0, rear == 0;
?空隊(duì)列狀態(tài)：length == 0, front == rear;
?滿隊(duì)列狀態(tài)：length == capacity, front == rear;
循環(huán)使用隊(duì)列中的空間
?入隊(duì)：rear = (rear + 1) % capacity;
?出隊(duì)：front = (front + 1) % capacity;
實(shí)現(xiàn)代碼：附件中SeqQue_2文件夾
鏈?zhǔn)疥?duì)列的瓶頸
?鏈?zhǔn)疥?duì)列
??線性表的第一個(gè)元素作為隊(duì)頭
??線性表的最后一個(gè)元素作為隊(duì)尾
?入隊(duì)的新元素是在線性表的最后，時(shí)間復(fù)雜度為O(n)
?出隊(duì)的元素即鏈表的第一個(gè)元素，時(shí)間復(fù)雜度O(1)
問題：如何將入隊(duì)操作的時(shí)間復(fù)雜度降低到O(1)?
鏈?zhǔn)疥?duì)列的優(yōu)化方案
?定義rear指針始終指向鏈表中的最有一個(gè)元素
??入隊(duì)時(shí)將新元素通過rear插入隊(duì)尾，且將rear指向新元素

鏈?zhǔn)疥?duì)列的關(guān)鍵狀態(tài)
?空隊(duì)列狀態(tài)：front == NULL, rear == NULL;
關(guān)鍵操作
?入隊(duì)：
??rear->next = node;
??rear = node;
??node->next = NULL;
?出隊(duì)：
??front = front->next;
實(shí)現(xiàn)代碼：附件中ListQue_2文件夾

隊(duì)列的特別實(shí)現(xiàn)

棧與隊(duì)列：用棧實(shí)現(xiàn)隊(duì)列

實(shí)現(xiàn)思路
?準(zhǔn)備兩個(gè)棧用于實(shí)現(xiàn)隊(duì)列：inStack和outStack
?當(dāng)有新元素入隊(duì)時(shí)：將其壓入inStack中
?當(dāng)需要出隊(duì)時(shí)：
??當(dāng)outStack為空時(shí)：
???1. 將inStack中的元素逐一彈出并壓入outStack中
???2. 將outStack的棧頂元素彈出
??當(dāng)outStack不為空時(shí)：
???– 直接將outStack的棧頂元素彈出
算法框架

實(shí)現(xiàn)代碼：附件中NewQue文件夾

附件