文档介绍：第三章栈和队列
学时:6学时
泰山学院
栈(Stack) 队列(Queue)
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
泰山学院
本章主要介绍以下内容:
      1、栈的概念、存储结构及其基本操作
      2、队列的概念、存储结构及其基本操作
      3、栈与队列的应用举例 
 
本章重点难点:
1、栈的存储结构、特点、基本操作算法实现、以及栈在递归算法实现中的应用。
      2、队列存储结构、特点、基本操作、算法实现、循环队列及其应用。
泰山学院
栈是仅在表尾进行插入、删除操作的线性表。
表尾(即 an 端)称为栈顶/top ; 表头(即 a1 端)称为栈底/base
例如: 栈 S= (a1 , a2 , a3 , ……….,an-1 , an )
插入元素到栈顶的操作,称为入栈。
从栈顶删除最后一个元素的操作,称为出栈。
an称为栈顶元素
a1称为栈底元素
想一想:要从栈中取出a1,应当如何操作?
强调:插入和删除都只能在表的一端(栈顶)进行!
泰山学院
问题1:堆栈是什么?它与一般线性表有什么不同?
堆栈是一种特殊的线性表,它只能在表的一端(即栈顶)进行插入和删除运算。
一般线性表堆栈
逻辑结构:1:1 逻辑结构: 1:1
存储结构:顺序表、链表存储结构:顺序栈、链栈
运算规则:随机存取运算规则:后进先出(LIFO)
“进”=插入=压入=PUSH(an+1)
“出”=删除=弹出=POP(an)
泰山学院
栈不存在的条件: base=NULL;
栈为空的条件: base=top;
栈满的条件: top-base=stacksize;
a1
a2
……
an
顺序栈S
ai
……
低地址
高地址
an+1
栈底base
栈顶top
泰山学院
若入栈动作使地址向高端增长,称为“向上生成”的栈;
若入栈动作使地址向低端增长,称为“向下生成”的栈;
对于向上生成的堆栈:
入栈口诀:堆栈指针top “先压后加”: S[top++]=an+1
出栈口诀:堆栈指针top “先减后弹”: e=S[--top]
问题:什么叫“向上生成”的栈? “向下生成”是如何生成的?
泰山学院
问题3: 为什么要设计堆栈? 它有什么独特用途?
调用函数或子程序非它莫属;
递归运算的有力工具;
用于保护现场和恢复现场;
简化了程序设计的问题。
下面用3个例子来帮助理解堆栈:
泰山学院
,2,3,若在入栈的过程中允许出栈,则可能得到的出栈序列是什么?
答:
可以通过穷举所有可能性来求解:
① 1入1出, 2入2出,3入3出, 即123;
② 1入1出, 2、3入,3、2出, 即132;
③ 1、2入,2出, 3入3出, 即231;
④ 1、2入,2、1出,3入3出, 即213;
⑤ 1、2、3入,3、2、1出, 即321;
合计有5种可能性。
泰山学院
例2:一个栈的输入序列是12345,若在入栈的过程中允许出栈,则栈的输出序列43512可能实现吗?12345的输出呢?
答:
43512不可能实现,主要是其中的12顺序不能实现;
12345的输出可以实现,每压入一数便立即弹出即。
思考:有无通用的判别原则?
泰山学院