栈

真题练习

关于栈直接考查其定义和概念比较少，更多的是考查应用，但是这一节还是 作为基础，需要熟悉下。

定义与基本操作

栈 是一个元素的集合，加入元素的操作叫做 “压栈”（push），而移除元素的操作叫做 “出栈”（pop）。它遵循 后进先出（LIFO, Last In First Out） 的原则。这意味着最后被压入栈的元素是第一个被弹出的元素。

基本操作

• push(element): 将元素添加到 栈 的顶部。
• pop(): 移除并返回 栈顶 的元素。如果 栈 为空，这个操作可能会抛出一个错误或返回特定的值（例如 null 或 undefined），具体取决于实现。
• peek() 或 top(): 返回 栈顶 的元素但不移除它。这只是一个查看操作，栈 的内容不会改变。如果 栈 为空，这个操作可能会抛出一个错误或返回特定的值。
• isEmpty(): 判断 栈 是否为空。如果 栈 为空，返回 true；否则返回 false。
• size() 或 length(): 返回 栈 中元素的数量。

存储实现

栈 的实现方式有两种，顺序栈 和 链式栈。 顺序栈 是在 顺序表 的基础上实现 栈结构， 链式栈 是在 链表 的基础上实现 栈结构。

顺序栈

顺序栈是使用 数组 来实现的 栈，利用数组的索引来模拟 栈 的操作。 与普通的线性表不同，栈 的操作被限制在表的一端进行，这一端被称为 栈顶 (Top)，另一端被称为 栈底 (Bottom)。

顺序栈的关键在于 栈顶指针，栈顶指针是一个整数变量，用于指示 栈顶 元素在 数组 中的位置。其值的变化直接反映了栈中元素的变化。

若约定 top 保存栈顶元素的数组下标，则 栈空 时令 top = -1，栈满 时有 top = MAX_SIZE - 1。也有教材令 top 指向下一个可用位置，此时判空、判满条件会不同；同一道题中必须始终遵守同一约定。

当元素 入栈 时，将栈顶指针 向后 移动一个位置、然后放置新元素即可。当元素 出栈 时，需要将栈顶指针 向前 移动一个位置。

当然，入栈需要保证栈不满，出栈需要保证栈不空。

• 栈的定义
• 初始化
• 入栈
• 出栈
• 获取栈顶元素
• 判断栈空

#define MAX_SIZE 100 // 定义栈的最大容量

// 定义顺序栈的结构
typedef struct {
    int data[MAX_SIZE]; // 使用数组存储数据
    int top;            // 栈顶指针
} SeqStack;

// 初始化栈
SeqStack* initStack() {
    SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack));
    if(!stack) {
        printf("Failed to allocate memory for stack\n");
        exit(1);
    }
    // 栈顶指针初始化为 -1，表示栈为空
    stack->top = -1;
    return stack;
}

// 入栈操作
bool push(SeqStack* stack, int value) {
    if (isFull(stack)) {
        printf("Stack is full!\n");
        return false;
    }
    // 先移动栈顶指针，再存放元素
    stack->data[++stack->top] = value;
    return true;
}

// 出栈操作
bool pop(SeqStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    // 先取出元素，再移动栈顶指针
    *value = stack->data[stack->top--];
    return true;
}

// 获取栈顶元素
bool peek(SeqStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    *value = stack->data[stack->top];
    return true;
}

// 判断栈是否为空
// 当栈中没有元素时，栈顶指针通常指向一个特殊的位置，例如 -1。
bool isEmpty(SeqStack* stack) {
    return stack->top == -1;
}

// 判断栈是否已满
// 当栈顶指针指向数组中的最后一个元素时，说明栈已经满了
bool isFull(SeqStack* stack) {
    return stack->top == MAX_SIZE - 1;
}

顺序栈的不变量与取舍

上述实现采用“top 指向当前栈顶元素”的约定，因此空栈时 top == -1，有效元素恰好位于 data[0..top]。每次成功入栈后，top 增 1 且新元素成为唯一可直接访问的栈顶；每次成功出栈后，原栈顶被返回、top 减 1。这个关系就是栈操作的核心不变量。

顺序栈的入栈、出栈和取栈顶都是 $O(1)$，但容量由数组上界限制。链式栈同样能在 $O(1)$ 时间完成这些操作，且不会出现“数组已满”的上溢；代价是每个结点要存储链接字段，并且结点申请失败也应视为不能入栈。二者都必须先判空再出栈，不能把数组中残留的旧值或已释放结点中的数据当作有效元素。

易错点：若另一份代码约定 top 指向“下一个可用位置”，空栈应为 top == 0，入栈和出栈中的自增/自减顺序也会变化。先读懂指针语义，再判断空满条件。

链式栈

栈的 链式存储结构 利用 单链表 来实现栈的功能。

在 链式栈 实现中，一般 头结点不存放数据，仅作为链表的固定起点。栈顶元素始终为 head->next，入栈和出栈的时间复杂度均为 $O(1)$。

链式栈具备以下 重要特性：

• head 始终存在，不存储实际数据，只作为哨兵节点。

• 栈顶元素 始终位于 head->next。

• 空栈 时，head->next == NULL。

• 入栈时在 head->next 前插入新节点；出栈时删除 head->next。

• 栈的定义

• 初始化

• 入栈

• 出栈

• 获取栈顶元素

• 判断栈空

// 定义链式栈的节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义链式栈（带头结点）
typedef struct {
    Node* head;  // 指向头结点
} LinkedStack;

// 初始化栈（带头结点）
LinkedStack* initStack() {
    LinkedStack* stack = (LinkedStack*)malloc(sizeof(LinkedStack));
    if (!stack) {
        printf("Failed to allocate memory for stack\n");
        exit(1);
    }
    stack->head = (Node*)malloc(sizeof(Node)); // 创建头结点
    if (!stack->head) {
        printf("Failed to allocate memory for head node\n");
        exit(1);
    }
    stack->head->next = NULL; // 初始为空栈
    return stack;
}

// 入栈操作（头插法）
void push(LinkedStack* stack, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Failed to allocate memory for new node\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = stack->head->next;
    stack->head->next = newNode;
}

// 出栈操作
bool pop(LinkedStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    Node* topNode = stack->head->next;
    *value = topNode->data;
    stack->head->next = topNode->next;
    free(topNode);
    return true;
}

// 获取栈顶元素
bool peek(LinkedStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    *value = stack->head->next->data;
    return true;
}

// 判断栈是否为空
bool isEmpty(LinkedStack* stack) {
    return stack->head->next == NULL;
}

栈状态不变量与应用边界

若顺序栈采用本页的“栈顶下标”约定，栈中有 $s$ 个元素时必有 $top=s-1$，有效区恰为从数组开头到 $top$ 的连续区间。入栈先检查 $s<\operatorname{MAX_SIZE}$，再使 $top$ 增一；出栈先检查 $s>0$，取出旧栈顶后再使 $top$ 减一。这个先后顺序保证了任何时刻都不会读取不存在的元素，也解释了为什么空栈、满栈不是普通元素值能够判断的状态。

链式栈不受预先数组容量限制，却仍可能上溢：申请新结点失败时，入栈也必须报告失败。出栈后应先把头结点连接到原栈顶的后继，再释放原栈顶；如果反过来释放后再读取后继，就会访问失效结点。顺序栈和链式栈的差别是存储分配方式，不会改变“只从一端进出”的后进先出语义。

递归调用也可看作由系统维护的栈帧栈：每次调用压入返回地址、局部变量和参数，函数返回时按相反顺序恢复现场。因此递归太深会耗尽调用栈，而不是“递归函数自己有无限空间”。括号匹配、深度优先遍历和表达式求值的共同点，也是先保存尚未完成的最近任务，再优先处理最新任务；一旦题目要求先到先服务，就应改用队列而非栈。