栈的定义与实现

复习定位

栈是一种只在一端进行插入和删除的线性表——LIFO(后进先出)的性质使得它非常适合处理嵌套匹配的问题(函数递归调用、括号匹配、表达式求值)。顺序栈和链栈的实现差异不大——但顺序栈的容量有限可能需要扩容。

栈的定义

栈(stack)是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶(top)——另一端称为栈底(bottom)。不含任何元素的栈称为空栈(top=-1)。

栈的操作：push(插入)、pop(删除栈顶并返回)、peek/top(查看栈顶不删除)、isEmpty(判断空)、size(返回栈长度)

顺序栈

用一维数组实现——下标0作为栈底——从data[0]到data[MAXSIZE-1]顺序入栈。top指向当前栈顶元素的下标——空栈时top=-1。入栈: data[++top] = e。出栈: e = data[top--]。

顺序栈需要提前预估最大容量——当top==MAXSIZE-1时栈不可再插入——需要动态扩容(重新分配更大的数组)或报栈溢出错误。

两个栈共用同一数组的空间可以优化内存——当两个栈具有大致对等增长速度时——将两个栈底分别设在数组两端——栈顶向中间靠拢——直到top1+1==top2时栈满。这种共享栈有效利用了一个数组的整体内存。

链栈

用单链表实现栈——top指针指向链表的第一个结点(即栈顶)。入栈——在链表头部插入结点；出栈——删除链表头部结点。链栈不限制容量(除非内存耗尽)——适合数据规模变化很大的场景。

// 链栈的入栈
void push(LinkStack *S, ElemType e) {
    StackNode *node = malloc(sizeof(StackNode));
    node->data = e;
    node->next = S->top; // 将新结点链接到原栈顶之前
    S->top = node;       // 更新栈顶指针
    S->count++;
}

链栈的出栈——保存栈顶的data——将top指针后移——释放原栈顶结点。

栈的典型应用

函数调用与递归——每次函数调用——将返回地址、函数的局部变量压入栈——函数返回时弹出栈顶——恢复上一级函数的执行环境。递归的层层嵌套就是栈的层层入栈。

括号匹配——扫描表达式——遇到左括号'('入栈——遇到右括号')'——弹出栈顶的左括号检查是否匹配——如果栈空或匹配错误则括号不匹配。扫描结束后栈应为空。

表达式求值(中缀转后缀)——操作数栈和运算符栈配合——优先级高的运算符先计算——括号内的表达式提前计算。这是编译器中表达式处理的基础。

复习检查

1. 顺序栈中data[++top]=e和data[top++]=e——哪一个是正确的入栈操作——前一个还是后一个?为什么栈顶指向已存在元素(不是下一个空闲位置)时的区别明显？

2. 两个栈共享同一数组的存储方案——栈1从数组低端入栈(向高地址增长)、栈2从数组高端入栈(向低地址增长)——当top1+1==top2时的含义。

3. 链栈的入栈在链表头部还是尾部插入？解释了为什么栈顶指针总是指向链表第一个结点。

4. 括号匹配——{ [ ( ) ] }是匹配的——而{ [ ( } ) ]不匹配——栈的什么操作分别展示了这两种情况？

5. 递归函数的栈溢出——无限递归最终导致栈溢出错误——这是因为每次递归调用在栈上分配哪些数据而导致的？