数据结构PPT：栈和队列

2023/6/141栈和队列栈和队列都是操作受限的线性表，应用十分广泛。4.1栈（Stack）定义：栈是限制插入和删除操作只能在某一端进行的线性表，并按先进后出（FILO)或后进先出（ＬIＦＯ）的原则进行操作入栈顺序：

e0e1e2…en-2en-1

出栈顺序：

en-1en-2…e2e1e0

栈可以对序列实现求逆en-1e0e1en-2…进栈（Push）出栈（Pop）栈顶top栈底数据结构PPT：栈和队列全文共41页，当前为第1页。2023/6/142栈的基本操作：（参见P104）（1）栈初始化 Stack(int=10);//构造函数（2）进栈Push voidPush(constType&item);（3）出栈Pop TypePop();（4）判栈空IsEmpty intIsEmpty(){returntop==-1;}（5）读取栈顶元素GetTop TypeGetTop();（6）置空栈MakeEmpty voidMakeEmpty(){top=-1;}（7）判栈满IsFull intIsFull()const{returntop==maxSize;}栈的封闭性及其抽象数据类型：在一个栈中，出入口处称为栈顶，栈内最深处称为栈底。除了栈顶元素外，其他元素不会被改变，因而栈的封闭性非常好，使用起来非常安全。另外，在下面的栈的类定义中，体现了栈的抽象数据类型，在此定义中，所有栈的成员函数都是共有的，其他类的成员函数都可以使用这些函数，但是，栈的存储表示和成员函数的实现对其他类的成员来说都是隐蔽的。数据结构PPT：栈和队列全文共41页，当前为第2页。2023/6/1434.1.1顺序栈－－在顺序存储结构上实现的栈#include<assert.h>//C＋＋断言功能template<classType>classStack//顺序栈的类定义{ public: Stack(int=10);//栈初始化，建立一个空栈，缺省大小为10 ~Stack(){delete[]elements;} voidPush(constType&item);//将数据元素item入栈

TypePop(); //将栈顶元素出栈

TypeGetTop(); //读取栈顶元素

voidMakeEmpty(){top=-1;}//置空栈，top=-1表示栈为空

intIsEmpty()const{returntop==-1;}//判栈空

intIsFull()const{returntop==maxSize-1;}//判栈满

private://top=maxSize-1表示栈已满

inttop;//栈顶指针（栈顶元素下标）

Type*elements;//存储顺序栈的数组

intmaxSize;//顺序栈的最大容量}数据结构PPT：栈和队列全文共41页，当前为第3页。2023/6/144顺序栈的基本操作（算法）（1）顺序栈初始化算法（构造函数）template<classType>Stack<Type>::Stack(ints):top(-1),maxSize(s)//建立一个最大尺寸为s的空栈，若分配不成功则错误处理{ element=newType[maxSize];//创建顺序栈空间（数组）

assert(elements!=0);//断言语句：若条件成立，则继续；否则出错处理并终止执行}（2）顺序栈入栈算法template<classType>voidStack<Type>::Push(constType&item)//若栈不满，则将元素item插入到栈顶，否则出错处理{ assert(!IsFull());//断言：栈不满则继续执行

elements[++top]=item;//栈顶指针先加1，然后按此地址进栈}数据结构PPT：栈和队列全文共41页，当前为第4页。2023/6/145（3）顺序栈出栈算法template<classType>TypeStack<Type>::Pop()//若栈不空，则返回栈顶元素，并使栈顶指针退1；否则出错处理

{ assert(!IsEmpty());//断言：若栈不空，则继续执行

returnelements[top--];//返回栈顶元素，并使栈顶指针退1}（4）读取顺序栈栈顶元素算法Template<classType>TypeStack<Type>::GetTop()//若栈不空，则返回栈顶元素；否则出错处理{ assert(!IsEmpty());//断言：若栈不空，则继续执行

returnelements[top];//返回栈顶元素，注意：栈顶指针不变} 数据结构PPT：栈和队列全文共41页，当前为第5页。2023/6/1464.1.3链栈——利用链式存贮结构实现的栈

与顺序表一样，顺序栈的最大尺寸（maxSize）也难以确定，太小了容易溢出，太大了又浪费空间。因此在动态性较强的应用领域，宜采用链栈。 链栈的结构如下图所示。与单链表相似，但不设头结点，第一个结点即为栈顶。插入（入栈）与删除（出栈）操作均只能在表头进行。当top=NULL时，表示空栈…^top栈顶元素栈底元素数据结构PPT：栈和队列全文共41页，当前为第6页。2023/6/147链栈的定义：链栈结点类的定义：template<classType>classStack;//链栈类的前视声明template<classType>classStackNode{ friendclassStack<Type>; private: Typedata; StackNode<Type>*link; StackNode(Typed=0,StackNode<Type>*l=NULL): data(d),link(l){}//构造函数，初始化一链栈结点}datalink链栈结点结构数据结构PPT：栈和队列全文共41页，当前为第7页。2023/6/148链栈类的定义：template<classType>classStack{ public: Stack():top(NULL){}//构造函数，初始化一个空链栈

~Stack();//析构函数，释放链栈的所有结点，并使top=NULL。置栈空操作

voidPush(constType&item);//入栈操作

TypePop();//出栈操作

TypeGetTop();//读取栈顶元素

voidMakeEmpty(){top=NULL;}//置栈空操作，应先删除栈内所有结点

intIsEmpty()const{returntop==NULL;}//判栈空操作

intIsFull()const{return0}//判栈满，在链栈中该操作无意义

private: StackNode<Type>*top;//栈顶指针}数据结构PPT：栈和队列全文共41页，当前为第8页。2023/6/149链栈的入栈算法：Template<classType>voidStack<Type>::Push(constType&item)//将数据元素item入栈{ top=newStackNode<Type>(item,top);//创建一个新的链栈结点，并将该结点的data域置为item，

//link域置为top,最后将该结点的指针赋值给top.参见下图}…^top原栈顶新栈顶item(1)(2)数据结构PPT：栈和队列全文共41页，当前为第9页。2023/6/1410比较与思考：（1）比较顺序栈与链栈的类定义 两者的类名相同，均为Stack

两者成员函数的名、参数、返回类型与规格说明均相同，但内部的实现有别假定某大型软件系统原来使用顺序栈，因经常上溢，欲改用链栈，请问哪些部分需要改动？数据结构PPT：栈和队列全文共41页，当前为第10页。2023/6/1411栈应用举例——迷宫问题迷宫问题：求迷宫中从入口点到出口点所有可能的简单路径迷宫模型：入口(i,j)出口

墙通道数据结构PPT：栈和队列全文共41页，当前为第11页。2023/6/1412

所谓的简单路径是指：在求出的任何一条路径上，不能重现某一通道块，否则总有任意多条路径迷宫问题是许多实际问题的抽象，求解这类问题时，没有现成的数学公式可以套用，只能采用系统化的试探方法。下面规定： 通道用空格“”表示 墙壁用“#”表示 足迹用“0”表示 从入口点到当前立足点间，具有足迹标志的相连的通道块构成的简单路径叫当前路径将迷宫模型用二维字符型数组表示：

charmaze[n+1][n+1];

并假定入口为maze[0][0]，出口为maze[n][n]

考虑一般情况，设maze[i][j]为当前立足点，并纳入当前路径（即印上足迹标志“0”），则从当前立足点继续试探的算法如下：数据结构PPT：栈和队列全文共41页，当前为第12页。2023/6/1413ifmaze[i][j]是出口

then打印刚找到的一条简单路径，并回溯一步；

elseif东面的是通道块

then前进一步

elseif南面的是通道块

then前进一步

elseif西面的是通道块

then前进一步

elseif北面的是通道块

then前进一步

else回溯一步(i,j)东南西北数据结构PPT：栈和队列全文共41页，当前为第13页。2023/6/1414前进一步：将下一通道块印上“0”作为当前立足点（切换当前立足 点），并保存原立足点的信息以便回溯。回溯一步：去掉当前立足点的足迹“0”;

把最近的原立足点重新切换为当前立足点； 试探尚未试探过的方向。上述的活动均需要在迷宫中移动，并且具有方向性，这种活动可以使用二维数组下标增量技术来实现：行下标增量di[k]列下标增量dj[k]方向及其序号k东0南1西2北3 intdi[4]={0,1,0,-1}; intdj[4]={1,0,-1,0};01100－1－10数据结构PPT：栈和队列全文共41页，当前为第14页。2023/6/1415在上述的规定下：

k=0时，maze[i+di[k]][j+dj[k]]为立足点的东面下一块；

k=1时，maze[i+di[k]][j+dj[k]]为立足点的南面下一块；

k=2时，maze[i+di[k]][j+dj[k]]为立足点的西面下一块；

k=3时，maze[i+di[k]][j+dj[k]]为立足点的北面下一块；客体的表示方法设计：从上述的用试探法走迷宫的过程可知，其中 所管理的信息是立足点的信息。可以用三元组（i,j,k)来表 示立足点，其中(i,j)表示立足点的位置信息，k表示立足点 的下一个试探方向。可以将三元组定义成一个结构：

structitems{inti,j,k;};数据的组织方法设计：考察上述用试探法走迷宫的过程：前进一步时，需要保存原立足点的信息；回溯一步时，需要取出最近的原立足点的信息，并且遵循 后保存的先取出的原则，即“后进先出”的原则，因此可以用栈 来记录立足点的信息。迷宫问题的算法框架：

数据结构PPT：栈和队列全文共41页，当前为第15页。2023/6/14161 Stack<items>s(sz);//栈初始化：创建一个大小为sz的栈，其数据元素类型为items2 itemse;intk;3 e.i=0;e.j=0;e.k=0;s.Push(e);maze[e.i][e.j]=‘0’; //将入口作为立足点并入栈4 while(!s.IsEmpty())//若栈不空则继续循环试探

//若空表示已找到所有简单路径，可以结束程序5 {e=s.Pop();//出栈，准备试探下一方向或实现回溯一步操作6 if(e.k==4)maze[e.i][e.j]=‘‘;//四个方向均试探完毕

//消足迹,当再执行到5时回溯一步

elseif(e.i==n&&e.j==n)printmaze();//当前立足点为出口

//成功找到一条简单路径并输出，当再执行到5时回溯一步

else{k=e.k;e.k=e.k+1;s.Push(e);//记住立足点的下一试探方向

e.i=e.i+di[k];e.j=e.j+dj[k];e.k=0;//沿k方向前进一步

if(maze[e.i][e.j]==‘‘)//若为通道则切换为新立足点并入栈

{s.Push(e);maze[e.i][e.j]=‘0’;} } } 数据结构PPT：栈和队列全文共41页，当前为第16页。2023/6/1417作业：

完善迷宫问题解决算法（迷宫数组的输入inputmaze()算法、 简单路径的输出printmaze()算法等） 编写软件并上机实习要求11月6日前完成数据结构PPT：栈和队列全文共41页，当前为第17页。2023/6/14184.3队列定义：队列是限制插入操作只能在一端进行，而删除操作只能在另 一端进行的线性表，并按先进向出（FIFO）的原则进行操作。 在一个队列中，能进行删除的一端称为队首（front），能进行 插入操作的一端称为队尾（rear）。出列入列队首（front）队尾（rear） 与栈类似，队列的封闭性也非常好 栈能对输入序列部分或全局起求逆作用 队列对输入序列起缓冲作用，队列的应用非常广泛e0e1…en-2en-1数据结构PPT：栈和队列全文共41页，当前为第18页。2023/6/1419队列的基本操作Template<classType>classQueue{ public: Queue(int=10);//构造函数，队列初始化操作

voidEnQueue(constType&item);//入列操作

TypeDeQueue();//出列操作

TypeGetFront();//读取队首元素操作

voidMakeEmpty();//置队空操作

intIsEmpty()const;//判队空操作

intIsFull()const;//判队满操作}数据结构PPT：栈和队列全文共41页，当前为第19页。2023/6/1420队列的顺序存储结构——循环队列（环型队列）

由于在队列的入列和出列操作中，其对应的队尾和队首指 针（下标）都是进1操作（否则出列操作需要移动所有的数据元素），随着入列和出列操作的进行，队尾和队首指针都在逐步增大，因此队列若用普通的顺序存储结构来实现，则很容易上溢，基本不能使用，因此实际中一般使用循环队列。 通过求余运算（%），可以实现下标的循环累进：

index=(index+1)%m 012…m-1

因此，对队首和队尾进行如下操作就可以实现循环队列：

front=(front+1)%maxSize队首指针循环进1 rear=(rear+1)%maxSize队尾指针循环进1 maxSize表示数组的最大尺寸

front和rear的最大取值为maxSize-1数据结构PPT：栈和队列全文共41页，当前为第20页。2023/6/1421循环队列：逆时针运行示意图

Queue012maxSize-1maxSize-2front队首指针rear队尾指针规定：队空：front==rear队满：front==(rear+1)%maxSize队尾元素：elements[rear]

队首元素：elements[(front+1)%maxSize]@@@@数据结构PPT：栈和队列全文共41页，当前为第21页。2023/6/1422循环队列：满队列示意图

Queue012maxSize-1maxSize-2front队首指针rear队尾指针front==(rear+1)%maxSize本图满足上述队满条件。由图可知：队满时队首指针所指的单元不能利用，此时再入列会使队列变成空队列(front==rear)队尾元素elements[rear]

队首元素@@@@@@@@@@@@数据结构PPT：栈和队列全文共41页，当前为第22页。2023/6/1423循环队列的类定义：#include<assert.h>template<classType>classQueue{ public: Queue(int=10); ~Queue(){delete[]elements;} voidEnQueue(constType&item); TypeDeQueue(); TypeGetFront(); voidMakeEmpty(){front=rear=0;} intIsEmpty()const{returnfront==rear;} intIsFull()const{returnfront==(rear+1)%maxSize;} intLength()const{return(rear-front+maxSize)%maxSize;} private: intrear,front,maxSize; Type*elements;}数据结构PPT：栈和队列全文共41页，当前为第23页。2023/6/1424循环队列入列操作算法：template<classType>voidQueue<Type>::EnQueue(constType&item)//若队列不满，则将元素item插入到队尾，否则出错处理{ assert(!IsFull());//断言：队列不满则继续，否则出错处理

rear=(rear+1)%maxSize;//队尾指针循环加1 elements[rear]=item;//在队尾插入item}循环队列出列操作算法：template<classType>TypeQueue<Type>::DeQueue()//若队列不空，则删除并返回队首元素，否则出错处理{ assert(!IsEmpty());//断言：队列不空则继续，否则出错处理

front=(front+1)%maxSize;//队首指针循环加1，队首元素出列

returnelements[front];//返回出列的队首元素}数据结构PPT：栈和队列全文共41页，当前为第24页。2023/6/14254.3.3链队列——利用链式存贮结构实现的队列

与顺序表一样，循环队列的最大尺寸（maxSize）也难以确定，太小了容易溢出，太大了又浪费空间。因此在动态性较强的应用领域，宜采用链队列。 链队列的结构如下图所示。与单链表相似，但不设头结点，第一个结点即为队首。最后一个结点为队尾。插入（入列）操作只能在队尾进行，删除（出列）操作只能在队首进行。当front=rear=NULL时，表示空队列…^front队首指针

队首队尾rear队尾指针数据结构PPT：栈和队列全文共41页，当前为第25页。2023/6/1426链队列的类定义template<classType>classQueue;template<classType>classQueueNode{//链队列结点的类定义

friendclassQueue<Type>;//将链队列类作为链队列结点类的友元

private: Typedata; QueueNode<Type>*link; QueueNode(Typed=0,QueueNode*l=NULL): data(d),link(l){}};template<classType>classQueue//链队列的类定义{ public: //链队列类的成员函数

private: QueueNode<Type>*front,*rear;//队首与队尾指针}; 数据结构PPT：栈和队列全文共41页，当前为第26页。2023/6/1427链队列类的成员函数： Queue(int=10):rear(NULL),front(NULL){}//构造函数，建立一个

//空链队列，int型参数是为了与循环队列一致而设，此处无意义

~Queue();//析构函数，释放链队列的所有结点，参见下页定义

voidEnQueue(constType&item);//入列操作

TypeDeQueue();//出列操作

TypeGetFront();//读取队首元素

voidMakeEmpty();//置空队列，与析构函数类似，参见下页定义

intIsEmpty()const{returnfront==NULL;}//判队空操作

intIsFull()const;//为了与循环队列一致而设，对链队列无意义

intLength()const;//为了与循环队列一致而设，对链队列意义不大比较循环队列的类定义可知：链队列的成员函数的名、返回类型和参数表与循环队列的完全一样，这样安排的好处是，当一个大型软件原来使用循环队列时经常发生溢出，此时改用链队列的话只需将原来循环队列的类定义及其成员函数定义改为链队列的类定义和成员函数定义即可，无需更改软件的其他地方。数据结构PPT：栈和队列全文共41页，当前为第27页。2023/6/1428链队列成员函数定义：Template<classType>voidQueue<Type>::~Queue(){//析构函数，释放链队列中所有的结点

QueueNode<Type>*p; while(front!=NULL) {//队列不空，继续循环

p=front;//(1) front=front->link;//(2)出列队首结点

deletep;//释放出列的结点

}}

front^…rearpfront(1)(2)数据结构PPT：栈和队列全文共41页，当前为第28页。2023/6/1429置空队列操作：Template<classType>voidQueue<Type>::MakeEmpty(){//置空队列操作，释放链队列中所有的结点

QueueNode<Type>*p; while(front!=NULL) {//队列不空，继续循环

p=front;front=front->link;//出列队首结点

deletep;//释放出列的结点

}}链队列入列操作：Template<classType>voidQueue<Type>::EnQueue(constType&item){ QueueNode<Type>*p=newQueueNode<Type>(item,NULL); if(front==NULL) front=rear=p; else{rear->link=p;//(1) rear=p;//(2) }}

^…rearrearp(1)(2)原队尾新队尾item数据结构PPT：栈和队列全文共41页，当前为第29页。2023/6/1430链队列出列操作：template<classType>TypeQueue<Type>::DeQueue()//若队列不空，则删除队首结点并返回该结点的值，否则出错处理{ assert(!IsEmpty());//若队列不空，则继续，否则出错处理

QueueNode<Type>*p=front;//保留队首结点指针（1）

Typeretvalue=p->data;//读取队首结点的值

front=front->link;//队首指针指向下一结点，即删除队首结点（2）

if(rear==p)rear=NULL;//若原队列只有一个结点，

//则出列后为空队列：front=rear=NULL deletep;//释放原队首结点

returnretvalue;//返回原队首结点的值}原队首新队首…frontpfront(1)(2)数据结构PPT：栈和队列全文共41页，当前为第30页。2023/6/14314.5事件驱动模拟（Event-DrivenSimulation）模拟目的： （1）计算银行顾客的平均（最大）等待时间 （2）计算银行出纳员的工作繁忙程度 （3）计算银行顾客队列的最大长度出纳员服务原则： （1）某一时刻只能接待一位顾客 （2）若本窗口还有顾客则应立刻服务顾客活动原则： （1）顾客达到时间为ArrivalTime（随机数） （2）顾客需要服务的时间为ServiceTime（随机数） （3）顾客选择最短的队列排队 （4）顾客的等待时间（从进门到轮到服务）为WaitTime

（5）银行上班时间到后顾客才能进门，下班时间到时顾客 不能进门数据结构PPT：栈和队列全文共41页，当前为第31页。2023/6/1432仿真模型：

窗口队列服务窗口顾客选择排队顾客流（队列）…………数据结构PPT：栈和队列全文共41页，当前为第32页。2023/6/1433事件分析：顾客进门事件触发下列操作： （1）从顾客流队列中出列进门事件 （2）从各窗口队列中选择一最短队列 （3）计算顾客需要等待的时间 （4）将该顾客入列到所选的最短窗口队列中

出纳员对当前顾客服务完毕事件触发下列操作： （1）累计本窗口的服务时间 （2）累计本窗口顾客的等待时间 （3）记录本窗口顾客的最大等待时间 （4）记录本窗口的最大队列长度 （5）累计本窗口服务的顾客总数 （6）将当前顾客出列

数据结构PPT：栈和队列全文共41页，当前为第33页。2023/6/1434数据结构设计：（1）顾客信息的表示——可将其定义为一结构Event

进门时间（随机数）ArrivalTime——事件 进门序号（顾客号）CustomerID——用于统计顾客总数 要求服务的时间（随机数）ServiceTime

需要等待的时间（计算数）WaitTime（2）窗口信息的表示——将其定义为一结构TellerStatus

本窗口完成当前窗口队列服务的时刻finishService

本窗口已经服务的顾客总数CustomerCount

本窗口的累计顾客等待时间totalCustomerWait

本窗口的最大顾客等待时间maxCustomerWait

本窗口的最大队列长度maxQlength

本窗口的累计服务时间totalService（3）数据的组织方法——采用队列 将未进门的顾客按将要进门的先后顺序入列到顾客流队列中 将已进门的顾客（进门事件）入列到最短窗口队列中 数据结构PPT：栈和队列全文共41页，当前为第34页。2023/6/1435仿真算法思路：（1）利用随机数发生器预先计算一天中达到银行的所有顾客，并将他们入列到顾客流队列CustomerFlow中。该功能由下述的CreateCustomerFlow()函数实现：

Queue<Event>CustomerFlow;//定义顾客流队列

voidCreateCustomerFlow()//创建顾客流队列

{ Evente=GetAEvent();//获取一事件（使用随机数发生器）

CustomerFlow.EnQueue(e);//将事件入列到顾客流队列中

}//上述的每一事件代表一个顾客（2）用一虚拟时钟VirtualTimer来模拟前述进门事件和服务完毕事件的发生。此处的虚拟时钟是一查询循环，每循环一次代表走过一个时间单位，用查询模拟随机的中断请求，从而实现用顺序执行模拟并发执行过程。该功能由下页的RunSimulation()函数实现。数据结构PPT：栈和队列全文共41页，当前为第35页。2023/6/1436仿真运行函数设计：若规定上班时间为StartTime,下班时间为EndTime，则查询循环结构如下：VoidRunSimulation()//{ for(intt=StartTime;t<EndTime;t++)//虚拟时钟

{ Evente=CustomerFlow.GetFront();//读取顾客流队列的队首

if(e.ArrivalTime==t)ArrivalEvent(); //发现一进门事件并作相应处理。

for(i=0;i<tellernum;i++)//查询各窗口有无服务完毕事件

{ e=Windowq[i].GetFront(); inttime=e.ArrivalTime+e.waitTime+e.serviceTime; if(t>=time)ServicedEvent(i); //发现窗口i有一服务完毕事件并作相应处理

} }}数据结构PPT：栈和队列全文共41页，当前为第36页。2023/6/1437进门事件处理函数Queue<Event>Windowq[tellernum];//共定义了tellernum个窗口队列VoidArrivalEvent()//进门事件处理{ Evente=CustomerFlow.DeQueue(); //将进门事件从顾客流队列中出列到事件变量e中

//下面程序段实现从所有窗口队列中选择一最短队列

//若长度都一样，则选择Windowq[0] intj=0; intminLength=Windowq[0].Length(); for(inti=1;i<tellernum;i++) { intL=Windowq[i].Length(); if(L<minLength) { j=i; minLength=L; } } 数据结构PPT：栈和队列全文共41页，当前为第37页。2023/6/1438 //改变窗口j的工作表

e.WaitTime=tstat[j].finishService-e.ArrivalTime;//计算等待时间

if(e.WaitTime<0){e.WaitTime=0;//窗口队列j为空队列 tstat[j].finishService=e.ArrivalTime+e.serviceTime;}//图2 elsetstat[j].finishService+=e.serviceTime;//图1 Windowq[j].EnQueue(e);//将进门事件入列到最短窗口队列中}e.ArrivalTime原tstat[j].finishService新tstat[j].finishService

时间图1

e.W