数组如何实现栈和队列？为什么队列常用循环数组？

简化版

数组实现栈很自然，用一个 top 指向栈顶，尾部 push/pop 都是 O(1)。数组实现队列如果每次出队都整体左移，会退化 O(n)，所以常用 head、tail 加循环数组，让入队出队都 O(1)。

详细版

栈只在同一端操作，数组尾部追加和删除很适合。队列一端入、一端出，如果出队后移动所有元素，成本很高。循环数组把底层空间看成首尾相连：

next = (index + 1) % capacity

这样 head 前进表示出队，tail 前进表示入队，不需要搬移元素。面试要说清楚空满判断：可以浪费一个槽，或者维护 size 计数。

完整版教学

一、数组实现栈为什么简单

栈是后进先出，只在栈顶一端操作。数组尾部正好适合做栈顶。

bottom             top
[ 1, 2, 3, _, _ ]

push 时写到 a[top]，然后 top++；pop 时 top--，再取元素。两个操作都不需要移动中间元素。

记忆钩子：栈只动尾巴，数组最喜欢尾部操作。

二、栈的边界是容量和空栈

固定数组实现栈时，要检查满栈和空栈。

void push(int x) {
  if (top == capacity) throw new RuntimeException("full");
  a[top++] = x;
}

int pop() {
  if (top == 0) throw new RuntimeException("empty");
  return a[--top];
}

这里 top 表示下一个可写位置，同时也等于当前元素个数。有效元素区间是 [0, top)。

如果用动态数组实现栈，容量满了可以扩容，尾部 push 均摊 O(1)。

三、普通数组实现队列的问题

队列是先进先出，一端入队，一端出队。

如果每次出队都删除 a[0] 并把后面元素左移：

before: [A, B, C, D]
dequeue A
after:  [B, C, D, _]

一次出队可能移动 n-1 个元素，连续出队就很浪费。数组不是不能做队列，而是不能用“每次左移”的方式做高性能队列。

四、循环数组避免搬移

循环数组用 head 指向队头，tail 指向下一个写入位置。下标走到末尾后，通过取模回到 0。

capacity = 5
next(i) = (i + 1) % 5

index: 0 1 2 3 4
data:  _ B C D _
       ^     ^
     head   tail

出队只让 head = (head + 1) % capacity，入队只让 tail = (tail + 1) % capacity。元素不需要搬家。

五、空和满怎么判断

循环数组最容易混的是 head == tail。它可能表示空，也可能表示满。

常见解决方案有两种。

方案	判断空	判断满	特点
浪费一个槽	`head == tail`	`(tail + 1) % cap == head`	实现简单
维护 size	`size == 0`	`size == cap`	容量利用满

浪费一个槽时，容量为 5 的数组最多放 4 个元素。维护 size 时可以放满，但每次入队出队都要更新 size。

六、扩容时要按逻辑顺序复制

如果循环队列满了并需要扩容，不能直接从底层数组 0 到 n 复制，因为逻辑顺序可能跨过数组末尾。

index: 0 1 2 3 4
data:  D E _ B C
logical order: B C D E

扩容复制要从 head 开始复制 size 个元素：

for (int i = 0; i < size; i++) {
  newArr[i] = oldArr[(head + i) % oldCap];
}
head = 0;
tail = size;

这也是循环数组实现题的高频追问。

七、常见误区与追问

误区：数组不适合实现队列。 数组可以实现队列，关键是用循环数组避免出队搬移。
误区：出队必须把所有元素左移。 移动 head 指针即可，逻辑删除比物理搬移更高效。
误区：head == tail 一定表示空。 如果不额外设计，它也可能表示满，需要浪费槽或维护 size。
追问：数组实现栈为什么是 O(1)？ push/pop 都在尾部，不需要移动其他元素。
追问：循环数组为什么要取模？ 让下标到末尾后回到开头，复用前面释放的空间。
追问：循环队列扩容怎么复制？ 从 head 开始按逻辑顺序复制 size 个元素，再重置 head 和 tail。

八、加强记忆

数组实现栈和队列，关键看操作端。栈只动尾部，数组天然适合；队列如果出队左移会 O(n)，所以要用 head/tail 和循环数组，把物理数组当成环。空满判断用“浪费一个槽”或“维护 size”，扩容时按逻辑顺序复制，而不是按底层下标顺序照搬。

简化版

详细版