数据结构第三章栈和队列.pptxVIP

数据结构

3.1栈及其应用第三章栈和队列3.2队列及其应用3.3链栈与链队列

3.2队列及其应用队列(queue)简称队，是一种只允许在表的一端进行插入操作,而在表的另一端进行删除操作的线性表。一.队列的定义a1a2a3a4a5

3.2队列及其应用队列(queue)简称队，是一种只允许在表的一端进行插入操作,而在表的另一端进行删除操作的线性表。一.队列的定义a1a2a3a4a5设（a1,a2,a3,...,an）为一队列

①允许插入的一端称作队尾，允许删除的一端称为队头；则a1为队头元素，an为队尾元素；说明队头元素队尾元素

3.2队列及其应用队列(queue)简称队，是一种只允许在表的一端进行插入操作,而在表的另一端进行删除操作的线性表。一.队列的定义a1a2a3a4a5设（a1,a2,a3,...,an）为一队列

②在表尾插入元素的操作，称为入队操作；在表头删除元素的操作，称为出队操作；说明入队出队a6a1

3.2队列及其应用队列(queue)简称队，是一种只允许在表的一端进行插入操作,而在表的另一端进行删除操作的线性表。一.队列的定义a1a2a3a4a5设（a1,a2,a3,...,an）为一队列

③队列具有先进先出的特点，所以又称为先进先出表（FIFO表）说明

【火车车厢重排问题】问题描述：一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只需卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列他们。车厢的重排工作可以通过转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。设计算法解决火车车厢重排问题。入轨出轨581742963987654321H3H1H2入轨出轨581742963987654321H1H2H3

?队列的基本操作1）初始化操作InitQueue(Q)

功能：构造一个空队列Q；

2）销毁操作DestroyQueue(Q)

功能：销毁已存在队列Q；

3）置空操作ClearQueue(Q)功能：将队列Q置为空队列；4）判空操作QueueEmpty(Q)功能：若队列Q为空，则返回True，否则返回False；

5）取队头元素操作GetHead(Q,e)

功能：取队头元素，并用e返回；

6）入队操作EnQueue(Q,e)

功能：将元素e插入Q的队尾；

7）出队操作DeQueue(Q,e)

功能：若队列不空，则删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR；

二.队列的顺序存储结构#defineQUEUE_INIT_SIZE100//存储空间初始分配量#defineQUEUE_INCREAMENT2//分配增量

typedefstruct{

QElemType*base;//存储数据元素的数组

intrear;//尾指针，指向队尾元素的下一个位置intqueuesize;//当前分配的存储容量}SqQueue1;1．类型定义方法一注：队头元素总在[0]单元SqQueue1baserearqueuesize如何改进出队的时间性能？

二.队列的顺序存储结构01234入队出队例：a1a2a3a4依次入队a1a2a3a4Q.rearQ.rearQ.rearQ.rear入队操作时间性能为O(1)Q.rearQ.base

二.队列的顺序存储结构01234入队出队例：a1a2依次出队a1a2a3a4Q.rearQ.base

二.队列的顺序存储结构例：a1a2依次出队01234入队出队Q.basea2a3a4Q.rear

二.队列的顺序存储结构01234入队出队例：a1a2依次出队a2a3a4Q.rearQ.base

二.队列的顺序存储结构例：a1a2依次出队0123