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

栈和队列,主讲教师：李长云 班 级：信息系 教 室：多媒体,数据结构,栈的定义,栈（Stack）： 是一种操作受限的线性表。它是线性表的一个重要特例。栈中元素的进、出是按照后进先出的原则进行的，这是栈结构的重要特征。因此，栈又称后进先出（LIFOLast In First Out）的线性表，简称为LIFO表 有关术语 栈顶、栈底、进栈、出栈、空栈 栈是限制仅在表的一端进行插入和删除运算的线性表。允许插入和删除的一端称为栈顶（Top），即表尾。另一端称为栈底（Bottom），即表头。向栈里放入一个元素，称为“进栈”。从栈中取出一个元素，称为“出栈”。当栈中没有元素时，称为“空栈”。,栈的运算,栈的基本运算： （1）置空栈SETNULL(S) （2）判栈空EMPTY（S） （3）进栈PUSH（S，x） （4）退栈POS（S） （5）取栈顶TOP（s） （6） 重置空栈CLEAR（S） 栈有顺序存储和链接存储两种方式。,栈的示意图,栈的顺序存储结构,顺序栈即栈的顺序存储结构，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 附设指针top指示栈顶元素在顺序栈中的位置。top=0时，表示栈空。 每当插入一个新的栈顶元素，top增1；每当删除栈顶元素时，top减1。,图例,顺序栈的定义,/ 栈的顺序存储表示 #define STACK_INIT_SIZE 10 / 存储空间初始分配量 #define STACKINCREMENT 2 / 存储空间分配增量 struct SqStack SElemType *base; / 在栈构造之前和销毁之后，base的值为NULL SElemType *top; / 栈顶指针 int stacksize; / 当前已分配的存储空间，以元素为单位 ; / 顺序栈,顺序栈存储结构,顺序栈的基本操作,Status InitStack(SqStack ,构造空栈图例,顺序栈的基本操作,Status DestroyStack(SqStack ,销毁顺序栈图例,顺序栈的基本操作,Status ClearStack(SqStack ,顺序栈的基本操作,int StackLength(SqStack S) / 返回S的元素个数，即栈的长度 return S.top-S.base; Status GetTop(SqStack S,SElemType ,顺序栈的基本操作,Status Push(SqStack ,进栈图例,顺序栈的基本操作,Status Pop(SqStack ,出栈图例,栈的链式存储结构,为什么使用链栈 防止上溢错误、栈实际所用的最大空间是很难估计的、各个栈的实际容量在使用期是可变的。 链栈 栈的链式存储结构称为链栈,它是运算受限的单链表，它的插入和删除仅限制在表头位置上进行。栈顶指针就是链表的头指针，它唯一确定一个链栈。由于栈的操作是线性表操作的特例，故链栈的操作易于实现,链栈图例,链栈图例,链栈的基本操作,void push(node *HS,int x) / 在栈顶指针是HS的链栈中插入一个值为x的结点 node *s s=(node )malloc (sizeof(node)； s-date=x； s-next=HS； HS=s； ,链栈的基本操作,int pop(node *HS )/ 在栈顶指针是HS的链栈中取出一个结点 int x； node *p if (HS= =NULL) printf(“向下溢出n”)； else x=HS-date； p=HS； HS=HS-next； free(p)； return(x)； ,链栈的基本操作,int sempt(node *HS ) / 判定栈顶指针是HS的链栈是否为空 if (HS= =NULL) return(1)； else return(0)； ,栈的应用举例,void conversion() / 算法3.1 / 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 InitStack(s); / 初始化栈 scanf(“%d“, / 输出e ,栈的应用举例,void conversion() / 对于输入的任意一个非负10进制整数，打印输出与其等值的16进制数 InitStack(s); / 初始化栈 scanf(“%u“, ,栈的应用举例,Void lineEdit() /行编辑算法描述,利用字符栈s,从终端接收一行并传送至调用过程的数据区 Setnull(s)； / 构造空栈s ch = getchar( )；/从终端接收第一个字符 while (ch! = EOF)/EOF为全文结束符 while (ch ! = EOF break；/重置s为空栈 default：Push(S,c)；break； ch = getchar( )； /从终端接收下一个字符 clearStack(s)； /重置s为空栈 if (ch ! = EOF) ch = getchar( )；,队列的定义及其运算,队列（Queue）:也是一种特殊的线性表，它只允许在表的一端进行插入而在另一端进行删除。通常又把队列叫做先进先出（FIFOFist In Fist Out）表。 有关术语 允许删除的一端称队头（Front），允许插入的一端称队尾（Rear）。队列（Queue）也是一种特殊的线性表，它只允许在表的一端进行插入而在另一端进行删除。 队列的基本运算： （1）置空队列SETNULL（Q） （2）判队列EMPTY（Q） （3）入队列ENQUEUE（Q，X） （4）出队列DEQUEUE（Q） （5）取队头FRONT（Q）,链队列,链队列 链式存储结构简称链队列，对于使用中数据元素变动较大数据结构，用链式存储结构比顺序结构更有利。 链队列的特点 链队列它是限制仅在表头删除和表尾插入的单链表。为了便于单链表的头指针在表尾做插入操作。再设置一个尾指针，指向链表上的最后一个结点。于是，一个链队列由一个头指针和一个尾指针唯一确定。其中队首指针first指向单链表的表头，队尾指针rear指向单链表的表尾。,图 例,单链队列的定义,单链队列队列的链式存储结构 typedef struct QNode QElemType data; QNode *next; *QueuePtr; struct LinkQueue QueuePtr front,rear; / 队头、队尾指针 ;,单链队列图例,链队列,链队列图例,链队列的基本操作,Status InitQueue(LinkQueue ,空队列图例,链队列的基本操作,Status DestroyQueue(LinkQueue ,销毁后的队列,队列的基本操作,Status ClearQueue(LinkQueue ,队列的基本操作,Status QueueEmpty(LinkQueue Q) / 若Q为空队列,则返回TRUE,否则返回FALSE if(Q.front=Q.rear) return TRUE; else return FALSE; ,链队列的基本操作,int QueueLength(LinkQueue Q) / 求队列的长度 int i=0; QueuePtr p; p=Q.front; while(Q.rear!=p) i+; p=p-next; return i; ,链队列的基本操作,Status EnQueue(LinkQueue ,链队列的基本操作,Status DeQueue(LinkQueue ,顺序存储结构循环队列,顺序队列出现假溢出的问题 如果不考虑溢出，入队列操作可描述如下： q.rear=q.rear+1； q.dataq.rear=x 出队运算描述为： q.front=q.front+1 显然，当q.front=q.rear时，若作出队操作，则产生“下溢”。当q.rear-q.front=m时，队满，再作入队操作也会引起“上溢”。 循环队列:为了提高运算的效率，我们用另一种方法表达数组中各单元的位置关系。设想数组Q中的m个单元不是排成一行，而是围成一个圆环，即Q0接在Qm-1之后，形成一个闭合的环，这个意义下的队列叫做循环队列。,队列的假溢出,循环队列示意图,循环队列的定义,#define MAXQSIZE 5 / 最大队列长度(对于循队列，最大队列长度要减1) struct SqQueue QElemType *base; / 初始化的动态分配存储空间 int front; / 头指针,若队列不空,指向队列头元素 int rear; / 尾指针,若队列不空,指向队列尾元素的下一个位置 ;,队列的顺序存储结构,循环队列的基本操作,Status InitQueue(SqQueue ,空队列图例,循环队列的基本操作,int QueueLength(SqQueue Q) / 返回Q的元素个数,即队列的长度 return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; Status GetHead(SqQueue Q,QElemType ,循环队列的基本操作,Status EnQueue(SqQueue ,入队操作,循环队列的基本操作,Status DeQueue(SqQueue ,循环队列出队操作,循环队列的基本操作,Status DestroyQueue(SqQueue ,销毁队列图例,实习题（一）,栈、队列的算法设计 本次实习的目的在于深入了解栈和队列的特性，以便在实际问题背景下灵活运用它们。 1.停车场管理 基本描述 设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时，必须按它停留的时间长短缴纳费用，试为停车场编制按上述要求进行管理的模拟程序。,基本要求 以栈模拟停车场，以队列模拟车场外的通道，按照从终端读八的输入数据序列进行模拟管理。每一组输入数据包括三个数据项的汽车“到达”或“离去”信息，汽车牌照码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留时间不收费）。栈以顺序结构实现，队列以链表结构实现。 测试数据 设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。设计一个程序，求出所有可能由此输出的长度为n的车厢序列。 基本要求 首先在课本第3.1.2节中提供的栈的顺序存储结构之上实现的五种基本运算。除了栈初始化操作之外，都要按函数实现。Push(s,x)是一个布尔函数，当且仅当栈S上溢时返回“假”值，再说明一个date型的常量是datetype操作。pop(s)和top(s)遇到S为空的情况时，返回值为空元素NLLL。 程序对栈的任何存取（即更改，读取和状态判别等操作）必须借助于基本运算进行。 测试数据 分别取n=1,2,3,和4,复习思考题,1.什么是“栈”？什么叫“出栈”和“进栈”？ 2.设有一个栈，元素进栈的次序为A，B，C。试问能否得到下列操作序列？若不能，请说明原因。 （1）A，B，C （2）A，C，B （3）B，A，C （4）B，C，A （5）C，B，A （6）C，A，B 3.按照表达式运算优先级，画出对下列算术表达式求值时，操作数栈和运算符栈的变化过程。A-B*C/D+EE 4.设两个栈共享向量空间C（1