隊(duì)列概念
- 隊(duì)列是一種先進(jìn)先出的結(jié)構(gòu)，只允許在一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作，簡(jiǎn)稱 FIFO ，允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭
- 假設(shè)隊(duì)列 q=(a1,a2….an)，那么a1就是隊(duì)頭元素，an是隊(duì)尾元素，刪除操作總是從a1開(kāi)始，從an插入
隊(duì)列的抽象數(shù)據(jù)類(lèi)型
- Data（數(shù)據(jù)元素）：同線性表，元素具有相同的類(lèi)型，相鄰的元素具有前驅(qū)和后繼關(guān)系
- 基本操作
| 方法 | 描述 |
|---|---|
| initQueue(*Q) | 初始化操作，建立一個(gè)空隊(duì)列Q |
| DestoryQueue(*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ì)尾 |
| DeQueue(Q,e) | 刪除隊(duì)列Q中的隊(duì)頭元素，返回其值 |
| QueueLength(Q) | 返回隊(duì)列Q的元素個(gè)數(shù) |
隊(duì)列順序存儲(chǔ)的不足
- 入隊(duì)列操作是在隊(duì)尾追加一個(gè)元素，不需要移動(dòng)任何元素，時(shí)間復(fù)雜度為 O(1)
- 但順序存儲(chǔ)的隊(duì)列元素出列時(shí)元素都要向前移動(dòng)，時(shí)間復(fù)雜度為 O(n)
- 為解決隊(duì)列出隊(duì)時(shí)需要移動(dòng)全部數(shù)據(jù)，我們可以不去限制隊(duì)頭一定在下標(biāo)為 0 位置，引入兩個(gè)指針
- front 指向隊(duì)頭元素
- rear 指向隊(duì)尾元素下一個(gè)位置
- 當(dāng) front 等于 rear 時(shí)，隊(duì)列為空隊(duì)列，但會(huì)產(chǎn)生數(shù)組越界錯(cuò)誤與空間浪費(fèi)
循環(huán)隊(duì)列定義
- 為了解決假溢出，可以把隊(duì)列頭尾相接，rear 可以指向下標(biāo)為 0 的位置（當(dāng)下標(biāo)超過(guò)數(shù)組最大長(zhǎng)度時(shí)，指向下標(biāo) 0）
- 但可能會(huì)出現(xiàn)rear與front指針重合情況，無(wú)法判斷隊(duì)列是空還是滿
- 解決辦法：
- 設(shè)置一個(gè)flag，flag = 0 時(shí)隊(duì)列為空，flag = 1 時(shí)隊(duì)列滿
- 保留一個(gè)元素空間，當(dāng)隊(duì)列滿時(shí)，還有一個(gè)空閑單元
計(jì)算隊(duì)滿公式
- 由于 rear 可能比 front 大，也可能比 front 小，所以盡管只相差一個(gè)位置，但可能相差一整圈
若隊(duì)列最大尺寸為 QueueSize，那么當(dāng)隊(duì)列滿的條件是：（rear+1）% QueueSize == front（取模 % 的目的就是為了整合 rear 與 front 大小一樣的問(wèn)題）- 例如 QueueSize = 5，front = 0，而 rear = 4，（4+1）% 5 = 0 此時(shí)隊(duì)列滿
- 例如 QueueSize = 5，front = 2，而 rear = 1，（1+1）% 5 = 2 此時(shí)隊(duì)列滿
- 例如 QueueSize = 5，front = 2，而 rear = 0，（0+1）% 5 = 1，1 ≠ 2 此時(shí)隊(duì)列未滿
計(jì)算隊(duì)長(zhǎng)公式
- 當(dāng) rear > front 時(shí)，此時(shí)隊(duì)列的長(zhǎng)度為 rear - front ，但當(dāng) rear < front 時(shí)，隊(duì)列的長(zhǎng)度分為兩段，一段是 QueueSize - front，另一段是 0 + rear，隊(duì)列長(zhǎng)度為 rear - front + QueueSize，因此通用的計(jì)算隊(duì)列長(zhǎng)度的公式為：（rear-front+QueueSize）%QueueSize
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
- 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其實(shí)就是線性表的單鏈表，只不過(guò)它只能尾進(jìn)頭出而已，我們把它稱為鏈隊(duì)列
- 為方便操作，我們將隊(duì)頭指針指向鏈隊(duì)列的頭結(jié)點(diǎn)，而隊(duì)尾指針指向終端結(jié)點(diǎn)
- 空隊(duì)列時(shí)，front 和 rear 都指向頭結(jié)點(diǎn)
入隊(duì)操作
- 入隊(duì)操作其實(shí)就是在鏈表尾部插入結(jié)點(diǎn)
出隊(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)
循環(huán)隊(duì)列與鏈隊(duì)列的比較
- 從時(shí)間上：它們基本操作都是常數(shù)時(shí)間 O(1)，不過(guò)循環(huán)隊(duì)列事先申請(qǐng)好空間，使用期間不釋放，而對(duì)于鏈隊(duì)列，每次申請(qǐng)和釋放結(jié)點(diǎn)存在一些時(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)題，因此鏈隊(duì)列更加靈活
