C / C++ / 系统课时

栈为什么只能操作栈顶

栈为什么只能操作栈顶

栈把数据访问限制在同一个入口:新元素从栈顶加入,删除和查看也只针对栈顶。这个限制并不是存储结构做不到随机访问,而是为了稳定保持“后进入的数据先处理”的顺序,使函数返回、撤销等操作能够直接映射为简单的入栈和出栈。

学习目标

  • 理解栈顶限制与后进先出规则之间的关系
  • 掌握 push、pop 和 peek 三个核心操作
  • 能通过 C 语言数组实现一个最小栈并处理空栈、满栈边界

栈顶限制保证后进先出

假设依次把 10、20、30 放入栈中,30 是最后进入的元素,也位于栈顶。下一次删除时只能先取走 30,然后才轮到 20。这种顺序称为后进先出,即 LIFO。

栈顶执行 push pop peek 的访问关系

如果允许随意从中间删除 20,结构就不再严格保持最后进入者优先离开的规则。数组或链表作为底层存储时当然可能访问中间位置,但那属于底层实现能力,不属于栈这个抽象数据类型对外提供的标准操作。

push、pop 和 peek 各做什么

三个操作都围绕栈顶展开:

操作 行为 是否修改栈
push 把新元素放到栈顶 是
pop 删除并取得当前栈顶元素 是
peek 读取当前栈顶元素 否

对于数组实现,可以用整数 top 记录栈顶下标。约定空栈时 top == -1,那么入栈先增加 top,出栈读取后减少 top,三个操作都不需要移动已有元素。

用数组实现一个最小栈

下面的完整程序实现容量为 4 的整数栈,并显式检查栈满和栈空。这里让操作通过返回 bool 表示成功与否,避免在失败时伪造一个整数作为结果。

c
#include <stdbool.h>
#include <stdio.h>

#define CAPACITY 4

typedef struct {
    int data[CAPACITY];
    int top;
} Stack;

bool push(Stack *stack, int value) {
    if (stack->top == CAPACITY - 1) {
        return false;
    }

    stack->data[++stack->top] = value;
    return true;
}

bool pop(Stack *stack, int *value) {
    if (stack->top == -1) {
        return false;
    }

    *value = stack->data[stack->top--];
    return true;
}

bool peek(const Stack *stack, int *value) {
    if (stack->top == -1) {
        return false;
    }

    *value = stack->data[stack->top];
    return true;
}

int main(void) {
    Stack stack = {{0}, -1};
    int value;

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    if (peek(&stack, &value)) {
        printf("top=%d\n", value);
    }

    if (pop(&stack, &value)) {
        printf("pop=%d\n", value);
    }

    if (peek(&stack, &value)) {
        printf("top=%d\n", value);
    }

    return 0;
}

预期输出

text
top=30
pop=30
top=20

第一次 peek 只读取 30,并没有改变 top;随后 pop 删除 30,新的栈顶才变成 20。

函数调用和撤销为什么适合栈

程序执行函数调用时,新调用通常要先完成,程序才能返回到上一层调用位置。例如 main 调用 A,A 再调用 B,那么 B 必须先返回,随后才轮到 A。这与最后压入的调用现场最先弹出的顺序一致。

撤销操作也有相同特点。用户依次执行三个修改后,第一次撤销通常应恢复第三个修改,第二次撤销再恢复第二个修改。每次只关心最近保存的操作记录,因此无需搜索整个历史记录。

先检查栈空和栈满

pop 和 peek 面对空栈时没有合法的栈顶元素,不能直接访问 data[-1];固定长度数组实现的 push 在栈满时也不能继续增加下标。实际代码必须明确处理这两个边界。

只要所有插入、删除和查看都通过栈顶完成,栈的行为就可以只依赖当前 top 判断,而不需要在元素之间查找位置。这既保持了后进先出的语义,也让数组栈的三个核心操作都能以常数时间完成。

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

目录与阅读设置

阅读设置

17

记录一个想法

栈为什么只能操作栈顶

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

登录哪都通