在这里我先强调几点概念:
1、在非空队列中,头指针始终指向队列头元素,而尾指针始终指向队列尾元素的下一个位置。
2、在单队列中我们判断队列是否为空的条件是:Q.front==Q.rear;而在循环队列中只凭等式Q.front==Q.rear是无法判别队列是“空”还是“满”;可有两种处理方法:其一是另设一个标志位一区别队列是“空”还是“满”;其二是少用一个元素空间,约定以“队列头指针在队列尾指针的下一位置(置换的下一位置)上”作为队列呈“满”状态的标志,即(Q.rear+1)%MAXQSIZE == Q.front.
队列结构的实现:
#include <stdio.h>#include <malloc.h>typedef int QElemType;typedef int Status;#define MaxQSize 10#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -1typedef struct{QElemType *base;int front, rear;}SqQueue;//初始化循环队列Status InitQueue(SqQueue &Q){Q.base = (QElemType*)malloc(MaxQSize*sizeof(QElemType));if (Q.base == NULL){puts("分配内存空间失败!"); exit(OVERFLOW);}Q.front = Q.rear = 0;return 0;}//将循环队列清空Status ClearQueue(SqQueue &Q){Q.front = Q.rear = 0;}//求队列元素的个数Status QueueLength(SqQueue Q){return (Q.rear - Q.front + MaxQSize) % MaxQSize;}//插入元素到循环队列Status EnSqQueue(SqQueue &Q, QElemType e){if ((Q.rear + 1) % MaxQSize == Q.front){puts("队列已满!"); return ERROR; /*队列满*/}Q.base[Q.rear] = e; //元素e入队Q.rear = (Q.rear + 1) % MaxQSize; //修改队尾指针return OK;}//从循环队列中删除元素Status DeSqQueue(SqQueue &Q, QElemType &e){if (Q.front == Q.rear)return ERROR;e = Q.base[Q.front]; //取队头元素至eQ.front = (Q.front + 1) % MaxQSize; //修改队头指针,如果超内存,循环 return OK;}//判断一个循环队列是否为空队列Status isQueueEmpty(SqQueue Q){if (Q.front == Q.rear)return TRUE;elsereturn FALSE;}
测试代码:
int main(){int i, e;SqQueue Q;InitQueue(Q);for (i=0; i<MaxQSize; i++)//只有MaxQSize个数据进队列EnSqQueue(Q, i);i = QueueLength(Q);printf("队列里的元素有%d个\n", i);for (i=0; i<3; i++){DeSqQueue(Q, e);printf("%d ", e);}printf("\n");i = QueueLength(Q);printf("队列里的元素有%d个\n", i);for (i=10; i<12; i++)EnSqQueue(Q, i);i = QueueLength(Q);printf("队列里的元素有%d个\n", i);ClearQueue(Q);i = QueueLength(Q);printf("队列里的元素有%d个\n", i);return 0;}
运行结果: