数据结构第三章栈和队列.pptx
数据结构
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