队列

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

queue

我们将队列头部称为“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”。

常见操作

队列的常见操作如下表所示。在此采用与栈相同的方法命名。

方法名	描述	时间复杂度
`push()`	元素入队，即将元素添加至队尾	$O(1)$
`pop()`	队首元素出队	$O(1)$
`peek()`	访问队首元素	$O(1)$

直接使用编程语言中现成的队列类：

/* 初始化队列 */
// 在 Go 中，将 list 作为队列来使用
queue := list.New()
 
/* 元素入队 */
queue.PushBack(1)
queue.PushBack(3)
queue.PushBack(2)
queue.PushBack(5)
queue.PushBack(4)
 
/* 访问队首元素 */
peek := queue.Front()
 
/* 元素出队 */
pop := queue.Front()
queue.Remove(pop)
 
/* 获取队列的长度 */
size := queue.Len()
 
/* 判断队列是否为空 */
isEmpty := queue.Len() == 0

基于链表实现队列

将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”，规定队尾仅可添加节点，队首仅可删除节点。

/* 基于链表实现的队列 */
type linkedListQueue struct {
    // 使用内置包 list 来实现队列
    data *list.List
}
 
/* 初始化队列 */
func newLinkedListQueue() *linkedListQueue {
    return &linkedListQueue{
        data: list.New(),
    }
}
 
/* 入队 */
func (s *linkedListQueue) push(value any) {
    s.data.PushBack(value)
}
 
/* 出队 */
func (s *linkedListQueue) pop() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Front()
    s.data.Remove(e)
    return e.Value
}
 
/* 访问队首元素 */
func (s *linkedListQueue) peek() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Front()
    return e.Value
}
 
/* 获取队列的长度 */
func (s *linkedListQueue) size() int {
    return s.data.Len()
}
 
/* 判断队列是否为空 */
func (s *linkedListQueue) isEmpty() bool {
    return s.data.Len() == 0
}
 
/* 获取 List 用于打印 */
func (s *linkedListQueue) toList() *list.List {
    return s.data
}

基于数组实现队列

在数组中删除首元素的时间复杂度为 O(n)，为了避免这种情况，采用了下面的方法。

使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义 rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置。

基于此设计，数组中包含元素的有效区间为 [front, rear - 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()
    // 队首指针向后移动一位，若越过尾部，则返回到数组头部
    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]
}

双向队列

双向队列(double-ended queue)提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。

双向队列的常用操作如下表所示。

方法名	描述	时间复杂度
`push_first()`	将元素添加至队首	$O(1)$
`push_last()`	将元素添加至队尾	$O(1)$
`pop_first()`	删除队首元素	$O(1)$
`pop_last()`	删除队尾元素	$O(1)$
`peek_first()`	访问队首元素	$O(1)$
`peek_last()`	访问队尾元素	$O(1)$

直接使用编程语言中现成的双向队列类：

/* 初始化双向队列 */
// 在 Go 中，将 list 作为双向队列使用
deque := list.New()
 
/* 元素入队 */
deque.PushBack(2)      // 添加至队尾
deque.PushBack(5)
deque.PushBack(4)
deque.PushFront(3)     // 添加至队首
deque.PushFront(1)
 
/* 访问元素 */
front := deque.Front() // 队首元素
rear := deque.Back()   // 队尾元素
 
/* 元素出队 */
deque.Remove(front)    // 队首元素出队
deque.Remove(rear)     // 队尾元素出队
 
/* 获取双向队列的长度 */
size := deque.Len()
 
/* 判断双向队列是否为空 */
isEmpty := deque.Len() == 0

队列的应用

淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。
各类待办事项。任何需要实现“先来后到”功能的场景，例如打印机的任务队列、餐厅的出餐队列等，队列在这些场景中可以有效地维护处理顺序。
网络数据包。在计算机网络中，数据包按照先后顺序传输，队列可以很好地模拟这一过程。
广度优先搜索。在图论中，广度优先搜索（BFS）是一种遍历或搜索树、图的算法。它从根节点开始，沿着树的宽度遍历树的节点，直到找到目标节点或者遍历完整棵树。广度优先搜索通常使用队列来实现。

栈(stack)哈希表(hash map)