手写栈与队列

约定 top 指向下一个空位,栈里现有 top 个元素。push 就是 st[top++] = x,栈顶永远是 st[top - 1],pop 就是一句 top--。妙处在于:被弹掉的数其实还留在数组里,只是 top 不再罩着它,它就不属于栈了——连删除都不用做。

队列两端都要动,所以用两个下标:tail 管入队(尾进),head 管出队(头出)。入队 q[tail++] = x,看队头 q[head],出队 head++,元素个数是 tail - head。出队不要把整个数组往前挪——挪是 O(n),移一下 head 是 O(1)。两个下标只增不减,空间走过不回头,按上限开够就行。

栈是后进先出:括号匹配、表达式、DFS——最近打开的要最先闭合,正是栈的顺序。队列是先进先出:BFS、按到达顺序处理。所有操作都是 O(1),BFS 的循环条件 while (head < tail) 就是队列判空的直接应用。