文档介绍:第三章栈和队列
*
通常称,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。
线性表栈队列
Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)
1≤i≤n+1
Delete(L, i) Delete(S, n) Delete(Q, 1)
1≤i≤n
栈和队列是两种特殊的线性表,是操作受限的线性表,称限定性DS。
*
栈的应用举例
栈的类型定义与实现
队列的类型定义与实现
练****br/> 递归过程
栈的定义和特点
定义:限定仅在表尾进行插入或删除操作的线
性表,表尾—栈顶,表头—栈底,不含
元素的空表称空栈。
特点:先进后出(FILO)或后进先出(LIFO)
*
an
a1
a2
……...
栈底
栈顶
...
出栈
进栈
栈s=(a1,a2,……,an)
栈的类型定义与实现
设有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 Stack {
数据对象:
D={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系:
R1={ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }
约定an 端为栈顶,a1 端为栈底。
基本操作:
} ADT Stack
栈的抽象数据类型定义
*
InitStack(&S)
DestroyStack(&S)
ClearStack(&S)
StackEmpty(s)
StackLength(S)
GetTop(S, &e)
Push(&S, e)
Pop(&S, &e)
StackTravers(S, visit())