据结构C语言版(栈和队列).pptVIP

3.2.2 队列的顺序存储 队列的顺序存储结构如下图3-6所示： 图 3-6 * 问题1：当队空时，队头和队尾指针都为-1，队列将处于下图3-7所示的状态： 图 3-7 * 此时若进行入队操作，就需要让队头和队尾指针都增1，再将新数据元素放入该位置。也就是说，这样设置队头、队尾指针位置，在进行入队操作时，空队与非空队状态所需要执行的操作不完全一样。 解决方法：在算法中，需要对这两种情况加以区分，这势必增加了算法的复杂性。因此，人们设想了一种解决方法，即让队头指针指向队列真正队头元素的前一个位置，如下图3-8所示。 * 图 3-8 * 问题2：由于顺序存储结构的存储空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余单元的情况。对于队列来说，这一点又有它的特殊性。下面我们讨论一下下图3-10所示的队列。 图 3-10 * “假溢出”现象。 解决方法：将存储队列元素的一维数组首尾相接，形成一个环状。如图3-11所示。我们将这种形式表示的队列称之为循环队列。 * a8 a7 a6 a5 7 6 5 4 3 2 1 0 rear front 图 3-11 * 假设为队列开辟的数组单元数目为MAX_QUEUE，在C语言中，它的下标在0~MAX_QUEUE-1之间，若增加队头或队尾指针，可以利用取模运算（一个整数数值整除以另一个整数数值的余数）实现。如下所示： front=(front+1)%MAX_QUEUE； rear=(rear+1)%MAX_QUEUE； 当front或rear为MAXQUEUE-1时，上述两个公式计算的结果就为0。这样，就使得指针自动由后面转到前面，形成循环的效果。 队空和队满的标志问题： 队列变为空，队头和队尾指针相等。 * a7 a8 7 6 5 4 3 2 1 0 rear front 7 6 5 4 3 2 1 0 rear front (a) (b) 图 3-12 队列变为满，队头和队尾指针也相等。 * rear front a6 a5 a4 a3 a1 a2 7 6 5 4 3 2 1 0 a6 a5 a4 a3 a1 a2 a8 a7 7 6 5 4 3 2 1 0 rear front (a) (b) 图 3-13 * 解决方法：一是为队列另设一个标志，用来区分队列是“空”还是“满”；二是当数组只剩下一个单元时就认为队满，此时，队尾指针只差一步追上队头指针，即：(rear+1)%MAX_QUEUE==front。 类型定义： #define MAX_QUEUE 10 //队列的最大数据元素数目 typedef struct queue{ //假设当数组只剩下一个单元时认为队满 QueueEntry item[MAX_QUEUE]; //存放队列中数据元素的存储单元 int front,rear; //队头指针、队尾指针 }QUEUE; * 各项基本操作算法。 （1）初始化队列Q void InitQueue(QUEUE *Q) { Q-front=-1; Q-rear=-1; } * （2）入队 void EnQueue(QUEUE *Q,QueueEntry item) { if ((Q-rear+1)%MAX_QUEUE==Q-front) exit(OVERFLOW); else { Q-rear=(Q-rear+1)%MAX_QUEUE; Q-item[Q-rear]=item; } } * （3）出队 void DeQueue(QUEUE*Q,QueueEntry *item) { if (QueueEmpty(*Q)) exit(“Queue is empty.”); else { Q-front=(Q-front+1)%MAX_QUEUE; *item=Q-item[Q-front]; } } * （4）获取队头元素内容 void GetFront(QUEUE