文档介绍：数据结构与算法 (C++语言版)
第3章栈与队列
栈
栈的定义
栈(stack)是限制在表的一端进行插入和删除的线性表,又称为后进先出(last in first out)的线性表(简称LIFO结构)。进行插入和删除的一端是浮动端,称为栈顶(top),并用一个“栈顶指针”指示;另一端是固定端,称为栈底(bottom)。如图所示,栈S=(k1,
k2, …, kn),其中k1为栈底元素,kn
为栈顶元素。栈中元素按k1, k2, …,
kn的次序进栈,退栈的第一个元素
为栈顶元素。
设有4个元素a、b、c、d进栈,给出它们所有可能的出栈次序。
答:所有可能的出栈次序如下:
abcd abdc acbd acdb
adcb bacd badc bcad
bcda bdca cbad cbda
cdba dcba
设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是。
(A) A,B,C,D (B) D,C,B,A
(C) A,C,D,B (D) D,A,B,C
答:可以简单地推算,得容易得出D,A,B,C是不可能的,因为D先出来,说明A,B,C,D均在栈中,按照入栈顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是D,C,B,A。所以本题答案为D。
已知一个栈的进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=n,则pi的值。
(A) i (B) n-i
(C) n-i+1 (D) 不确定
答:当p1=n时,输出序列必是n,n-1,…,3,2,1,则有:
p2=n-1,
p3=n-2,
…,
pn=1
推断出pi=n-i+1,所以本题答案为C。
设n个元素进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=3,则p2的值。
(A) 一定是2 (B) 一定是1
(C) 不可能是1 (D) 以上都不对
答:当p1=3时,说明1,2,3先进栈,立即出栈3,然后可能出栈,即为2,也可能4或后面的元素进栈,再出栈。因此,p2可能是2,也可能是4,…,n,但一定不能是1。所以本题答案为C。
栈
在栈顶插入元素的操作通常称为入栈,删除栈顶元素的操作称为出栈。除此之外,栈的基本操作还包括栈的初始化、判空及取栈顶元素等。栈的抽象数据类型定义见以下ADT 。
栈
栈
栈的抽象类
程序给出了栈的抽象类定义,从面向对象的观点定义了栈的属性、方法,后面将介绍栈的顺序存储和链式存储所对应的类均是该抽象类的派生类。