go语言队列的链式表示和实现

1、链队的定义

• 队列(Queue)是一种先进先出的线性表，在表一段插入(表尾)，在另一端(表头)删除。
  • 队头(Front)，即表尾端
  • 队尾(Rear)，即表头端
  • FIFO(First In First Out)，即队列的操作具有先进先出的特性。
  • 与栈相同，队列也是限定插入和删除只能在表的"端点"进行的线性表，故栈和队列是线性表的子集(是插入和删除位置受限的线性表)。
• 链队列的操作与链表、链栈类似，当用户无法估计所用队列的长度，宜采用链队列。本文只给出以下操作的go语言实现。
  • 初始化
  • 入队
  • 出队

2、链队的初始化

//链式队列的数据结构
type queueNode struct {
    data interface{} // 存放数据
    next *queueNode // 存放指针
}

type queueList struct {
    length int //存储链表长度
    front *queueNode // 指向队头
    rear *queueNode // 指向队尾
}

//链队初始化
func initQueue() *queueList {
    L := &queueList{
        length: 0,
        front: nil,
        rear: nil,
    }
    return L
}

3、入队

//链队的入队
func (queue *queueList) push(val interface{}) {
    node := &queueNode{
        data: val,
        next: nil,
    }

    //处理空队
    if queue.isNull() {
        queue.front = node // 指向队头
        queue.rear = node
        queue.length ++
        return
    }

    queue.rear.next = node
    queue.rear = queue.rear.next
    queue.length ++
}

4、出队

//链队的出队
func (queue *queueList) pop() {
    // 判断队空
    if queue.isNull() {
        fmt.Println("队列为空")
        return
    }

    // 处理链队中只有一个结点的特殊情况
    if queue.length == 1 {
        queue.front = nil
        queue.rear = nil
        queue.length --
        return
    }

    queue.front = queue.front.next
    queue.length --
}

5、完整代码及结果演示

package main

import (
    "fmt"
)

//链式队列的数据结构
type queueNode struct {
    data interface{} // 存放数据
    next *queueNode // 存放指针
}

type queueList struct {
    length int //存储链表长度
    front *queueNode // 指向队头
    rear *queueNode // 指向队尾
}

//链队初始化
func initQueue() *queueList {
    L := &queueList{
        length: 0,
        front: nil,
        rear: nil,
    }
    return L
}

//链队的入队
func (queue *queueList) push(val interface{}) {
    node := &queueNode{
        data: val,
        next: nil,
    }

    //处理空队
    if queue.isNull() {
        queue.front = node // 指向队头
        queue.rear = node
        queue.length ++
        return
    }

    queue.rear.next = node
    queue.rear = queue.rear.next
    queue.length ++
}


//链队的出队
func (queue *queueList) pop() {
    // 判断队空
    if queue.isNull() {
        fmt.Println("队列为空")
        return
    }

    // 处理链队中只有一个结点的特殊情况
    if queue.length == 1 {
        queue.front = nil
        queue.rear = nil
        queue.length --
        return
    }

    queue.front = queue.front.next
    queue.length --
}

//判断队空
func (queue queueList) isNull() bool {
    return queue.length == 0
}


func (queue *queueList) Traverse() (arr []interface{}) {
    pre := queue.front
    for i := 0; i < queue.length; i++ {
        arr = append(arr, pre.data, "-->")
        pre = pre.next
    }
    return
}

func main() {
    data := []interface{}{
        "bala",
        12,
        33,
    }
    L := initQueue()
    for i := range data {
        L.push(data[i])
        fmt.Println(L.Traverse())
    }
    fmt.Println(L)
    L.pop()
    fmt.Println(L.Traverse())
    L.pop()
    fmt.Println(L.Traverse())
    L.pop()
    fmt.Println(L.Traverse())
    L.pop()
}

//输出
[bala -->]
[bala --> 12 -->]
[bala --> 12 --> 33 -->]
&{3 0xc0000044c0 0xc0000045a0}
[12 --> 33 -->]
[33 -->]
[]
队列为空

6、总结

在go语言中，现在能想到的队列相关应用是管道Channel的设计原理。
Channel 的收发操作均遵循了与队列类似的先进先出(FIFO)的设计，具体规则如下：

• 先从 Channel 读取数据的 Goroutine 会先接收到数据；
• 先向 Channel 发送数据的 Goroutine 会得到先发送数据的权利；

参考博客
Go 语言设计与实现

有疑问加站长微信联系（非本文作者）