314 队列队头、队尾指针指向不同位置的区别

众说周知，在队列的题目中，队头指针 (front) 和队尾指针 (rear) 有两种指示方法。

1. 队头指针 a. 指向队头元素 b. 指向队头元素的前一个位置
2. 队尾指针 a. 指向队尾元素 b. 指向队尾元素的后一个位置 指示方法不同元素入队和出队操作也不同，但是在做大部分题目的时候，我们并不需要分析队头指针和队尾指针具体操作，我们只要记住下面两个结论就行

结论

1. 结论一：当队列执行元素入队操作时，队尾指针（rear）向后移 (rear++)，队头指针（front）不变
2. 结论二：当队列执行元素出队操作时，队头指针（front）向后移 (front++)，队尾指针（rear）不变

实战

例 1

若用数组 $A[\mathrm{0...5}]$ 来实现循环队列，且当前 rear 和 front 的值分别是 1 和 5，当从队列中删除一个元素，再加入两个元素，rear 和 front 指针的值分别为

根据结论一，队列中删除一个元素就是进行元素出队操作，所以 front 指针后移，rear 指针不变，由于是循环队列所以 front 指针往后移值为 0

根据结论二，队列中加入元素就是进行元素入队操作，所以 rear 指针后移，front 指针不变，两次就是 rear 指针后移两步，1→2→3，所以 rear 指针值为 3

例 2

【2011 统考真题】已知循环队列存储一维数组 $A[\mathrm{0...}n-1]$ 中，且队列非空时 front 和 rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存储在 $A[0]$ 处，则初始时 front 和 rear 的值分别是

我们假设元素已存入 $A[0]$ 中，那么根据题意队列非空时 front 和 rear 分别指向队头元素和队尾元素，front 和 rear 都为 0。由于元素入队的时候只有 rear 指针后移，我们把 rear 指针回退到元素入队之前的情况，由于是循环队列，所以 0 前面就是 n-1，元素入队时 front 指针不变。

所以初始时 front 指向 0，rear 指向 n-1

例 3

【2014 统考真题】循环队列放在一维数组 $A[\mathrm{0...}M-1]$ 中，end1 指向队头元素，end2 指向队尾元素后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳 $M-1$ 个元素。初始时为空。则判断队空和对满的条件为

我们假设在一个空队列中将一个元素入队，存在 $A[0]$ 中，那么根据题意此时 end1 的值为 0，end2 的值为 1，模仿上一题的回退思路，end2 回退，所以队空的时候 end1 和 end2 的值均为 0，所以队空的判断条件为 end1==end2;

因为队列中最多容纳 $M-1$ 个元素，有一个空间空出来，所以队满的时候，end1 指向队头元素（它前面就是空出来的位置），end2 指向队尾元素后一个位置，就是空出来的位置，所以判断条件为 end1==(end2+1)%M;