[理学]数据结构3第三章：栈和队列ppt课件

1、栈和队列栈和队列 数据构造数据构造栈的定义栈Stack：是一种操作受限的线性表。它是线性表的一个重要特例。栈中元素的进、出是按照后进先出的原那么进展的，这是栈构造的重要特征。因此，栈又称后进先出LIFOLast In First Out的线性表，简称为LIFO表 有关术语栈顶、栈底、进栈、出栈、空栈栈是限制仅在表的一端进展插入和删除运算的线性表。允许插入和删除的一端称为栈顶Top，即表尾。另一端称为栈底Bottom，即表头。向栈里放入一个元素，称为“进栈。从栈中取出一个元素，称为“出栈。当栈中没有元素时，称为“空栈。 栈的运算栈的根本运算：1置空栈SETNULLS2判栈空EMPTYS3进栈PU

2、SHS，x4退栈POSS5取栈顶TOPs6 重置空栈CLEARS栈有顺序存储和链接存储两种方式。栈的示意图栈的顺序存储构造顺序栈即栈的顺序存储构造，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素附设指针top指示栈顶元素在顺序栈中的位置。top=0时，表示栈空。每当插入一个新的栈顶元素，top增1；每当删除栈顶元素时，top减1。 图例顺序栈的定义 / 栈的顺序存储表示 #define STACK_INIT_SIZE 10 / 存储空间初始分配量 #define STACKINCREMENT 2 / 存储空间分配增量 struct SqStack SElemType *base;

3、/ 在栈构造之前和销毁之后，base的值为NULL SElemType *top; / 栈顶指针 int stacksize; / 当前已分配的存储空间，以元素为单位 ; / 顺序栈顺序栈存储构造顺序栈的根本操作Status InitStackSqStack &S / 构造一个空栈Sif!S.base=SElemType malloc S T A C K _ I N I T _ S I Z E * s i z e o fSElemType exitOVERFLOW; / 存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return O

4、K; 构造空栈图例顺序栈的根本操作 Status DestroyStackSqStack &S / 销毁栈S，S不再存在 freeS.base; S.base=NULL; S.top=NULL; S.stacksize=0; return OK; 销毁顺序栈图例顺序栈的根本操作Status ClearStackSqStack &S / 把S置为空栈 S.top=S.base; return OK; Status StackEmptySqStack S / 假设栈S为空栈，那么返回TRUE，否那么返FALSE ifS.top=S.base return TRUE; else re

5、turn FALSE; 顺序栈的根本操作 int StackLengthSqStack S / 返回S的元素个数，即栈的长度 return S.top-S.base; Status GetTopSqStack S,SElemType &e / 假设栈不空，那么用e返回S的栈顶元素，并返回OK；否那么返回ERROR ifS.topS.base e=*S.top-1; return OK; else return ERROR; 顺序栈的根本操作Status PushSqStack &S,SElemType e / 插入元素e为新的栈顶元素 ifS.top-S.base=S.stac

6、ksize/ 栈满，追加存储空间 S.base=SElemType *reallocS.base,S.stacksize+STACKINCREMENT*sizeofSElemType; if!S.base exitOVERFLOW; / 存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK; 进栈图例顺序栈的根本操作Status PopSqStack &S,SElemType &e / 假设栈不空，那么删除S的栈顶元素，用e返回其值，并返回OK；否那么返回ERROR

7、ifS.top=S.base return ERROR; e=*-S.top; return OK; 出栈图例栈的链式存储构造为什么使用链栈防止上溢错误、栈实际所用的最大空间是很难估计的、各个栈的实际容量在使用期是可变的。链栈栈的链式存储构造称为链栈,它是运算受限的单链表，它的插入和删除仅限制在表头位置上进展。栈顶指针就是链表的头指针，它唯一确定一个链栈。由于栈的操作是线性表操作的特例，故链栈的操作易于实现 链栈图例链栈图例链栈的根本操作 void pushnode *HS,int x / 在栈顶指针是HS的链栈中插入一个值为x的结点 node *s s=node malloc sizeofn

8、ode； s-date=x； s-next=HS； HS=s； 链栈的根本操作 int popnode *HS / 在栈顶指针是HS的链栈中取出一个结点 int x； node *p if HS= =NULL printf“向下溢出n； else x=HS-date； p=HS； HS=HS-next； freep； returnx； 链栈的根本操作 int semptnode *HS / 断定栈顶指针是HS的链栈是否为空 if HS= =NULL return1； else return0； 栈的应用举例 void conversion / 算法3.1 / 对于输入的任意一个非负十进制整数，

9、打印输出与其等值的八进制数 InitStacks; / 初始化栈scanf%d,&n; / 输入非负十进制整数n whilen / 当n不等于0 Pushs,n%8; / 入栈n除以8的余数8进制的低位 n=n/8; while!StackEmptys / 当栈不空 Pops,e; / 弹出栈顶元素且赋值给e printf%d,e; / 输出e 栈的应用举例void conversion / 对于输入的任意一个非负10进制整数，打印输出与其等值的16进制数 InitStacks; / 初始化栈 scanf%u,&n; / 输入非负十进制整数n whilen / 当n不等于0 P

10、ushs,n%16; / 入栈n除以16的余数16进制的低位 n=n/16; while!StackEmptys / 当栈不空 Pops,e; / 弹出栈顶元素且赋值给e ifenext=NULL; return OK; 空队列图例链队列的根本操作 Status DestroyQueueLinkQueue &Q / 销毁队列Q无论空否均可 whileQ.front Q.rear=Q.front-next; freeQ.front; Q.front=Q.rear; return OK; 销毁后的队列队列的根本操作 Status ClearQueueLinkQueue &Q / 将

11、Q清为空队列Q.rear=Q.front; p=Q.front-next; Q.front-next=NULL; whilep q=p; p=p-next; freeq; return OK; 队列的根本操作Status QueueEmptyLinkQueue Q / 假设Q为空队列,那么返回TRUE,否那么返回FALSE ifQ.front=Q.rear return TRUE; else return FALSE; 链队列的根本操作int QueueLengthLinkQueue Q / 求队列的长度 int i=0; QueuePtr p; p=Q.front; whileQ.rear!

12、=p i+; p=p-next; return i; 链队列的根本操作 Status EnQueueLinkQueue &Q,QElemType e / 插入元素e为Q的新的队尾元素 p=QueuePtrmallocsizeofQNode if!p exitOVERFLOW; / 存储分配失败 p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK; 链队列的根本操作Status DeQueueLinkQueue &Q,QElemType &e / 假设队列不空,删除Q的队头元素,用e返回其值ifQ.front

13、=Q.rear return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; ifQ.rear=p Q.rear=Q.front; freep; return OK; 顺序存储构造循环队列顺序队列出现假溢出的问题假如不考虑溢出，入队列操作可描绘如下：q.rear=q.rear+1； q.dataq.rear=x 出队运算描绘为：q.front=q.front+1 显然，当q.front=q.rear时，假设作出队操作，那么产生“下溢。当q.rear-q.front=m时，队满，再作入队操作也会引起“上溢。循环队列:为了进步运算的效率，

14、我们用另一种方法表达数组中各单元的位置关系。设想数组Q中的m个单元不是排成一行，而是围成一个圆环，即Q0接在Qm-1之后，形成一个闭合的环，这个意义下的队列叫做循环队列。 队列的假溢出循环队列示意图循环队列的定义 #define MAXQSIZE 5 / 最大队列长度对于循队列，最大队列长度要减1 struct S ueue QElemType *base; / 初始化的动态分配存储空间 int front; / 头指针,假设队列不空,指向队列头元素 int rear; / 尾指针,假设队列不空,指向队列尾元素的下一个位置 ; 队列的顺序存储构造循环队列的根本操作Status InitQueu

15、eS ueue &Q / 构造一个空队列Q Q.base=QElemType*m a l l o c M A X Q S I Z E * s i z e o fQElemType; if!Q.base / 存储分配失败 exitOVERFLOW; Q.front=Q.rear=0; return OK; 空队列图例循环队列的根本操作int QueueLengthS ueue Q / 返回Q的元素个数,即队列的长度 returnQ.rear-Q.front+MAXQSIZE%MAXQSIZE; Status GetHeadS ueue Q,QElemType &e / 假设队列不

16、空,那么用e返回Q的队头元素,并返回OK,否那么返回ERROR ifQ.front=Q.rear / 队列空 return ERROR; e=*Q.base+Q.front; return OK; 循环队列的根本操作Status EnQueueS ueue &Q,QElemType e / 插入元素e为Q的新的队尾元素 ifQ.rear+1%MAXQSIZE=Q.front / 队列满 return ERROR; Q.baseQ.rear=e; Q.rear=Q.rear+1%MAXQSIZE; return OK; 入队操作循环队列的根本操作 Status DeQueueS ueue

17、 &Q,QElemType &e / 假设队列不空,那么删除Q的队头元素,用e返回其值,并返回OK;否那么返回ERROR ifQ.front=Q.rear / 队列空 return ERROR; e=Q.baseQ.front; Q.front=Q.front+1%MAXQSIZE; return OK; 循环队列出队操作循环队列的根本操作 Status DestroyQueueS ueue &Q / 销毁队列Q,Q不再存在 ifQ.base freeQ.base; Q.base=NULL; Q.front=Q.rear=0; return OK; 销毁队列图例实习题一

18、 栈、队列的算法设计本次实习的目的在于深化理解栈和队列的特性，以便在实际问题背景下灵敏运用它们。 1.停车场管理 根本描绘 设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列大门在最南端，最先到达的第一辆车停放在车场的最北端，假设车场内已停满n辆汽车，那么后来的汽车只能在门外的便道上等候，一旦有车开走，那么排在便道上的第一辆车即可开入；当停车场内某车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它分开停车场时，必须按它停留的时间长短缴纳费用，试为停车场编制按上述要求进展管理的模拟程序。 根本要求 以栈模

19、拟停车场，以队列模拟车场外的通道，按照从终端读八的输入数据序列进展模拟管理。每一组输入数据包括三个数据项的汽车“到达或“离去信息，汽车牌照码及到达或离去的时刻，对每一组输入数据进展操作后的输出数据为：假设是车辆离去，那么输出汽车在停车场内停留的时间和应交纳的费用在便道上停留时间不收费。栈以顺序构造实现，队列以链表构造实现。 测试数据 设n=2，输入数据为： A,1,5, A,2,10, D,1,15, A,3,20, A,4,25, A,5,30, D,2,35,D,4,10,E,0,0, 其中，A表示到达，D表示，E表示输入完毕。实习题二 2.车辆调度 问题描绘 假设停在铁路调度站，如课本3.1所示，入D处车厢序列的编号依次为1,2,3, n。设计一个程序，求出所有可能由此输出的长度为