《数据结构与算法》第3章 栈与队列

数据结构与算法 (C++语言版)第3章 栈与队列

栈 栈的定义 栈(stack)是限制在表的一端进行插入和删除的线性表， 又称为后进先出(last in first out)的线性表(简称LIFO结 构)。进行插入和删除的一端是浮动端，称为栈顶(top), 并用一个“栈顶指针”指示；另一端是固定端，称为栈底 (bottom)。如图所示，栈S=(k1, k2, …, kn),其中k1为栈底元素，kn 为栈顶元素。栈中元素按k1, k2, …, kn的次序进栈，退栈的第一个元素 为栈顶元素。

例3.1 设有4个元素a、b、c、d进栈,给出它 们所有可能的出栈次序。 答:所有可能的出栈次序如下: abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba

例3.2 设一个栈的输入序列为A,B,C,D,则借助 一个栈所得到的输出序列不可能是 。 (A) A,B,C,D (C) A,C,D,B (B) D,C,B,A (D) D,A,B,C

答:可以简单地推算,得容易得出D,A,B,C 是不可能的,因为D先出来,说明A,B,C,D 均在栈中,按照入栈顺序,在栈中顺序应为 D,C,B,A,出栈的顺序只能是D,C,B,A。所 以本题答案为D。

例3.3 已知一个栈的进栈序列是1,2,3,…,n,其输出 序列是p1,p2,…,pn,若p1=n,则pi的值 。 (A) i (C) n-i+1 (B) n-i (D) 不确定

答:当p1=n时,输出序列必是n,n-1,…,3,2,1,则有:

p2=n-1,p3=n-2,

…,pn=1 推断出pi=n-i+1,所以本题答案为C。

例3.4 设n个元素进栈序列是1,2,3,…,n,其输出序 列是p1,p2,…,pn,若p1=3,则p2的值 。 (A) 一定是2 (C) 不可能是1 (B) 一定是1 (D) 以上都不对

答:当p1=3时,说明1,2,3先进栈,立即出栈3,然后可 能出栈,即为2,也可能4或后面的元素进栈,再出栈。因 此,p2 可能是2,也可能是4,…,n,但一定不能是1。所以 本题答案为C。

栈 在栈顶插入元素的操作通常称为入栈，删除栈顶元素的操 作称为出栈。除此之外，栈的基本操作还包括栈的初始化、 判空及取栈顶元素等。栈的抽象数据类型定义见以下ADT 。

栈

栈 栈的抽象类 程序给出了栈的抽象类定义，从面向对象的观点定义了栈 的属性、方法，后面将介绍栈的顺序存储和链式存储所对 应的类均是该抽象类的派生类。

栈

栈 栈的顺序存储结构 栈的顺序存储结构称为顺序栈，它利用一组地址连续的存 储单元依次存放从栈底到栈顶的数据元素，并用一个变量 记录栈顶元素的位置。通常采用数组来存放，习惯上将栈 底放在数组下标小的那端。以下程序给出了顺序栈的类描 述。由于栈在使用过程中所需的最大空间很难估计。因此， 一般来说，在初始化设空栈时不应限定栈的最大容量。

栈

栈

栈

栈 栈的初始化操作为：按设定的初始分配量进行第一次存储 分配，top为栈顶指针，其初值指向栈底，值为 1,即 top= 1可作为

栈空的标记。每当插入新的栈顶元素时，指 针top增1;删除栈顶元素时，指针top减1。因此，非空栈中 的栈顶指针始终在栈顶第一个元素的位置上。下图展示了 顺序栈中数据元素进栈和出栈时与栈指针之间的对应关系。

栈

栈 栈的链式存储结构 栈的链式表示，即链栈，如图所示。由 于栈的操作是线性表操作的特例，因此 链栈可看成运算受限的单链表。其操作 易于实现，因此不作详细讨论。其特点 如下：① 链栈无栈满问题，空间可扩 充；② 插入与删除仅在栈顶处执行； ③ 链式栈的栈顶在链头；④ 适合于多 栈操作。以下程序给出了链栈的类描述。

栈