LeetCode 622. 设计循环队列

约 6 分钟
文章信息 12 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 腾讯 字节 阿里 华为 美团 拼多多 滴滴
标签
数组 链表 设计 队列

题目描述

✅ 622. 设计循环队列

image-20260928221956107

image-20260928221956108

题意分析

实现容量为 k 的先进先出队列，支持入队、出队、读取两端和判断空满。把数组首尾视为相连，下标走过末尾后回到开头，就能复用出队释放的空间，各项操作都无需搬移已有元素。

解法：数组 + 队首下标 + 元素数量

核心思路

[!blue]

用 head 记录队首下标，size 记录有效元素数量，始终满足 0 <= size <= k。从队首起，第 i 个元素的数组下标为 (head + i) % k，其中 i 从 $0$ 到 size - 1。这段环形位置按顺序组成当前队列。

非空时，当前队尾的偏移量是 size - 1，下标为 (head + size - 1) % k；下一次入队的偏移量为 size，下标就是 (head + size) % k。先判满再写入，才能保证新位置不属于仍在队列中的元素。

出队时让 head 向后移动一格并取模，再将 size 减一，剩余元素的先后顺序保持不变。旧队首的值可以留在数组里，因为只有从新 head 开始的 size 个位置有效，后续入队会在需要时覆盖旧值。

size == 0 表示空，size == k 表示满。这两种状态下，按入队公式算出的下标都等于 head，所以要由数量区分空满。容量为 $1$ 时下标始终为 $0$，仍可用 size 正确判断空满。

解题步骤

  1. 构造时申请长度为 k 的数组，令 head = 0、size = 0。
  2. 入队前判满；将值写入 (head + size) % k，再执行 size++。
  3. 出队前判空；令 head = (head + 1) % k，再执行 size--。旧值无需清除，因为有效性只由 head 和 size 决定。
  4. 非空时，队首为 data[head]，队尾为 data[(head + size - 1) % k]；空队列按题意返回 -1。
  5. 判空、判满分别比较 size 与 $0$、k。满时入队、空时出队都返回 false，且不能修改数组或下标、数量。

代码实现

class MyCircularQueue {
    private int[] data;
    private int head;
    private int size;

    public MyCircularQueue(int k) {
        data = new int[k];
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }

        // 当前队首加有效数量得到下一次写入位置，随后按容量回绕。
        int tail = (head + size) % data.length;

        data[tail] = value;
        size++;

        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }

        // 出队只需要移动队首下标，不需要清空数组位置。
        head = (head + 1) % data.length;
        size--;

        return true;
    }

    public int Front() {
        return isEmpty() ? -1 : data[head];
    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        }

        // 队尾是最后一个有效元素，比下一次写入位置少一格。
        return data[(head + size - 1) % data.length];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == data.length;
    }
}

type MyCircularQueue struct {
    data []int
    head int
    size int
}

func Constructor(k int) MyCircularQueue {
    return MyCircularQueue{data: make([]int, k)}
}

func (this *MyCircularQueue) EnQueue(value int) bool {
    if this.IsFull() {
        return false
    }
    // 当前队首加有效数量得到下一次写入位置，随后按容量回绕。
    tail := (this.head + this.size) % len(this.data)
    this.data[tail] = value
    this.size++
    return true
}

func (this *MyCircularQueue) DeQueue() bool {
    if this.IsEmpty() {
        return false
    }
    // head 按容量取模前进，实现循环复用数组。
    this.head = (this.head + 1) % len(this.data)
    this.size--
    return true
}

func (this *MyCircularQueue) Front() int {
    if this.IsEmpty() {
        return -1
    }
    return this.data[this.head]
}

func (this *MyCircularQueue) Rear() int {
    if this.IsEmpty() {
        return -1
    }
    // 队尾是最后一个有效元素，比下一次写入位置少一格。
    return this.data[(this.head+this.size-1)%len(this.data)]
}

func (this *MyCircularQueue) IsEmpty() bool {
    return this.size == 0
}

func (this *MyCircularQueue) IsFull() bool {
    return this.size == len(this.data)
}

复杂度分析

  • 时间复杂度：构造为 $O(k)$，初始化容量数组；后续各项操作为 $O(1)$，不搬移元素。
  • 空间复杂度：$O(k)$，用于保存容量为 k 的定长数组。

关键点总结

[!green]

  • 先定义状态不变量，再由它推导入队位置、队尾位置和空满条件，比背公式可靠。
  • 取模负责回绕，size 负责区分空与满，两者职责不同。
  • head + size 指向下一个写入位置，所以队尾必须再减 1。
  • 出队只改变逻辑边界，不必清除数组中的旧值。

易错点总结

[!yellow]

  • 只用 head == tail 同时判断空和满，两种状态会产生歧义；当前实现由 size 区分。
  • 入队前漏判满会覆盖仍有效的队首元素，并破坏 size <= k。
  • 队尾公式漏掉 -1，读到的是下一个待写位置；公式漏掉 head，绕圈后会读错。
  • 下标前进忘记取模，走过数组末尾就会越界。
  • 空队列调用 Front 或 Rear 必须返回 -1，不能直接读取数组默认值。

相似题目

题目 难度 关联与区别
641. 设计循环双端队列 中等 本题只支持队尾入、队首出，原题循环双端队列还支持两端插入删除。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/47057313
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！