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

* * 数据结构 3.1 栈及其应用 第三章 栈和队列 3.2 队列及其应用 3.3 链栈与链队列 3.2 队列及其应用 队列(queue)简称队，是一种只允许在表的一端进行插入操作, 而在表的另一端进行删除操作的线性表。 一. 队列的定义 a1 a2 a3 a4 a5 3.2 队列及其应用 队列(queue)简称队，是一种只允许在表的一端进行插入操作, 而在表的另一端进行删除操作的线性表。 一. 队列的定义 a1 a2 a3 a4 a5 设（a1,a2 , a3 , ... , an ）为一队列 ①允许插入的一端称作队尾，允许删除的一端称为队头；则a1为队头元素，an为队尾元素； 说明 队头元素 队尾元素 3.2 队列及其应用 队列(queue)简称队，是一种只允许在表的一端进行插入操作, 而在表的另一端进行删除操作的线性表。 一. 队列的定义 a1 a2 a3 a4 a5 设（a1,a2 , a3 , ... , an ）为一队列 ②在表尾插入元素的操作，称为入队操作；在表头删除元素的操作，称为出队操作； 说明 入队 出队 a6 a1 3.2 队列及其应用 队列(queue)简称队，是一种只允许在表的一端进行插入操作, 而在表的另一端进行删除操作的线性表。 一. 队列的定义 a1 a2 a3 a4 a5 设（a1,a2 , a3 , ... , an ）为一队列 ③队列具有先进先出的特点，所以又称为先进先出表（FIFO表） 说明 【火车车厢重排问题 】 问题描述：一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只需卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列他们。 车厢的重排工作可以通过转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。设计算法解决火车车厢重排问题。 入轨 出轨 581742963 987654321 H3 H1 H2 入轨 出轨 581742963 987654321 H1 H2 H3 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； ?队列的基本操作 二. 队列的顺序存储结构 #define QUEUE_INIT_SIZE 100 // 存储空间初始分配量 #define QUEUE_INCREAMENT 2 // 分配增量typedef struct{ QElemType *base; //存储数据元素的数组 int rear; //尾指针，指向队尾元素的下一个位置 int queuesize;//当前分配的存储容量 }SqQueue1; 1．类型定义方法一 注：队头元素总在[0]单元 SqQueue1 queuesize rear base 如何改进出队的时间性能？ 0 1 2 3 4 入队 出队 例：a1a2a3a4依次入队 a1 a2 a3 a4 Q.rear Q.rear Q.rear Q.rear 入队操作时间性能为O(1) 二. 队列的顺序存储结构 Q.rear Q.base 0 1 2 3 4 入队 出队 例：a1a2依次出队 a1 a2 a3 a4 Q.rear 二. 队列的顺序存储结构 Q.base 例：a1a2依次出队 二. 队列的顺序存储结构 0 1 2 3 4 入队 出队 Q.base a2 a3 a4 Q.rear 0 1