数据结构-队列

队列（queue）是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开

基于链表的队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package queue

import "container/list"

type linkedQueue struct {
	data *list.List
}

func NewLinkedQueue() *linkedQueue {
	return &linkedQueue{
		data: list.New(),
	}
}
func (q linkedQueue) push(value int) {
	q.data.PushBack(value)
}
func (q linkedQueue) pop(value int) any {
	if q.isEmpty() {
		return nil
	}
	e := q.data.Front()
	q.data.Remove(e)
	return e.Value
}
func (q linkedQueue) peek(value int) any {
	if q.isEmpty() {
		return nil
	}
	return q.data.Front().Value
}
func (q linkedQueue) isEmpty() bool {
	return q.data.Len() == 0
}

/* 获取 List 用于打印 */
func (s *linkedQueue) toList() *list.List {
	return s.data
}

基于数组的队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
package queue

// ArrayQueue : 基于环形数组实现的队列
type ArrayQueue struct {
	nums        []int // 用于存储队列元素的数组
	front       int   // 队首指针，指向队首元素
	queSize     int   // 队列长度
	queCapacity int   // 队列容量（即最大容纳元素数量）
}

func NewArrayQueue(queCapacity int) *ArrayQueue {
	return &ArrayQueue{nums: make([]int, queCapacity),
		queCapacity: queCapacity,
		front:       0,
		queSize:     0}
}

/* 获取队列的长度 */
func (q *ArrayQueue) size() int {
	return q.queSize
}

/* 判断队列是否为空 */
func (q *ArrayQueue) isEmpty() bool {
	return q.queSize == 0
}

/* 入队 */
func (q *ArrayQueue) push(num int) {
	// 当 rear == queCapacity 表示队列已满
	if q.queSize == q.queCapacity {
		return
	}
	// 计算队尾指针，指向队尾索引 + 1
	// 通过取余操作实现 rear 越过数组尾部后回到头部
	rear := (q.front + q.queSize) % q.queCapacity
	// 将 num 添加至队尾
	q.nums[rear] = num
	q.queSize++
}

/* 出队 */
func (q *ArrayQueue) pop() any {
	num := q.peek()
	// 队首指针向后移动一位，若越过尾部，则返回到数组头部
	q.front = (q.front + 1) % q.queCapacity
	q.queSize--
	return num
}

/* 访问队首元素 */
func (q *ArrayQueue) peek() any {
	if q.isEmpty() {
		return nil
	}
	return q.nums[q.front]
}

/* 获取 Slice 用于打印 */
func (q *ArrayQueue) toSlice() []int {
	rear := (q.front + q.queSize)
	if rear >= q.queCapacity {
		rear %= q.queCapacity
		return append(q.nums[q.front:], q.nums[:rear]...)
	}
	return q.nums[q.front:rear]
}
package queue

// ArrayQueue : 基于环形数组实现的队列
type ArrayQueue struct {
	nums        []int // 用于存储队列元素的数组
	front       int   // 队首指针，指向队首元素
	queSize     int   // 队列长度
	queCapacity int   // 队列容量（即最大容纳元素数量）
}

func NewArrayQueue(queCapacity int) *ArrayQueue {
	return &ArrayQueue{nums: make([]int, queCapacity),
		queCapacity: queCapacity,
		front:       0,
		queSize:     0}
}

/* 获取队列的长度 */
func (q *ArrayQueue) size() int {
	return q.queSize
}

/* 判断队列是否为空 */
func (q *ArrayQueue) isEmpty() bool {
	return q.queSize == 0
}

/* 入队 */
func (q *ArrayQueue) push(num int) {
	// 当 rear == queCapacity 表示队列已满
	if q.queSize == q.queCapacity {
		return
	}
	// 计算队尾指针，指向队尾索引 + 1
	// 通过取余操作实现 rear 越过数组尾部后回到头部
	rear := (q.front + q.queSize) % q.queCapacity
	// 将 num 添加至队尾
	q.nums[rear] = num
	q.queSize++
}

/* 出队 */
func (q *ArrayQueue) pop() any {
	num := q.peek()
	// 队首指针向后移动一位，若越过尾部，则返回到数组头部
	q.front = (q.front + 1) % q.queCapacity
	q.queSize--
	return num
}

/* 访问队首元素 */
func (q *ArrayQueue) peek() any {
	if q.isEmpty() {
		return nil
	}
	return q.nums[q.front]
}

/* 获取 Slice 用于打印 */
func (q *ArrayQueue) toSlice() []int {
	rear := (q.front + q.queSize)
	if rear >= q.queCapacity {
		rear %= q.queCapacity
		return append(q.nums[q.front:], q.nums[:rear]...)
	}
	return q.nums[q.front:rear]
}

Ref