题目概览
范围
| 来源 | 内容 |
|---|---|
class013 | QueueStackAndCircularQueue |
题型归纳
题型： 基础数据结构实现
适用条件： 需要自己实现队列、栈、循环队列，或者题目要求在固定数组空间内完成入队、出队、取队头、取队尾等操作。
解法： 队列用数组配合左右边界 l、r，栈用数组配合 size，循环队列额外维护当前元素个数 size 和容量 limit。
易错点： 队列的有效范围是 [l, r)，栈顶位置是 size - 1，循环队列的 r 指向下一个可写位置，取尾元素时要处理 r == 0 的回绕。
看到”固定数组空间内实现队列或栈”就是这类题的信号——数组队列用
[l, r)半开区间管理有效范围，数组栈用size同时表示元素个数和下一个写入位置。循环队列的核心是让r到达末尾后回绕到0，并用独立的size区分空和满；最容易出错的是Rear()直接返回queue[r]——r是下一个可写位置，真正的队尾在r的前一个位置，且要处理r == 0时回绕到limit - 1的情况。
基础结构
队列
队列是先进先出结构，常见操作如下：
| 操作 | 含义 |
|---|---|
offer | 从尾部加入元素 |
poll | 从头部弹出元素 |
peek / head | 查看头部元素但不弹出 |
tail | 查看尾部元素 |
size | 返回当前元素数量 |
栈
栈是后进先出结构，常见操作如下：
| 操作 | 含义 |
|---|---|
push | 压入栈顶 |
pop | 弹出栈顶 |
peek | 查看栈顶但不弹出 |
size | 返回当前元素数量 |
队列实现
Java 内部实现
如果直接使用 Java 内置结构，可以用 LinkedList 当队列。
public static class Queue1 {
public Queue<Integer> queue = new LinkedList<>();
public boolean isEmpty() { return queue.isEmpty(); }
public void offer(int num) { queue.offer(num); }
public int poll() { return queue.poll(); }
public int peek() { return queue.peek(); }
public int size() { return queue.size(); }
}这种写法好处是简单，坏处是 LinkedList 内部是双向链表，常数时间不如数组实现。
数组队列
刷题时更常见的写法是提前准备一个数组，用 l 和 r 表示队列范围：
[l, r)也就是：
l指向当前队头。r指向下一个可写入的位置。- 队列为空时，
l == r。 - 当前元素个数是
r - l。
核心模板如下：
public static class Queue2 {
public int[] queue; public int l; public int r;
public Queue2(int n) { queue = new int[n]; l = 0; r = 0; }
public boolean isEmpty() { return l == r; }
public void offer(int num) { queue[r++] = num; }
public int poll() { return queue[l++]; }
public int head() { return queue[l]; }
public int tail() { return queue[r - 1]; }
public int size() { return r - l; }
}指针角色
| 变量 | 作用 |
|---|---|
queue | 保存队列元素的数组 |
l | 队头位置，弹出时向右移动 |
r | 下一个可写位置，加入时向右移动 |
例如依次加入 3, 5, 7 后：
queue = [3, 5, 7, ...]l = 0r = 3有效范围 = [0, 3)弹出一次后：
l = 1r = 3有效范围 = [1, 3)队头 = queue[1]队尾 = queue[2]这种普通数组队列适合能确定加入操作总次数不超过 n 的场景。即使中间有弹出，l 之前的空间也不会复用。
栈实现
Java 内部实现
可以直接使用 Java 的 Stack：
public static class Stack1 {
public Stack<Integer> stack = new Stack<>();
public boolean isEmpty() { return stack.isEmpty(); }
public void push(int num) { stack.push(num); }
public int pop() { return stack.pop(); }
public int peek() { return stack.peek(); }
public int size() { return stack.size(); }
}这种写法也很方便，但刷题时如果数据范围明确，数组栈通常更直接。
数组栈
数组实现栈只需要一个 size。
public static class Stack2 {
public int[] stack; public int size;
public Stack2(int n) { stack = new int[n]; size = 0; }
public boolean isEmpty() { return size == 0; }
public void push(int num) { stack[size++] = num; }
public int pop() { return stack[--size]; }
public int peek() { return stack[size - 1]; }
public int size() { return size; }
}size 有两层含义：
- 当前栈里有几个元素。
- 下一个新元素应该写到哪个位置。
所以入栈是 stack[size++] = num，出栈是 return stack[--size]——栈顶元素永远在 size - 1 位置，弹出前要先让 size 回到栈顶下标。
例题：622. 设计循环队列
题意
设计一个循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则，并且队尾被连接在队首之后形成一个循环。它也被称为”环形缓冲器”。
循环队列的好处是可以利用队列之前用过的空间。普通队列一旦队尾走到数组末尾，就不能继续插入下一个元素，即使前面因为出队操作空出了位置。循环队列则可以让队尾回到数组开头，继续使用这些空位。
需要实现 MyCircularQueue 类：
MyCircularQueue(k)构造器，设置队列长度为k。Front()从队首获取元素，如果队列为空，返回-1。Rear()获取队尾元素，如果队列为空，返回-1。enQueue(value)向循环队列插入一个元素，如果成功插入则返回true。deQueue()从循环队列中删除一个元素，如果成功删除则返回true。isEmpty()检查循环队列是否为空。isFull()检查循环队列是否已满。
示例
创建一个容量为 3 的循环队列：
MyCircularQueue circularQueue = new MyCircularQueue(3);| 步骤 | 操作 | 返回值 | 队列内容 |
|---|---|---|---|
| 1 | enQueue(1) | true | [1] |
| 2 | enQueue(2) | true | [1, 2] |
| 3 | enQueue(3) | true | [1, 2, 3] |
| 4 | enQueue(4) | false | [1, 2, 3]，队列已满 |
| 5 | Rear() | 3 | 队尾是 3 |
| 6 | isFull() | true | 当前容量已满 |
| 7 | deQueue() | true | [2, 3] |
| 8 | enQueue(4) | true | [2, 3, 4] |
| 9 | Rear() | 4 | 队尾是 4 |
LeetCode 调用格式平台上的原始输入会写成方法名数组和参数数组，输出则是每一步调用的返回值：
提示
- 所有的值都在
0至1000的范围内 - 操作数将在
1至1000的范围内 - 请不要使用内置的队列库
解法
核心思路
普通数组队列的问题是：弹出后，前面的空间不会再使用。循环队列要解决的就是这个问题：当 r 走到数组最后一个位置后，如果前面有空位，就让 r 回到 0 继续写。
关键在于：循环数组里 l == r 既可能表示空，也可能表示满。额外维护 size 后，size == 0 表示空，size == limit 表示满，判断就变得非常清楚。
普通队列的
l之前是”死空间”，循环队列让r回绕到数组开头，把死空间变成可复用空间——代价是需要一个独立的size来区分空和满。
核心模板
class MyCircularQueue {
public int[] queue;
public int l, r, size, limit;
public MyCircularQueue(int k) { queue = new int[k]; l = r = size = 0; limit = k; }
public boolean enQueue(int value) { if (isFull()) { return false; } else { queue[r] = value; r = r == limit - 1 ? 0 : (r + 1); size++; return true; } }
public boolean deQueue() { if (isEmpty()) { return false; } else { l = l == limit - 1 ? 0 : (l + 1); size--; return true; } }
public int Front() { if (isEmpty()) { return -1; } else { return queue[l]; } }
public int Rear() { if (isEmpty()) { return -1; } else { int last = r == 0 ? (limit - 1) : (r - 1); return queue[last]; } }
public boolean isEmpty() { return size == 0; }
public boolean isFull() { return size == limit; }
}变量角色
queue 是固定长度的底层数组；l 指向当前队头位置；r 指向下一个可写位置，入队后向右移动并在末尾回绕到 0；size 记录当前队列里的元素个数，用来区分空和满；limit 是队列容量，即数组长度。
过程拆解
- 入队：先判满，没满则把值写到
r位置，移动r（到末尾回绕），size++。 - 出队：先判空，不空则移动
l（到末尾回绕），size--。不需要清空旧值，边界变量决定有效数据。 - 取队头：直接返回
queue[l]。 - 取队尾：
r是下一个可写位置，真正的队尾在r的前一个位置。r == 0时回绕到limit - 1，否则就是r - 1。 - 判空判满：
size == 0为空，size == limit为满。
易错点
- 入队成功后移动
r并且size++，出队成功后移动l并且size--，两步缺一不可。 - 数组里的旧值不用清理，边界变量才决定当前有效数据。
enQueue()只写queue[r++]错误写法：
为什么错：循环队列的
r到达数组最后一个位置后，不能继续++到limit，而是要回绕到0。正确写法：
deQueue()只改size，不移动l错误写法：
为什么错：出队删除的是当前队头，成功出队后必须让
l移到下一个位置。数组里的旧值不用清理，但队头边界必须更新。正确写法：
Rear()直接返回queue[r]错误写法：
为什么错：
r指向的是下一个将要写入的位置，不是最后一个已写入的位置。如果r == 0，实际队尾在queue[limit - 1]；否则队尾在queue[r - 1]。正确写法：
用l == r判断空或满错误写法：
为什么错：在循环数组中，队列从空开始入队直到满，
l和r会再次相遇。仅靠l == r无法区分这两种状态。正确写法：用独立的
size变量区分：
口诀
l指队头，r指下一个可写位置，size决定空和满，到末尾就回绕。
复杂度
- 队列、栈、循环队列的每个操作时间复杂度都是
O(1)。 - 数组队列和数组栈的空间复杂度是
O(n)。 - 循环队列的空间复杂度是
O(k)，k是初始化时给定的容量。
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时