Go 數(shù)據(jù)結(jié)構(gòu)和算法篇（三）：隊列
一、隊列的概念
介紹完棧之后，接下來我們要介紹的是另一種跟棧很相似的數(shù)據(jù)結(jié)構(gòu) —— 隊列。
和棧一樣，隊列也是一種特殊的線性表結(jié)構(gòu)，只不過隊列是在一端插入，另一端刪除，就跟我們平常排隊一樣的道理，從隊尾入隊，在隊頭出去，所以隊列的特性是先入先出（FIFO），允許插入的一端叫隊尾，允許刪除的一端叫隊頭。
一張圖可以形象地體現(xiàn)兩者的差別：
和棧一樣，隊列也可以通過數(shù)組和鏈表實現(xiàn)，通過數(shù)組實現(xiàn)的叫順序隊列，通過鏈表實現(xiàn)的叫做鏈式隊列，棧只需要一個棧頂指針就可以了，因為只允許在棧頂插入刪除，但是隊列需要兩個指針，一個指向隊頭，一個指向隊尾。
二、隊列的實現(xiàn)
基于鏈表實現(xiàn)隊列的示例代碼
下面我們以鏈式隊列為例，看看如何通過 Go 代碼基于鏈表實現(xiàn)隊列這種數(shù)據(jù)結(jié)構(gòu)，這里我們?yōu)殛犃刑峁┝巳腙?、出隊和遍歷三種操作：
package main
import (
"fmt"
)
// 定義鏈表節(jié)點
type Node struct {
Value int
Next *Node
}
// 初始化隊列
var size = 0
var queue = new(Node)
// 入隊（從隊頭插入）
func Push(t *Node, v int) bool {
if queue == nil {
queue = &Node{v, nil}
size++
return true
}
t = &Node{v, nil}
t.Next = queue
queue = t
size++
return true
}
// 出隊（從隊尾刪除）
func Pop(t *Node) (int, bool) {
if size == 0 {
return 0, false
}
if size == 1 {
queue = nil
size--
return t.Value, true
}
// 迭代隊列，直到隊尾
temp := t
for (t.Next) != nil {
temp = t
t = t.Next
}
v := (temp.Next).Value
temp.Next = nil
size--
return v, true
}
// 遍歷隊列所有節(jié)點
func traverse(t *Node) {
if size == 0 {
fmt.Println("空隊列!")
return
}
for t != nil {
fmt.Printf("%d -> ", t.Value)
t = t.Next
}
fmt.Println()
}
func main() {
queue = nil
// 入隊
Push(queue, 10)
fmt.Println("Size:", size)
// 遍歷
traverse(queue)
// 出隊
v, b := Pop(queue)
if b {
fmt.Println("Pop:", v)
}
fmt.Println("Size:", size)
// 批量入隊
for i := 0; i < 5; i++ {
Push(queue, i)
}
// 再次遍歷
traverse(queue)
fmt.Println("Size:", size)
// 出隊
v, b = Pop(queue)
if b {
fmt.Println("Pop:", v)
}
fmt.Println("Size:", size)
// 再次出隊
v, b = Pop(queue)
if b {
fmt.Println("Pop:", v)
}
fmt.Println("Size:", size)
// 再次遍歷
traverse(queue)
}
除了入隊出隊位置和棧不同外，其他代碼實現(xiàn)很相似。運行上述代碼，打印結(jié)果如下：
基于數(shù)組實現(xiàn)隊列存在的問題
如果通過數(shù)組實現(xiàn)順序隊列的話，有一個問題，就是隨著隊列元素的插入和刪除，隊尾指針和隊頭指針不斷后移，從而導致隊尾指針指向末尾無法繼續(xù)插入數(shù)據(jù)，這時候有可能隊列頭部還是有剩余空間的，如下圖所示：
我們當然可以通過數(shù)據(jù)搬移的方式把所有隊列數(shù)據(jù)往前移，但這會增加額外的時間復雜度，如果頻繁操作數(shù)據(jù)量很大的隊列，顯然對性能有嚴重損耗，對此問題的解決方案是循環(huán)隊列，即把隊列頭尾連起來：
這樣一來就不會出現(xiàn)之前的問題了。此時判斷隊列是否為空的條件還是 tail==head，但是判斷隊列是否滿的條件就變成了 (tail+1) % maxsize == head，maxsize 是數(shù)組的長度，浪費一個空間是為了避免混淆判斷空隊列的條件。
當然如果通過鏈表來實現(xiàn)隊列的話，顯然沒有這類問題，因為鏈表沒有空間限制。
三、隊列的使用場景
隊列的使用也非常廣泛，比如我們在業(yè)務系統(tǒng)中經(jīng)常看到的消息隊列系統(tǒng)（如 RabbitMq、Kafka、RocketMq 等）就是隊列的典型應用場景。
（本文完）
學習過程中有任何問題，可以通過下面的評論功能或加入「Go 語言研習社」與學院君討論：
本系列教程首發(fā)在 geekr.dev，你可以點擊頁面左下角閱讀原文鏈接查看最新更新的教程。