第3章 数据结构（Ｃ＋＋版）栈和队列

数据结构第3章栈和队列第2讲1本章分为（3）讲第1讲

3.1栈

3.2栈的顺序存储结构及实现

3.3栈的链表存储结构及实现

3.4栈的应用3.4.1表达式计算第3讲3.7队列的链表存储结构及实现3.8队列的应用第2讲

3.4.2子程序的嵌套调用

3.4.3递归调用

3.5队列

3.6队列的顺序存储结构及实现供教师参考23.4.2

子程序的嵌套调用

在各种程序设计语言中都有子程序（或称函数、过程）调用功能。一个子函数还可以调用另一函数。在系统软件中会自动使用栈，将返回地址管理起来。下图所示为由主程序开始的三层嵌套调用关系，以及返回地址栈的情况。33.4.3

递归调用一个子程序可以直接或问接地调用自身。这就是递归调用。在一层层递归调用时，其返回地址和所在每一调用层的形参变量数据都需一一记下进栈。返回时，它们一一出栈并且被采用。现以求阶乘的递归方法为例分析栈在递归中的应用。这样可以加深对递归调用的理解，提高运用递归方法进行程序设计的能力。43.4.3

递归调用

求n!的递归方法思路是：

n!=

与之相应的Ｃ函数框架是：

floatfac(intn){floatp;if(n==0||n==1)p=1;elsep=n*fac(n-1);//递归调用

returnp;}5//求阶乘的递归函数

floatfac(intn)

{floatp;

if(n==0)p=1;

elsep=n*fac(n-1);

return(p);

}软件内部会自动用到两个栈，一个递归调用的返回地址栈(略)，一个是调用时函数参数栈如图(b).

63.5

队列

队列(Queue)也是一种特殊的线性表。在现实中例子很多，如客户到银行办理业务往往需要排队，先来的先办理，晚来的则排在队尾等待，如图(a)所示。抽象成逻辑图如图(b)所示。73.5.1队列的定义

队列(Queue)是特殊的线性表,其所有的插入均限定在表的一端,而所有的删除则限定在表的另一端。

允许插入的一端称队尾(Rear),

允许删除的一端称队头(Front)。

特点：先进先出(FirstInFirstOut)FIFO

使用队尾指针rear，队头指针front。83.5.2

队列的抽象数据类型ADTQueue{

数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0;}

数据关系：R={<ai-1,ai>|ai-1,ai∈≥D,i=2,3,…,n}

约定a1端为队头，an

端为队尾。基本操作：初始化一个空队列；判队空，空队返回True,否则返回False；入队，在队尾插入一个元素；出队，在队头删除一个元素；取队头数据元素值；置队列为空状态；销毁队列；等等；

}ADTQueue;93.6

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

常用一维数组来存储队列中的元素。并约定：头指针front指向队列头元素的前一位置；

尾指针rear指向队尾元素。队列顺序存储结构：typedef

int

ElemType;struct

SeQueuestr

{ElemType

elem[MAXSIZE];//一维数组

intfront,rear; //头、尾指针

};10注意：

(d)因尾指针rear已到最后位置,所以再进队a7会发生假“溢出”。

(a)和(c)队列为空,均有：

rear==front。3.6.1

队列的顺序存储结构

假设有个队列能容纳6个元素，如图:（a）初始空状态，

rear

=

front

=

−1；（b）3个元素相继入队；（c）a1,a2,a3先后出队；空状态，rear

=

front

=

2；（d）a4,a5,a6依次入队；假溢出状态。??11

采用平移元素的方法,即一旦发生“假溢出”就把整个队列的元素平移到存储区的首部。如图,将a4,a5,a6平移到elem[0]至elem[2],而将a7插到第3个位置上,显然,平移元素的方法效率是很低的。解决“假溢出”方法（1）:12图(a)

设想elem[0]接在elem[5]之后,发生假溢出时,可把a7插入到第0个位置上。

图(b)元素a8和a9进队后队列已满（真）,若还要插入元素就会发生上溢（真）。此时有：front=rear=2。

图(C)队列为空状态,有：front=rear=0。

队列只凭rear==front,无法判别队空还是队满，矛盾？解决“假溢出”方法（2）:13解决矛盾方的法：循环队列

①设置一个布尔变量来区分队空和队满；②不设布尔变量，而使有MAXSIZE个空间的数组仅存储MAXSIZE-1个数据，即空闲一个空间。这样，可以把尾指针加1后是否等于头指针作为队满的标志。实践证明②更加方便好用，这就是所谓循环队列。

循环队列判断队空条件：rear==front循环队列判断队满条件：

(rear+1)%MAXSIZE==front14循环队列的进队：在队列循环中,每插入一个新元素时,就把尾指针rear沿顺时针方向移动，即:

rear=(rear+1)%MAXSIZE;

elem[rear]=x;

假设：MAXSIZE是6x是

a7rear=(5+1)%6=0elem[0]=a715循环队列的出队：同样,每删除一个新元素时,就把头指针front沿顺时针方向移动一个位置,即:

front=(front+1)%MAXSIZEx=elem[front];假设：MAXSIZE是6front=(5+1)%6=0出队elem[0]即a7，最终队列的头元素就是a8。163.6.2

循环队列类定义

循环队列实质上是顺序存储结构。类的数据成员包括：一个一维数组，一个头指针，一个尾指针:

ElemType

elem[MAXSIZE];

int

front,rear;

各种操作的处理可以作为类的函数成员。讨论循环队列的各种操作，重点是进队和出队操作：

voidAddQ(ElemTypex); //进队

ElemType

DelQ(); //出队17classSeQueue{private:

ElemType

elem[MAXSIZE];

int

front,rear;public:

SeQueue(){front=0;rear=0;} //初始化空队列

~SeQueue(){};

intEmpty();voidDisplay(); //输出队列

voidAddQ(ElemTypex); //进队

ElemType

DelQ(); //出队

ElemType

GetFront();};1.循环队列的类定义：18

int

SeQueue::Empty()//判断循环队列是否为空

{if(rear==front)return1;elsereturn0;}

ElemType

SeQueue::GetFront()//取队首元素，不出队

{ElemTypex;

if(front==rear)//判断队列是否为空{cout<<"\nQueuisEmpty!"<<endl;x=-1;}elsex=elem[(front+1)%MAXSIZE];returnx;}循环队列类的函数：19进队是在队列尾指针处插入。首先判断当前循环队列是否已满，如果队列已满，则输出提示信息；否则让尾指针rear加1对MAXSIZE取模后，x进队。voidSeQueue::AddQ(ElemTypex){if((rear+1)%MAXSIZE==front)//判断是否满队

cout<<"\nQueuisFull!"<<endl;else{rear=(rear+1)%MAXSIZE;//尾指针加1

elem[rear]=x;//x进队列

}}

2.循环队列的进队-算法3.720首先判断队列是否为空，如果队列为空，不能出队，输出提示信息，返回异常数据；否则让头指针front加1对MAXSIZE取模后，返回elem[front]值。ElemType

SeQueue::DelQ(){if(front==rear)//判断队列是否为空{cout<<"\nQueueisEmpty!"<<endl;return-1; //表明队空，未曾出队

}else{front=(front+1)%MAXSIZE;//出队操作

returnelem[front];}}3.循环队列的出队-算法3.821创建循环队列对象Q，调用进队、出队和输出函数。int

main(int

argc,char*argv[]){ElemTypee;intj;

SeQueueQ;

cout<<"\n队列顺序存储结构演示";

cout<<"进队data=?";cin>>e;

Q.AddQ(e); //进