文档介绍：2017/11/20
1
第3章栈和队列
本章主题:栈和队列的应用
教学目的:掌握栈和队列的应用方法,理解栈的重要作用
教学重点:利用栈实现行编辑,利用栈实现表达式求值
教学难点:利用栈实现表达式求值
栈,也叫堆栈,是最常用也是最重要的数据结构之一。比如编译器中的语法识别、数学表达式的处理、程序运行中的函数及过程的调用等,都要用到栈的有关特性。它们是栈应用于实际问题的典型。
栈
【课前思考】 
1. 什么是线性结构?
简单地说,线性结构是一个数据元素的序列。
  2. 你见过餐馆中一叠一叠的盘子吗?如果它们是按1,2,…,n 的次序往上叠的, 那么使用时候的次序应是什么样的?
必然是依从上往下的次序,即n,…,2,1。它们遵循的是"后进先出"的规律,这正是本章要讨论的"栈"的结构特点。 
3. 在日常生活中,为了维持正常的社会秩序而出现的常见现象是什么?
是"排队"。在计算机程序中,模拟排队的数据结构是"队列"。
2017/11/20
2
2017/11/20
3
栈是一种特殊的线性表,插入或删除栈元素的运算只能在表的一端进行,称运算的一端为栈顶,另一端称为栈底。
特点:后进先出
栈又称为“后进先出”的线性表,简称LIFO表。
栈的定义和运算
an
a1
a2
……...
栈底
栈顶
...
出栈
进栈
栈s=(a1,a2,……,an)
2017/11/20
4
初始化栈InitStack(S)
设置一个空栈S。
压栈Push(S,x)
将元素x插入栈S中,使x成为栈S的栈顶元素。
出栈Pop(S,x)
当栈S不空时,由x返回栈顶元素,并从栈中删除栈顶元素
取栈顶元素GetTop(S,x)
若栈S不空,则由x返回栈顶元素。
判栈空Empty(S)
若栈S为空栈,结果为1,否则结果为0。
2017/11/20
5
例1:
对于一个栈,给出输入项A、B、C,如果输入项序列
由ABC组成,试给出所有可能的输出序列。
A进 A出 B进 B出 C进 C出 ABC
A进 A出 B进 C进 C出 B出 ACB
A进 B进 B出 A出 C进 C出 BAC
A进 B进 B出 C进 C出 A出 BCA
A进 B进 C进 C出 B出 A出 CBA
不可能产生输出序列CAB
2017/11/20
6
例2:一个栈的输入序列是12345,若在入栈的过程中允许出栈,则栈的输出序列43512可能实现吗?12345的输出呢?
43512不可能实现,主要是其中的12顺序不能实现;
12345的输出可以实现,只需压入一个立即弹出一个即可。
435612中到了12顺序不能实现;
135426可以实现。
例3:如果一个栈的输入序列为123456,能否得到435612和135426的出栈序列?
答:
答:
2017/11/20
7
例4:计算机系2001年考研题(程序设计基础)
设依次进入一个栈的元素序列为c,a,b,d,则可得到出栈的元素序列是:
A)a,b,c,d
B)c,d,a,b
C)b,c,d,a
D)a,c,d,b
A、D可以( B、C不行)。
答:
2017/11/20
8
栈的顺序存储结构及其基本运算的实现
栈有两种存储表示方法:顺序存储和链式存储
栈的顺序存储结构简称为顺序栈。通常由一个一维数组和一个记录栈顶元素位置的变量组成。
2017/11/20
9
ElemType 为栈中元素的数据类型,可以根据需要而指定为某种具体的类型。
data域:为一个一维数组,用于存储栈中元素。
top域:栈顶指针。取值范围为0~MaxSize-1。
top=-1表示栈空,top=MaxSize-1表示栈满。
#define MaxSize <存储数据元素的最大个数>
typedef struct {
ElemType data[MaxSize];
int top;
}STACK;
顺序栈的C++语言描述如下:
2017/11/20
10
。
顺序栈的几种状态(最大长度MaxSize为4)
(a)当栈中没有数据元素时,表示为栈空。栈顶元素所对应的下标值top=-1。
(b)表示在(a)基础上执行Push(S, ‘A’)后得到这种状态。
(c)又有三个元素B、C、D先后入栈,此时栈顶元素的下标值top=3。栈已满。
(d)表示在(c)状态下,执行一次Pop(S,x)运算得到。
(e)表示在(d)状态下,执行三次Pop(S,x)运算得到。此时栈顶下标值top=-l,又变成栈空状态