六、隊列的實現

隊列的定義及實現

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

?隊列的一些常用操作
??創建隊列
??銷毀隊列
??清空隊列
??進隊列
??出隊列
??獲取隊頭元素
??獲取隊列的長度
?隊列的順序存儲實現

實現代碼：附件中SeqQue文件夾
?隊列的鏈式存儲實現

實現代碼：附件中ListQue文件夾

隊列的優化實現

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

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

鏈式隊列的關鍵狀態
?空隊列狀態：front == NULL, rear == NULL;
關鍵操作
?入隊：
??rear->next = node;
??rear = node;
??node->next = NULL;
?出隊：
??front = front->next;
實現代碼：附件中ListQue_2文件夾

隊列的特別實現

棧與隊列：用棧實現隊列

實現思路
?準備兩個棧用于實現隊列：inStack和outStack
?當有新元素入隊時：將其壓入inStack中
?當需要出隊時：
??當outStack為空時：
???1. 將inStack中的元素逐一彈出并壓入outStack中
???2. 將outStack的棧頂元素彈出
??當outStack不為空時：
???– 直接將outStack的棧頂元素彈出
算法框架

實現代碼：附件中NewQue文件夾

附件