1定義

所有代碼以及測試代碼見 : https://gitee.com/babyb/data_srtuct/tree/master/006queue
通過執(zhí)行 go test -v 命令 即可查看測試結(jié)果

隊(duì)列的定義: 只允許在一端進(jìn)行插入操作, 而在另一端進(jìn)行彈出操作的線性表
先進(jìn)先出 First In First Out 簡稱FIFO , 允許插入的一端稱為隊(duì)尾, 允許刪除的一端為隊(duì)頭

2 數(shù)據(jù)結(jié)構(gòu)

/*
Object 用于存放任何數(shù)據(jù)
*/
type Object interface{}

/*
Node 隊(duì)列的數(shù)據(jù)
*/
type Node struct {
    data Object
    next *Node
}

/*
Queue 隊(duì)列
*/
type Queue struct {
    head *Node
    tail *Node
}

3 實(shí)現(xiàn)的方法

3.1 隊(duì)列初始化

func InitQueue() Queue {
    q := Queue{}
    q.head = nil
    return q
}

3.2 向鏈?zhǔn)疥?duì)列中插入數(shù)據(jù)

func (q *Queue) Push(d Object) {
    newNode := &Node{
        data: d,
    }
    // 第一種寫法, temp變量作為游標(biāo), 遍歷到最后一個(gè)元素, 缺點(diǎn)是當(dāng)數(shù)據(jù)變大之后, 插入會(huì)變慢
    // temp := q.head
    // for temp.next != nil {
    //  temp = temp.next
    // }
    // temp.next = newNode

    //第二種寫法, Queue 中增加一個(gè)tail 變量, 用于存放最后一個(gè)元素, 判斷
    if q.Empty() {
        //隊(duì)列為空的時(shí)候, 頭和尾都是newNode
        q.head = newNode
        q.tail = newNode
    } else {
        //隊(duì)列不為空時(shí), 直接操作尾元素即可
        q.tail.next = newNode
        q.tail = newNode
    }

}

3.3 判斷鏈表是否為空

func (q *Queue) Empty() bool {
    if q.head == nil {
        return true
    }
    return false
}

3.4 彈出隊(duì)頭元素

func (q *Queue) Pop() (data Object, err error) {
    if q.Empty() {
        fmt.Println("鏈表為空無法繼續(xù)彈出")
        return 0, errors.New("鏈表為空無法繼續(xù)彈出")
    }
    head := q.head
    q.head = head.next
    return head.data, nil
}

3.5 展示隊(duì)列所有內(nèi)容

func (q *Queue) Show() {
    temp := q.head
    for temp != nil {
        fmt.Printf("%v, ", temp.data)
        temp = temp.next
    }
    fmt.Println("展示完所有內(nèi)容")
}

4 測試代碼

package queue

import (
    "fmt"
    "testing"
)

func Test(t *testing.T) {
    fmt.Println("隊(duì)列測試")
    queue := InitQueue()
    empty := queue.Empty()
    fmt.Println("隊(duì)列是否為空", empty)
    // queue.Push("小明")
    // queue.Push("小紅")
    // queue.Push("小花")
    // queue.Show()

    queue.Push("小明")
    queue.Push("小紅")
    a1, err := queue.Pop()

    fmt.Println("a1 : ", a1, "錯(cuò)誤是,", err)

    a2, err := queue.Pop()
    fmt.Println("a2 : ", a2, "錯(cuò)誤是,", err)

    a3, err := queue.Pop()
    fmt.Println("a3 : ", a3, "錯(cuò)誤是,", err)
}