栈和队列课件

第三章

学时：6学时

3.1栈（Stack）3.2队列（Queue）

1.定义L定义

2.逻辑结构2.逻辑结构

3.存储结构3.存储结构

4.运算规则4.运算规则

5.实现方式5.实现方式

本章主要介绍以下内容：

1、栈的概念、存储结构及其基本操作

2、队列的概念、存储结构及其基本操作

3、栈与队列的应用举例

本章重点难点：

1、栈的存储结构、特点、基本操作算法实现、以

及栈在递归算法实现中的应用。

2、队列存储结构、特点、基本操作、算法实现

、循环队列及其应用。

栈是仅在表尾进行插入、删除操作的线性表。

表尾（即an端）称为考顶/top;表头（即ai端）称为戈底/base

从栈顶删除最后一

想一想：要从栈中取出ai,个元素的操作，称

应当如何操作？出栈。

问题1:堆栈是什么？它与一般线性表有什么不同？

堆栈是一种特殊的线性表，它只能在表的一端（即

栈顶）进行插入和删除运算。

一般线性表堆栈

逻辑结构：1:1逻辑结构：1:1

存储结构：顺序表、链表存储结构：顺序栈、链栈

“出”=删除=弹出=POP（a，

栈不存在的条件：base=NULL;

栈为空的条件：base=top;

栈满的条件：top-base=stacksize;

问题：什么叫“向上生成”的栈？

“向下生成”是如何生成的？

若入栈动作使地址向高端增长，称为“向上生成”的栈;

若入栈动作使地址向低端增长，称为“向下生成”的栈;

对于向上生成的堆栈：

入栈口诀：堆栈指针top“先压后加”：S[top++]=an+l

出栈口诀：堆栈指针top“先减后弹"：e=S[-top]

问题3:为什么要设计堆栈?

它有什么独特用途?

1.调用函数或子程序非它莫属；

2.递归运算的有力工具；

3.用于保护现场和恢复现场；

4.简化了程序设计的问题。

下面用3个例子来帮助理解堆栈:

例1.一个栈的输入序列为1,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的输出可以实现，每压入一数便立即弹出即。

思考：有无通用的判别原则?

例3：设依次进入一个栈的元素序列为c,a,b,d,

则可得到出栈的元素序列是：

A)a,b,c,dB)c,d,a,b

C)b,ad,aD)a,c,d,b

答：A)、D)可以，B)、C)不行。

讨论：有无通用的判别原则?

有！若输入序列…，Pj…Pk…Pj…(Pj<Pk<Pj

一定不存在这样的输出序列…,P匕叫…Pk…

本节重点：顺序栈和链栈的基本操作

栈的抽象数据类型定义:

ADTStack{

数据对象：D=

数据关系：R=

入栈、出栈、

基本操作：建栈初始化、

判断栈满或栈空、

读栈顶元素值等。

}ADTStack

顺序栈的存储表示（教材P46）：

#defineSTACK-INIT-SIZE/Jo//存储空间初始分配量

#defineSTACKINCREMENT10//存储空间分配增量

typedefstruct{

SElemType*base;//栈的基址即栈底指针

SElemType*top;//栈顶指针

intstacksize;//当前分配的空间

}SqStack;

顺序栈的入栈操作——例如用堆栈存放(A,B,C,D)

Push(D);

顺序栈出栈操作——例如从栈中取出B

链栈的入栈操作和出栈操作(教材省略)

栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈

(1)链栈的构造方式以头指针为栈顶，在头指针处插入或删除

datanext链栈中每个结点由两个域构成：

data域和next域，其定义为：

typedefStructSNode{

SElemTypedata;

StructSNode*next;

}Node;

Node*st,*p;

intm=sizeof(Node);

(2)操作

链栈

入栈

函数

链栈

出栈

函数

例3表达式求值(这是栈应用的典型例子)

这里，表达式求值的算法是“算符优先法”。

例如：编写算法，用栈实现表达式3*(7-2)求值。

一个算术表达式是由

操作数(x,y,z…)和

算符(*，/,+,(,

(1)表达式求值必须满足算术四则运算规则:

a.从左算到右

b.先乘除，后加减

c.先括号内，后括号外

为了实现算符优先算法，可以设定两个工作栈,

OPND—存放操作数或运算结果，OPTR—存放运算符号。

（2）算法思想：

1）首先置操作数栈OPND为空栈，表达式的起始符#为运算

符栈OPTR的栈底元素；

2）依次读入表达式中的每个字符，

若运算符是‘产或栈顶是结束计算，返回OPND栈顶

值。

if（是操作数）一贝”PUSH（OPND,操作数）；

if（是运算符）一则与OPTR栈顶元素进行比较，按优

的噌以挪篆达式求值完毕（当前读入的字符和OPTR

栈的栈顶元素均为#）

表达式求值过程的描述:3*(7-2)

OPTROPNDINPUTOPERATE

#3*(7・2)#Push(opnd,,3,)

#3*(7-2)#Push(optr,'*')

礼*3(7-2)#Push(optr,'(')

37-2)#Push(opnd,,7,)

3,7-2)#Push(optr,'-')

#,*,(「3,72)#Push(opnd,,2,)

#,*,(「3,7,2)#Operate(7-2)

#,*,(3,5)#Pop(optr)

礼*3,5#Operate©*5)

#15#GetTop(opnd)

例4汉诺（Hanoi）塔问题

移动时的规则：x

♦：♦每次只能移动一个盘子；]

只能小盘子在大盘子上面；|

可以使用任一柱子。心

分析：

设三根柱子分别为X,y,Z,盘子在X柱上，要移到Z柱上。

1、当n=l时，盘子直接从x柱移到z柱上；

2、当n>l时,则:

①设法将前n-1个盘子从x移到y柱上（借助z）,则盘

子n就能从x移到z柱上；

②再设法把n-1个盘子从y移到z柱上（这又是一个与原来

相同的问题，只是规模少1了）。

设计如下:

VoidHanoi(intn,charx,chary,charz)

{//将n个编号从上至(下为L.・n的盘子从x柱，借助y柱移到z柱

if(n==1)

move(x,1,z);//将编号为1的盘子从x柱移到z柱

else{//将nT个编号从上到下为1…n-1的盘子从x柱，借助y

柱移到z柱

Hanoi(n-1,x,z,y);

move(x,n,z);//修编号为11的盘子从*柱移到2柱

//将nT个编号从上到下为l...n-l的盘子从y柱，借助x柱

Hanoi(n-1,y,x9z);

32队列

队列的定义限制在一端插入、在另一端删除的线性表

称为一个队列。插入端称为队尾，删除端称为队首。

分别用一个“队头指针”和一个“队尾指针”指向队

首和队尾。

a2

队列的顺序存储结构及算法实现

•顺序队列：用连续的空间区域存放一个

队列，设置两个指针分别指向队头合队

尾。

■循环队列：为解决顺序队列中的溢出现

象而设置的头尾连接的队列。

•链式队列：每个元素定义成一个结点，

含两个域：其中数据域：存放结点数据,

顺序队列:

4-1图显示顺序表入队出队的过程:

从示意图中可以看到，随着入队、出队操作的进行，

整个队列会整体向后移动，这样就出现了图4-1(d)

中的现象：队尾指针虽然已经移到了最后，而队列却

未真满的“假溢出”现象，使得队列的空间没有得到

有效的利用。

rear=9

图4」

Rcdl1

front="l

(a)

(b)

2.循环队列

为了解决上述队列的“假溢出”现象，要做移

动操作，当移动数据较多时将会影响队列的操

作速度。一个更有效的方法是将队列的数据区

Q：0・.MAXLEN-1］看成是首尾相连的环，即将

表示队首的元素Q［0］与表示队尾的元素

Q［MAXLEN-L］连接起来，形成一个环形表，这

就成了循环队列，如图（4-2）所示。

循环队列示意图

MAXSIZE-1

front14-2循环队

歹U

上图是假设长度为10的循环队列操作示意图。

因为是头尾相接的循环结构，所以将入队时的队尾指

针加1操作修改为：

p->rear=(p->rear+l)%MAXLEN；

将出队时的队头指针加1操作修改为：

p->front=(p->front+l)%MAXLEN；

在图4-4(a)中，此时front=4,rear=8,队列中具

有：@6、a7、a8>@9四个元素；

随着@『@15相继入队，此时front=4,rear=4,队

列已满，如(b)所示，可见在队满情况下有：

front==rear0

若在(a)的情况下，@6〜ag相继出队，此时队空，

front=8,rear=8,如(c)所示，也有：front二

二rear,也就是说，仅根据等式front二二rear无法有

效判别是“队满”还是“队空