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 语言设计与实现
