#23 佇列 Queue | Golang魔法使 - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

第 12 屆 iThome 鐵人賽

DAY 23

自我挑戰組

Golang魔法使 ─ 30天從零開始學習Go語言 | 比Python還簡單 | 理科生一定學得會 | 文科生不好說系列第 23 篇

#23 佇列 Queue | Golang魔法使

12th鐵人賽

liao2000

2020-09-23 22:20:00

1762 瀏覽

分享至

小櫻以同學千春送了遊樂園的門票為由邀請她最喜歡的雪兔哥一起去遊樂園，但是假日遊樂園人最多了，導致他們一直在排隊。

排隊的隊伍可以視作一個佇列。假設小櫻排在小狼前面，那麼工作人員理論上要先讓小櫻上遊樂設施再來才是小狼。這就是所謂的先進先出。與堆疊剛好相反，堆疊只適用你疊在椅子上的衣服而已 (X

佇列 Queue 先加入的元素先取出 (先進先出) First in first out (FIFO)
堆疊 Stack 後加入的元素先取出 (後進先出) Last in first out (LIFO)

什麼是佇列

佇列和堆疊、鏈結串列一樣都是一種資料結構，你可以把佇列想像成一個型態，但是這個型態必需能實作以下方法

type Element{

}

type Queue interface{
    En(Element)     // 把元素加入佇列頂端
    De() Element    // 返回最先加入的元素 (返回尾端的元素)
    IsEmpty() bool  // 佇列為空
}

↑ 先進先出的概念

創建 package

首先我們先創建一個 package，至於要怎麼創建？請複習：#14 套件 Package (2020) & 套件實戰(math, http, sort) | Golang魔法使

我們先建立一些基本的結構體：

./queue/queue.go

package queue

type Queue struct{
    list   []interface{}
    top    int    // 新元素從頭加入
    bottom int    // 提取元素從尾端提取
    len    int    // 記錄元素個數方便後續處理
}

實作 New() 提供給使用者快速建立一個 *Queue

func New() *Queue{
    q := new(Queue)
    // 預設長度為 8, 容量為 8
    // 在本範例中將slice的長度與容量設為一樣
    // 以方便實作
    q.list   = make([]interface{}, 8, 8)
    q.top    = -1
    //q.bottom = 0    new()的時候已預設為 0
    //q.len    = 0    new()的時候已預設為 0
    return q
}

新增 IsEmpty() 方法

func (q *Queue) IsEmpty() bool{
    return q.len == 0
}

新增 En() 方法

在實作前說明一下，這裡的實作是從 top 加入，但是如果只從 top 加入，又從 bottom 取出會導致可能出現

空空空空空...空有有有有

這種情況，所以如果切片(q.list)前方是空的，會將 top 往回指

空空空空空...空有有有有
有空空空空...空有有有有

也因為這樣很難判定切片有沒有滿，所以額外用 q.len 記錄當前切片確實有使用元素的個數

func (q *Queue) En(val interface{}){
    // 如果 q.list 滿了就將 q.list 擴大原先的兩倍
    if q.len == cap(q.list){
        oldCap := cap(q.list)
        newCap := oldCap << 1
        newList := make([]interface{}, newCap, newCap)
        // 一共有 len 個元素所以迴圈 len 次
        for i:=0; i< q.len; i++{
            newList[i] = q.list[(q.bottom + i) % oldCap]
        }
        q.list   = newList
        q.top    = q.len-1
        q.bottom = 0
    }

    // O: 空 X: 有值
    // 欲加入新元素至：
    // OOOOXXXX bottom = 4, top = 7, len = 4, cap(list) = 8
    // 此時將 (top + 1) % cap 則可得 top = 0
    // XOOOXXXX
    
    q.top = (q.top + 1) % cap(q.list)
    q.list[q.top] = val
    q.len++
}

新增 De() 方法

如果 q.len 小於 cap(q.list) 的四分之一，我們會宣告新的切片(容量和長度為原先一半)來取代 q.list 以免浪費空間。但看在大家都是新手魔法使就先不這樣實作了

func (q *Queue) De() interface{}{
    if q.IsEmpty(){
        return nil
    }
    temp := q.list[q.bottom]
    q.bottom = (q.bottom + 1) % cap(q.list)
    q.len--
    return temp
}

額外新增 ToSlice() 方法以方便 debug

func (q *Queue) ToSlice() []interface{}{
    s   := make([]interface{}, q.len, q.len)
    cap := cap(q.list)
    for i:=0; i< q.len; i++{
        s[i] = q.list[(q.bottom + i) % cap]
    }
    return s
}

./lesson23.go

本系列教學採用新版 Golang version >= 1.11 並使用 go mod 初始化為 practice module

package main

import(
    "practice/queue"
    "fmt"
)

func main(){
    myQueue := queue.New()
    myQueue.En("小櫻")
    fmt.Println(myQueue.ToSlice())  // [小櫻]
    myQueue.En("知世")
    fmt.Println(myQueue.ToSlice())  // [小櫻 知世]
    myQueue.En("桃矢")
    fmt.Println(myQueue.ToSlice())  // [小櫻 知世 桃矢]
    myQueue.En("小狼")
    fmt.Println(myQueue.ToSlice())  // [小櫻 知世 桃矢 小狼]
    myQueue.En("莓玲")
    fmt.Println(myQueue.ToSlice())  // [小櫻 知世 桃矢 小狼 莓玲]
    myQueue.En("千春")
    fmt.Println(myQueue.ToSlice())  // [小櫻 知世 桃矢 小狼 莓玲 千春]
    myQueue.En("唬爛王山琦")
    fmt.Println(myQueue.ToSlice())  // [小櫻 知世 桃矢 小狼 莓玲 千春 唬爛王山琦]
    myQueue.En("利佳")
    fmt.Println(myQueue.ToSlice())  // [小櫻 知世 桃矢 小狼 莓玲 千春 唬爛王山琦 利佳]
    myQueue.En("寺田老師")
    fmt.Println(myQueue.ToSlice())  // [小櫻 知世 桃矢 小狼 莓玲 千春 唬爛王山琦 利佳 寺田老師]
    myQueue.En("觀月老師")
    fmt.Println(myQueue.ToSlice())  // [小櫻 知世 桃矢 小狼 莓玲 千春 唬爛王山琦 利佳 寺田老師 觀月老師]
    myQueue.En("花店阿姨")
    fmt.Println(myQueue.ToSlice())  // [小櫻 知世 桃矢 小狼 莓玲 千春 唬爛王山琦 利佳 寺田老師 觀月老師 花店阿姨]
    fmt.Println(myQueue.De())       // 小櫻
    fmt.Println(myQueue.De())       // 知世
    fmt.Println(myQueue.De())       // 桃矢
    fmt.Println(myQueue.De())       // 小狼
    fmt.Println(myQueue.De())       // 莓玲
    fmt.Println(myQueue.De())       // 千春
    fmt.Println(myQueue.ToSlice())  // [唬爛王山琦 利佳 寺田老師 觀月老師 花店阿姨]
    myQueue.En("小可")
    fmt.Println(myQueue.ToSlice())  // [唬爛王山琦 利佳 寺田老師 觀月老師 花店阿姨 小可]
    myQueue.En("雪兔")
    fmt.Println(myQueue.ToSlice())  // [唬爛王山琦 利佳 寺田老師 觀月老師 花店阿姨 小可 雪兔]
    fmt.Println(myQueue.De())       // 唬爛王山琦
    fmt.Println(myQueue.De())       // 利佳
    fmt.Println(myQueue.De())       // 寺田老師
    fmt.Println(myQueue.De())       // 觀月老師
    fmt.Println(myQueue.De())       // 花店阿姨
    fmt.Println(myQueue.ToSlice())  // [小可 雪兔]
    fmt.Println(myQueue.De())       // 小可
    fmt.Println(myQueue.De())       // 雪兔
    fmt.Println(myQueue.De())       // <nil>
}