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 表示操作是否成功,调用方不用依赖特殊整数作为错误码。

c
#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;
}

预期输出

text
top=30
pop=30
pop=20
pop=10
stack is empty

peek 输出 30 后,随后的第一次 pop 仍然得到 30,说明读取栈顶没有删除元素。连续出栈的顺序与入栈相反,体现了后进先出。

边界条件必须先判断

顺序栈最危险的错误不是逻辑顺序,而是越界。若栈已满仍执行 top++ 并写数组,会访问 data[CAPACITY];若栈空仍读取 data[top],则会访问负下标对应的非法位置。

还要避免把“修改 top”和“读取元素”的先后顺序写反。例如出栈如果先执行 top-- 再读 data[top],就会跳过原来的栈顶元素。因此可以把规则记成:入栈先扩范围再写,出栈先读再缩范围。

复杂度与使用场景

顺序栈的 push、pop、peek 都只涉及常数次下标运算,因此时间复杂度都是 O(1)O(1)。数组在结构体中一次性分配,空间复杂度为 O(CAPACITY)O(CAPACITY),不会随着实际元素数量自动缩小。

当容量上限明确、希望减少动态内存分配、重视缓存局部性时,顺序栈很合适,例如表达式求值中的临时操作数栈、深度有限的状态回退或嵌入式程序中的固定工作区。若元素数量上限难以预估,则固定数组可能过早耗尽容量,此时更适合动态扩容数组或链式栈。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用数组实现一个顺序栈

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通