队列
队列是一种遵循先入先出规则的线性数据结构，顾名思义，队列模拟了排队现象，即新来的人不断加入队列末尾，而位于队列头部的人逐个离开。
队列操作
队列的常用操作
- push()，元素入队，即将元素添加至队尾，时间复杂度O(1)
- pop(), 队首元素出队，时间复杂度O(1)
- peek(), 访问队首元素，时间复杂度O(1)
func main(){
queue := list.New()
queue.PushBack(1)
queue.PushBack(2)
queue.PushBack(3)
// 访问队首元素
front := queue.Front()
fmt.Println(front.Value)
// 队首元素出队
queue.Remove(front)
front = queue.Front()
fmt.Println(front.Value)
queue.Remove(front)
front = queue.Front()
fmt.Println(front.Value)
queue.Remove(front)
size := queue.Len()
fmt.Println(size)
isEmpty := queue.Len() == 0
fmt.Println(isEmpty)
}
队列实现
1. 基于链表的实现
我们可以将链表的头节点和尾节点分别视为队列的首和尾，规定队尾只能添加节点，队首只能删除节点。
import "container/list"
type LinkedListQueue struct {
*list.List
}
func NewLinkedListQueue() *LinkedListQueue {
return &LinkedListQueue{list.New()}
}
// 入队
func (q *LinkedListQueue) Push(element interface{}) {
q.List.PushBack(element)
}
// 出队
func (q *LinkedListQueue) Pop() interface{} {
if q.IsEmpty() {
return nil
}
e := q.List.Front()
q.List.Remove(e)
return e.Value
}
// 访问队首元素
func (q *LinkedListQueue) Peek() interface{} {
if q.IsEmpty() {
return nil
}
e := q.List.Front()
return e.Value
}
// 队列长度
func (q *LinkedListQueue) Size() int {
return q.List.Len()
}
func (q *LinkedListQueue) IsEmpty() bool {
return q.List.Len() == 0
}
2. 基于数组的实现
在数组中删除首元素的时间复杂度为O(n)，这会导致出队操作效率低。我们可以采用以下技巧来避免这个问题。
使用一个变量front指向队首元素的索引，并维护一个size变量记录队列的长度。定义 rear = front + size, 这个公式计算出的rear指向队尾元素的下一个位置。至此，队首元素和队尾元素的位置我们都能在O(1)时间复杂度内确认。
基于此设计，数组中包含元素的区间为[front, rear - 1],
- 入队操作：将输入元素赋值给索引rear索引处，并将长度size增加1.
- 出队操作：将front加1，并将size减1
这样做的好处就是，出队时，不需要删除队首元素，只需改变队首的指针，而原队首的元素值会被后续入队的元素覆盖。可以想象成一个环形数组首尾相连。
/* 基于环形数组实现的队列 */
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()
if num == nil {
return nil
}
// 队首指针向后移动一位，若越过尾部，则返回到数组头部
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]
}
以上队列实现仍然有局限性，队列长度固定；为此我们需要使用动态数组来解决这个问题。
/* 初始化队列 */
func newArrayQueue() *arrayQueue {
return &arrayQueue{
queCapacity: 0,
front: 0,
queSize: 0,
}
}
/* 入队 */
func (q *arrayQueue) push(num int) {
// 队列为空，则扩容为1
if q.queCapacity == 0 {
q.nums = make([]int, 1)
q.queCapacity = 1
}
// 当 rear == queCapacity 表示队列已满,此时需要扩容
if q.queSize == q.queCapacity {
// 增加1倍容量
enlargeNum := make([]int, q.queCapacity)
// 添加到原队列
q.nums = append(q.nums, enlargeNum...)
q.queCapacity = 2 * q.queCapacity
}
// 计算队尾指针，指向队尾索引 + 1
rear := (q.front + q.queSize)
// 将 num 添加至队尾
q.nums[rear] = num
q.queSize++
}
/* 出队 */
func (q *arrayQueue) pop() any {
num := q.peek()
if num == nil {
return nil
}
q.front = (q.front + 1)
q.queSize--
return num
}
在此实现方式中，队列元素不会超出，也就不需要通过求余重置队首的索引，但是元素出栈时，并不是真正从数组移除，只是改变了队首指针的位置，所以必定会造成空间浪费，但是时间复杂度仍然是O(1)。
对比两种方式，各有利弊，当然这里只是模拟实现，真正实现可能还需要考虑更多的问题。
队列应用
- 淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。
- 各类待办事项。任何需要实现“先来后到”功能的场景，例如打印机的任务队列、餐厅的出餐队列等，队列在这些场景中可以有效地维护处理顺序。
网友评论