第2章-4 队列精要.ppt

* * 2.2 栈和队列 * * 2.2.2 队列(Queue) 定义 队列是只允许在一端删除，在另一端插入的线性表。 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特性：先进先出(First In First Out:FIFO) 逻辑示意图 a1 a2 …… an 入队列 出队列 队尾rear 队头front * * 队列的基本概念 队头（front):允许删除(出队)的一端。 front指向队头元素的前一个位置 队尾（rear):允许插入(入队)的一端。 Rear指向队尾元素 空队列：队列中没有元素。 进队：队列的插入运算，插入对尾元素。 出队：队列的删除运算，删除队首元素。 * * 入队出队的示意图 * * 队列的入队出队 进队时 队尾指针先加1：rear = rear + 1； 再将新元素按rear指示位置加入。 出队时 队头指针先加1：front = front + 1； 再将下标为front的元素取出。 队满时再进队将溢出出错(错误的情况)；队空时再出队将以队空处理(程序控制转向的条件)。 * * 队列的基本运算 入队 出队 取队头元素 置空队列 判队列是否为空 在不同的存储方式下，实现上述运算的方法和过程是不同的。 * * 队列的顺序存储结构—顺序队列 顺序队列： 队列的顺序存储结构，用一组连续的存储单元依次存放队列中的元素。 顺序队列的类型说明： typedef struct queue { elemtype data[MaxSize]; int f,r; //队首 队尾 }sequeue; * * 顺序队列运算时的头、尾指针变化 Sq-f 3 2 1 0 空队列 Sq-r 3 2 1 0 A、B相继入队 Sq-r Sq-f A B 3 2 1 0 A、B相继出队 Sq-r Sq-f 3 2 1 0 C、D相继入队 Sq-r Sq-f C D * * 指针变化的小结 队头指针：f总指向当前队头元素的前一个位置。 队尾指针：r指向当前队尾元素的位置。 初始(空)状态：f=r=-1 操作过程中空：f = r ? -1 入队运算： sq-r++; //尾指针加1 sq-data[sq-r]=x; //x入队 出队运算：sq-f++; //头指针加1 * * 指针变化的小结 队列长度：(sq-r)-(sq-f) 队空：(sq-r)=(sq-f) 下溢：队空时再作出队操作。 队满：(sq-r)-(sq-f)= m 上溢：队满时再作入队操作。 当sq-r = MaxSize – 1时：队列可能为满，也可能不满！ * * 指针变化的小结 队上溢： 真上溢（r-f = m)：队列真正满时再入队。 假上溢：r已指向队尾，但队列前端仍有空位置。 解决假上溢的方法： 方法一：每次删除队头一个元素后，把整个队列往前移一个位置（造成时间浪费）。 方法二：循环队列 * * 循环队列 将所用的数组sq-data[m]设想为首尾相接的循环数组（即：data[0]连在data[m-1]之后)。 f a0 an …… r 0 MaxSize-1 …… * * 循环队列 循环意义下的队列入队： 若尾指针r等于向量的上界，再入队，令尾指针等于向量的下界,即：在循环意义下的尾指针的加1操作可描述为： If(sq-r+1 = Maxsize-1) sq-r=0; else sq-r++; 利用“模运算”，则下述运算可描述为： 入队：sq-r=(sq-r+1)%m 出队：sq-f=(sq-f+1)%m 队空：sq-r=(sq-f) 队满：(sq-r+1）%m=sq-f * * 循环队列 初始状态：空队列 sq-f = sq-r = MaxSize–1; 操作过程中队列空： Sq-f = sq-r; f a0 ai …… r 0 MaxSize-1 …… an-1 在右图中，再入队一个元素,下式将成立： sq-r = sq-f表示队列满 …… * * 循环队列队满队空 为了解决 f = r是队空队满的问题，有规定如下： 队尾指针追上头指针作为队满标志，即： sq-f = sq-r +1 队尾等于队头指针作为队空标志，即： sq-f = sq-r 在上述规定下，当队满时，尚有一个空单元。 * * 循环队列队满队空 考虑到循环队列的指针翻转，队空队满的完整条件如下： 队空：sq-f == sq-r; 队满：sq-f == (sq-r + 1)%MaxSize; 或者： 队空:(sq-f - sq-r)%MaxSize = 0; 队满:(sq-f - sq-r)%MaxSize = 1; 另一种方法： 用