文档介绍：引例
:
:
:

:
文本信息:字符串
栈,队和字符串
调用:ab  c  d
返回: d c  b fa
返回:d c  b  a
搜索:ab  c  d
完成: a b c d
指令: a b c d
响应: a b c d
请求: a b c d
12/9/2017
本章
知识
要点
本章
重点
本章
难点
第 3 章栈、队列和串
栈的特点,基本操作及实现;
队列的特点,基本操作及实现;
串的概念,基本运算及存储。
栈和队列的操作特性;
栈和队列基本操作的实现;
串的模式匹配算法。
两栈共享空间的实现;
循环队列的组织及队空队满的判定;
改进的模式匹配KMP算法。
12/9/2017
栈
栈的逻辑结构

栈(stack)是限在表尾进行插入和删除操作的线性表。
允许进行插入和删除操作的一端叫栈顶,另一端称为栈底。
(a1,a2,a3,a4,…an)
栈顶
栈底
栈的示意图:
a1
a2
a3
a4
栈的几个术语:
空栈,入栈/压栈,出栈/弹栈。
12/9/2017
栈
栈的逻辑结构

线性性:相邻元素有前驱和后继关系
a1
a2
a3
a4
注意,栈只限制了插入和删除的位置,并没有限制插入和删除的时间。以三个元素(a,b,c)依次入栈为例,有下列几种情况:
受限性:所有操作限于栈顶
后进先出性:元素入栈后再出栈,后进者先出(last in first out)
12/9/2017
栈
栈的逻辑结构
a
b
c
三个元素依次入栈(a,b,c)再出栈的情形示意:
a
b
c
a
b
c
a
b
c
a
b
c
三个元素的情形有五种,那N个元素时,如何求解全部的方案?
12/9/2017
栈
栈的逻辑结构

ADT Stack
Data
栈中元素具有相同类型及后进先出特性,
相邻元素具有前驱和后继关系
Operation
InitStack
前置条件:栈不存在
输入:无
功能:栈的初始化
输出:无
后置条件:构造一个空栈
12/9/2017
栈
栈的逻辑结构

DestroyStack
前置条件:栈已存在
输入:无
功能:销毁栈
输出:无
后置条件:释放栈所占用的存储空间
Push
前置条件:栈已存在
输入:元素值x
功能:在栈顶插入一个元素x
输出:如果插入不成功,抛出异常
后置条件:如果插入成功,栈顶增加了一个元素
12/9/2017
栈
栈的逻辑结构

Pop
前置条件:栈已存在
输入:无
功能:删除栈顶元素
输出:如果删除成功,返回被删元素值,否则,抛出异常
后置条件:如果删除成功,栈减少了一个元素
GetTop
前置条件:栈已存在
输入:无
功能:读取当前的栈顶元素
输出:若栈不空,返回当前的栈顶元素值
后置条件:栈不变
12/9/2017
栈
栈的逻辑结构

Empty
前置条件:栈已存在
输入:无
功能:判断栈是否为空
输出:如果栈为空,返回1,否则,返回0
后置条件:栈不变
endADT
12/9/2017
栈
栈的顺序存储结构及实现

栈的顺序存储结构称为顺序栈(sequential stack)。它实际上是顺序表的简化,通常我们用小下标端表示栈底,大下标端表示栈顶。
由于顺序栈的主要操作发生在栈顶,故我们用一个变量(top)来标记它。请注意它与顺序表的length的关系。
SeqList
MaxSize
length
data
……
SeqStack
StackSize
top
data
……
表中元素个数
栈顶元素下标
12/9/2017