队列的概念2.pptVIP

队列 ( Queue ) 定义 队列是只允许在一端删除，在另一端插入的线性表 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特点 先进先出(FIFO, First In First Out) 队列的主要操作 入队（EnQueue） 出队（DeQueue ） 队列的存储表示 顺序存储—循环队列 链式存储—链队列 循环队列 (Circular Queue) 队列存放数组被当作首尾相接的表处理； 队头、队尾指针加1时从maxSize -1直接进到0，可用C语言的取模(余数)运算实现； 队头指针加1: front = (front+1) % maxSize; 队尾指针加1: rear = (rear+1) % maxSize; 队列初始化：front = rear = 0; 队空条件：front == rear; 队满条件：(rear+1) % maxSize == front 队列的链式表示 — 链队列 队头在链头，队尾在链尾。 链式队列在入队时无队满问题，但有队空问题。 队空条件为 Q.front == NULL 优先级队列 (Priority Queue) 优先级队列 每次从队列中取出的是具有最高优先权的元素 如下表：任务优先权及执行顺序的关系 * a0 a1 a2 an-1 front rear ?? 顺序队列的入队和出队 front rear 空队列 front rear A入队 A front rear B入队 A B front rear C, D入队 A B C D front rear A出队 B C D front rear B出队 C D front rear E,F,G入队 C D E F G C D E F G front rear H入队,溢出 队列的入队和出队原则 入队时将新元素按 rear 指示位置加入队 尾，再将队尾指针加1 rear = rear + 1； 出队时先将下标为 front 的元素取出，再 将队头指针加1 front = front + 1； 队满时再入队将溢出出错； 队空时再出队将队空处理。 解决办法之一：将队列元素存放数组首尾 相接，形成循环(环形)队列。 0 1 2 3 4 5 6 7 front 0 1 2 3 4 5 6 7 front 0 1 2 3 4 5 6 7 front rear A A B C rear rear 空队列 A入队 B, C入队 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 A出队 B出队 0 1 2 3 4 5 6 7 D,E,F,G,H入队 B C rear A front B C rear front C rear D E F G H front ^ data next … 队尾 队头 Q.front Q.rear Q.front Q.rear ∧ 空队列 Q.front Q.rear Q.front Q.rear Q.front Q.rear X ∧ Y ∧ X Y ∧ X 元素X入队列 元素Y入队列 元素X出队列 队列的应用举例 — 逐行打印 二项展开式 (a + b)i 的系数 分析第 i 行元素与第 i+1行元素的关系 从前一行的数据可以计算下一行的数据 i = 2 i = 3 i = 4 0 1 3 3 1 0 1 4 6 4 1 0 1 2 1 0 0 1 1 0 s t s+t 从第 i 行数据计算并存放第 i+1 行数据 1 2 1 0 1 3 3 1 0 1 4 6 s=0 t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1 s+t s=t s=t s=t s=t s=t s=t s=t s=t s+t s+t s+t s+t s+t s+t s+t s+t 数字越小，优先权越高 *