考研笔记

栈的顺序存储与链式存储

这一节的题只考一件事：top 指向哪里、往哪个方向长，入栈出栈的语句就跟着变。 教材注意框原话：「栈顶、队头与队尾的指针的定义是不唯一的，做题时务必仔细审题和思考。」判空判满条件收在 速查：栈与队列的判空判满，本页讲怎么从约定推出语句。

机制

3.1.2 顺序栈

利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针 top 指示当前栈顶元素的位置。

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int top;              // 栈顶指针
}SqStack;

教材的默认约定是 top 指向栈顶元素，初始 S.top=-1：

项写法
栈顶元素S.data[S.top]
入栈栈不满时，栈顶指针先加 1，再送值到栈顶：S.data[++S.top]=x;
出栈栈非空时，先取栈顶元素，再将栈顶指针减 1：x=S.data[S.top--];
栈空 / 栈满 / 栈长S.top==-1 / S.top==MaxSize-1 / S.top+1

另一种常见约定是 top 指向栈顶元素的下一个位置，初始 S.top=0：入栈先送值再加 1，出栈先减 1 再取值；栈空 S.top==0，栈满 S.top==MaxSize。

出栈只移动指针，不清除数据。 教材图 3.2(d)：A~E 依次入栈后 E、D、C 相继出栈，C、D、E 可能仍在原先的单元存储着，但 top 已经指向新的栈顶，它们已不在栈中（2009 命题追踪「出/入栈操作的模拟」）。

顺序栈的入栈受数组上界约束，最大使用空间估计不足时可能发生栈上溢。

共享栈

两个顺序栈共享一个一维数组空间，两个栈底分别设在共享空间的两端，两个栈顶向中间延伸。

项0 号栈（左）1 号栈（右）
栈空top0==-1top1==MaxSize
入栈top0 先加 1 再赋值top1 先减 1 再赋值
出栈先取值再减 1先取值再加 1

栈满：两个栈顶指针相邻，top1-top0==1。 共享栈为了更有效地利用存储空间，两个栈的空间相互调节，只有整个存储空间被占满时才发生上溢。存取数据的时间复杂度仍为 。

3.1.3 链栈

采用链式存储的栈。优点是便于多个栈共享存储空间和提高效率，且不存在栈满上溢的情况。

通常用单链表实现，所有操作都在单链表的表头进行。教材规定链栈没有头结点，Lhead 指向栈顶元素。

操作（不带头结点，top 指向栈顶结点）写法
入栈 x 结点x->next=top; top=x;
出栈并存入 xx=top->data; top=top->next;

带头结点和不带头结点的链栈，具体实现会有所不同。

手算模板

入栈、出栈语句由两个约定决定：top 指向栈顶元素还是其下一个位置；栈向高地址还是低地址增长。

top 指向增长方向入栈出栈
栈顶元素高地址data[++top]=xx=data[top--]
栈顶元素的下一个位置高地址data[top++]=xx=data[--top]
栈顶元素低地址data[--top]=xx=data[top++]
栈顶元素的下一个位置低地址data[top--]=xx=data[++top]

判断依据：top 指向栈顶元素时，入栈要先移到空位再存；top 指向下一个位置时，它本身就是空位，先存再移。出栈正好反过来。

从初始值反推约定：数组下标 时，top=1 说明指向下一个位置（向高长），top=n+1 说明指向栈顶元素（向低长）。王道 3.1.4 第 4、5、6 题分别对应表中第 1、2、3 行，详见 3.1.1 的错题复盘。

边界

说法判断说明
「栈和队列的存储结构相同」❌它们具有相同的逻辑结构（都是线性结构），只是对数据的运算不同
「栈是顺序存储的线性结构」❌栈可以顺序存储也可以链式存储。准确说法是限制存取点的线性结构
「删除栈底元素是栈的基本操作」❌不属于基本运算，但可以通过调用基本运算求得
「出栈后元素就从存储单元里被清除了」❌只是 top 移动了，数据可能仍在原单元；逻辑上已不在栈中
「链栈的优势是插入、删除更容易实现」❌优势是通常不会出现栈满，可以动态分配存储空间
「共享栈能减少存取时间」❌存取仍是 。好处是节省存储空间，降低发生上溢的可能
「共享栈降低下溢的可能」❌降低的是上溢：存储器满了还往里写。下溢是存储器空了还往外读
「共享栈栈满是 top1==top2」❌top1=-1、top2=n 起步时，栈满是 top2-top1==1
「任何单链表都适合做链栈」❌只有表头指针、没有表尾指针的单向循环链表最不适合：在表头插入删除后要更新尾结点的 next，找尾结点需

错题复盘：栈顶指针的地址计算（3.1.4 第 7 题）

空栈的栈顶指针为 1000H，栈向高地址增长，每个元素占一个存储单元。执行 push, push, pop, push, pop, push, pop, push 后，栈顶指针为 1002H。 每次 push 加 1、pop 减 1，依次为 1001H、1002H、1001H、1002H、1001H、1002H、1001H、1002H。只看最终的入栈次数减出栈次数（5−3=2）即可。

错题复盘： GetTop 不出栈（3.1.4 第 12 题）

InitStack(st); Push(st,a); Push(st,b); Pop(st,x); GetTop(st,x); 之后 x 的值为 a。 Pop 让 x=b 并弹出 b；GetTop 读出当前栈顶 a 覆盖 x，但 a 仍留在栈中。

考点

  • 两种 top 约定 × 两种增长方向，对应四组入栈出栈语句。
  • 出栈只移指针，不清数据（2009 命题追踪）。
  • 共享栈：栈满 top1-top0==1；好处是节省空间、降低上溢。
  • 链栈：不带头结点，操作都在表头；优势是不会栈满。

链接

反向链接