跳转至

队列

💡 一句话概述

队列是一种先进先出（FIFO）的数据结构，只允许从一端入队、另一端出队。

🔑 核心概念

  1. FIFO 原则：先入队的元素先出队，类似于排队买票
  2. 操作：入队（Enqueue）从队尾添加，出队（Dequeue）从队头移除
  3. 类型：顺序队列、链式队列、循环队列、双端队列

📝 详细说明

队列是一种受限的线性表，限制只在表的两端进行操作：

  • 队头（Front）：允许出队的一端
  • 队尾（Rear）：允许入队的一端

适用场景：任务调度、消息队列、BFS 遍历、缓冲区、打印队列等。

💻 代码示例

顺序队列（数组实现）

package main

import "fmt"

type Queue struct {
    data []int
    head int
    tail int
    size int
}

func NewQueue(capacity int) *Queue {
    return &Queue{
        data: make([]int, capacity),
        head: 0,
        tail: 0,
        size: capacity,
    }
}

func (q *Queue) Enqueue(val int) bool {
    if q.tail == q.size {
        return false // 队满
    }
    q.data[q.tail] = val
    q.tail++
    return true
}

func (q *Queue) Dequeue() (int, bool) {
    if q.head == q.tail {
        return 0, false // 队空
    }
    val := q.data[q.head]
    q.head++
    return val, true
}

func (q *Queue) IsEmpty() bool {
    return q.head == q.tail
}

func main() {
    q := NewQueue(5)
    q.Enqueue(1)
    q.Enqueue(2)
    q.Enqueue(3)

    for !q.IsEmpty() {
        val, _ := q.Dequeue()
        fmt.Println(val) // 输出: 1 2 3
    }
}

链式队列（链表实现）

package main

import "fmt"

type Node struct {
    Val  int
    Next *Node
}

type LinkedQueue struct {
    head *Node
    tail *Node
    size int
}

func NewLinkedQueue() *LinkedQueue {
    return &LinkedQueue{}
}

func (q *LinkedQueue) Enqueue(val int) {
    node := &Node{Val: val}
    if q.tail != nil {
        q.tail.Next = node
    }
    q.tail = node
    if q.head == nil {
        q.head = node
    }
    q.size++
}

func (q *LinkedQueue) Dequeue() (int, bool) {
    if q.head == nil {
        return 0, false
    }
    val := q.head.Val
    q.head = q.head.Next
    if q.head == nil {
        q.tail = nil
    }
    q.size--
    return val, true
}

func main() {
    q := NewLinkedQueue()
    q.Enqueue(10)
    q.Enqueue(20)

    for {
        val, ok := q.Dequeue()
        if !ok {
            break
        }
        fmt.Println(val) // 输出: 10 20
    }
}

循环队列

package main

import "fmt"

type CircularQueue struct {
    data []int
    head int
    tail int
    size int
    cap  int
}

func NewCircularQueue(capacity int) *CircularQueue {
    return &CircularQueue{
        data: make([]int, capacity),
        head: 0,
        tail: 0,
        size: 0,
        cap:  capacity,
    }
}

func (q *CircularQueue) Enqueue(val int) bool {
    if q.size == q.cap {
        return false
    }
    q.data[q.tail] = val
    q.tail = (q.tail + 1) % q.cap
    q.size++
    return true
}

func (q *CircularQueue) Dequeue() (int, bool) {
    if q.size == 0 {
        return 0, false
    }
    val := q.data[q.head]
    q.head = (q.head + 1) % q.cap
    q.size--
    return val, true
}

func main() {
    q := NewCircularQueue(3)
    q.Enqueue(1)
    q.Enqueue(2)
    q.Enqueue(3)

    val, _ := q.Dequeue() // 出队 1
    fmt.Println("出队:", val)

    q.Enqueue(4) // 入队 4

    for !q.IsEmpty() {
        val, _ := q.Dequeue()
        fmt.Println(val) // 输出: 2 3 4
    }
}

⚠️ 常见陷阱

顺序队列的假溢出

用数组实现队列时，即使前面有空位，tail 到达数组末尾也无法入队。解决办法：使用循环队列，通过取模运算让队列"首尾相接"。

队空和队满的判断条件

循环队列中，head == tail 表示队空，(tail + 1) % cap == head 表示队满（牺牲一个位置）。或者额外维护一个 size 变量来区分。

🏋️ 练习题

练习 1：用两个栈实现队列

使用两个栈实现队列的 push 和 pop 操作。

type MyQueue struct {
    inStack  []int
    outStack []int
}

func (q *MyQueue) Push(x int) {
    q.inStack = append(q.inStack, x)
}

func (q *MyQueue) Pop() int {
    if len(q.outStack) == 0 {
        for len(q.inStack) > 0 {
            q.outStack = append(q.outStack, q.inStack[len(q.inStack)-1])
            q.inStack = q.inStack[:len(q.inStack)-1]
        }
    }
    val := q.outStack[len(q.outStack)-1]
    q.outStack = q.outStack[:len(q.outStack)-1]
    return val
}
练习 2：用队列实现 BFS

用队列实现二叉树的层序遍历。

答案 
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    result := [][]int{}
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        level := []int{}
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append(result, level)
    }
    return result
}

🔗 相关链接