C / C++ / 系统课时
用数组实现一个顺序栈
用数组实现一个顺序栈
顺序栈把一段连续数组当作存储区,再用 top 记录当前栈顶元素的位置。只要把入栈、出栈和读栈顶都约束为只操作数组的一端,就能得到固定容量、操作时间稳定且容易调试的栈实现。
学习目标
- 用数组与
top下标表示顺序栈,并判断栈空、栈满状态 - 正确实现入栈、出栈和读取栈顶,避免数组越界
- 理解顺序栈的时间复杂度、容量限制与适用场景
用数组和 top 表示栈
设数组容量为 CAPACITY,约定 top 保存“当前栈顶元素的数组下标”。初始化时栈里没有元素,因此令 top = -1。第一次入栈后 top 变为 0,元素写入 data[0]。
这个约定会直接给出两个边界条件:top == -1 表示栈空,top == CAPACITY - 1 表示栈满。注意 top 不是元素个数;当 top == 2 时,栈内实际有 3 个元素。
入栈时必须先检查是否已满,再把 top 增加 1 后写入数组;出栈时先读取 data[top],再把 top 减少 1。读取栈顶只读不改,因此不会改变 top。
完整实现
下面实现一个保存 int 的顺序栈。push、pop 和 peek 都通过返回 bool 表示操作是否成功,调用方不用依赖特殊整数作为错误码。
#include <stdbool.h>
#include <stdio.h>
#define CAPACITY 4
typedef struct {
int data[CAPACITY];
int top;
} ArrayStack;
void stack_init(ArrayStack *stack) {
stack->top = -1;
}
bool stack_is_empty(const ArrayStack *stack) {
return stack->top == -1;
}
bool stack_is_full(const ArrayStack *stack) {
return stack->top == CAPACITY - 1;
}
bool stack_push(ArrayStack *stack, int value) {
if (stack_is_full(stack)) {
return false;
}
// 先移动栈顶下标,再写入新的栈顶元素。
stack->top++;
stack->data[stack->top] = value;
return true;
}
bool stack_pop(ArrayStack *stack, int *out_value) {
if (stack_is_empty(stack)) {
return false;
}
// 先取出当前栈顶,再缩小有效区间。
*out_value = stack->data[stack->top];
stack->top--;
return true;
}
bool stack_peek(const ArrayStack *stack, int *out_value) {
if (stack_is_empty(stack)) {
return false;
}
*out_value = stack->data[stack->top];
return true;
}
int main(void) {
ArrayStack stack;
int value;
stack_init(&stack);
stack_push(&stack, 10);
stack_push(&stack, 20);
stack_push(&stack, 30);
if (stack_peek(&stack, &value)) {
printf("top=%d\n", value);
}
while (stack_pop(&stack, &value)) {
printf("pop=%d\n", value);
}
if (!stack_pop(&stack, &value)) {
printf("stack is empty\n");
}
return 0;
}预期输出
top=30
pop=30
pop=20
pop=10
stack is emptypeek 输出 30 后,随后的第一次 pop 仍然得到 30,说明读取栈顶没有删除元素。连续出栈的顺序与入栈相反,体现了后进先出。
边界条件必须先判断
顺序栈最危险的错误不是逻辑顺序,而是越界。若栈已满仍执行 top++ 并写数组,会访问 data[CAPACITY];若栈空仍读取 data[top],则会访问负下标对应的非法位置。
还要避免把“修改 top”和“读取元素”的先后顺序写反。例如出栈如果先执行 top-- 再读 data[top],就会跳过原来的栈顶元素。因此可以把规则记成:入栈先扩范围再写,出栈先读再缩范围。
复杂度与使用场景
顺序栈的 push、pop、peek 都只涉及常数次下标运算,因此时间复杂度都是 。数组在结构体中一次性分配,空间复杂度为 ,不会随着实际元素数量自动缩小。
当容量上限明确、希望减少动态内存分配、重视缓存局部性时,顺序栈很合适,例如表达式求值中的临时操作数栈、深度有限的状态回退或嵌入式程序中的固定工作区。若元素数量上限难以预估,则固定数组可能过早耗尽容量,此时更适合动态扩容数组或链式栈。