队列

队列

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

队列操作

队列的常用操作

• 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)。
对比两种方式，各有利弊，当然这里只是模拟实现，真正实现可能还需要考虑更多的问题。

队列应用

• 淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。
• 各类待办事项。任何需要实现“先来后到”功能的场景，例如打印机的任务队列、餐厅的出餐队列等，队列在这些场景中可以有效地维护处理顺序。