LeetCode 622. 设计循环队列

Categories:

题目描述
思路分析
1. 解法一：数组 + 头尾指针（推荐）
相似题目

题目描述

✅ 622. 设计循环队列

思路分析

解法一：数组 + 头尾指针（推荐）

核心思路：

使用固定大小数组存储队列元素，用 head 指针指向队首元素，tail 指针指向队尾元素的下一个位置，用 size 记录当前元素数量。

入队时，将元素写入 tail 位置，然后 tail = (tail + 1) % capacity，size++。

出队时，head = (head + 1) % capacity，size--。

判空：size == 0；判满：size == capacity。

取队首：queue[head]；取队尾：queue[(tail - 1 + capacity) % capacity]。

复杂度分析：

时间复杂度：O(1)，所有操作（入队、出队、查首、查尾）均为常数时间。

空间复杂度：O(k)，其中 k 为队列容量，申请固定大小数组存储元素。

class MyCircularQueue {

    private final int[] queue;
    private final int capacity;
    // 队首指针，指向队首元素
    private int head;
    // 队尾指针，指向下一个写入位置
    private int tail;
    // 当前队列中的元素数量
    private int size;

    public MyCircularQueue(int k) {
        capacity = k;
        queue = new int[k];
        head = 0;
        tail = 0;
        size = 0;
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        // 在 tail 位置写入元素，然后移动 tail 指针
        queue[tail] = value;
        tail = (tail + 1) % capacity;
        size++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        // 移动 head 指针，相当于删除队首元素
        head = (head + 1) % capacity;
        size--;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return queue[head];
    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        // tail 指向下一个写入位置，故队尾元素在 (tail-1+capacity)%capacity
        return queue[(tail - 1 + capacity) % capacity];
    }

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

    public boolean isFull() {
        return size == capacity;
    }
}

type MyCircularQueue struct {
    queue    []int
    capacity int
    // 队首指针，指向队首元素
    head int
    // 队尾指针，指向下一个写入位置
    tail int
    // 当前队列中的元素数量
    size int
}

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

func (q *MyCircularQueue) EnQueue(value int) bool {
    if q.IsFull() {
        return false
    }
    // 在 tail 位置写入元素，然后移动 tail 指针
    q.queue[q.tail] = value
    q.tail = (q.tail + 1) % q.capacity
    q.size++
    return true
}

func (q *MyCircularQueue) DeQueue() bool {
    if q.IsEmpty() {
        return false
    }
    // 移动 head 指针，相当于删除队首元素
    q.head = (q.head + 1) % q.capacity
    q.size--
    return true
}

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

func (q *MyCircularQueue) Rear() int {
    if q.IsEmpty() {
        return -1
    }
    // tail 指向下一个写入位置，故队尾元素在 (tail-1+capacity)%capacity
    return q.queue[(q.tail-1+q.capacity)%q.capacity]
}

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

func (q *MyCircularQueue) IsFull() bool {
    return q.size == q.capacity
}

相似题目

题目	难度	考察点
641. 设计循环双端队列	中等	数组、双端队列设计
1670. 设计前中后队列	中等	队列设计、双端队列
232. 用栈实现队列	简单	栈、队列
225. 用队列实现栈	简单	栈、队列
933. 最近的请求次数	简单	队列、滑动窗口
346. 数据流中的移动平均值	简单	队列、滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/47057313