（一）循环队列
来源：程序员人生 发布时间：2015-03-23 08:22:41 阅读次数：3306次
队列可使用数组或链表实现，这里介绍1种使用数组实现的循环队列。
所谓循环队列，是指当尾指针超过数组索引界限时，通过取余运算返回数组起始端，只要保证尾指针和头指针不相遇，就能够继续存储元素。
首先设定队列的大小，并建立队列结构体：
#define MAXSIZE 100001
typedef struct {
int items[MAXSIZE];
int front;
int rear;
}Queue;
设头指针和尾指针指向同1索引时队列为空，起始时均在索引0处。
void initQueue(Queue *q){
q->front = q->rear = 0;
}
入队操作是先检查rear指针前进后是不是会和front指针相遇，如果会相遇则直接返回，并输出毛病：队列已满。
注意要对MAXSIZE取余，实现循环：
void AddQ(Queue *q, int item){
if ((q->rear + 1)%MAXSIZE == q->front)
{
// 为了辨别空队列与满队列，必须保证rear和front不能再次碰面，因此要留出1个距离，提早判断是不是添加后front=rear。
printf("队列满");
return;
}
q->rear = (q->rear + 1) % MAXSIZE;
*(q->items + q->rear) = item;
}
出队操作是先检查front和rear是不是相等，否则队列为空，如果不空，则先将front后移，然后将front位置的元素返回：
int DeleteQ(Queue *q){
if (q->rear == q->front)
{
printf("队列空");
return NULL;
}
q->front = (q->front + 1) % MAXSIZE;
return *(q->items + q->front);
}
注意入队是先判断后移是不是相遇来判断是不是为满再履行操作，操作方法为指针后移然后在指针处存入元素；出队时是先判断是不是相遇来判断是不是为空，操作方法为指针后移然后在指针处存入元素。
在先移动指针再操作指针处元素、rear和front相等为空这两个约定下，可以实现循环队列。
完全代码为：
#define MAXSIZE 100001
typedef struct {
int items[MAXSIZE];
int front;
int rear;
}Queue;
void initQueue(Queue *q){
q->front = q->rear = 0;
}
bool isEmpty(Queue *q){
return q->front == q->rear;
}
void AddQ(Queue *q, int item){
if ((q->rear + 1)%MAXSIZE == q->front)
{
// 为了辨别空队列与满队列，必须保证rear和front不能再次碰面，因此要留出1个距离，提早判断是不是添加后front=rear。
printf("队列满");
return;
}
q->rear = (q->rear + 1) % MAXSIZE;
*(q->items + q->rear) = item;
}
int DeleteQ(Queue *q){
if (q->rear == q->front)
{
printf("队列空");
return NULL;
}
q->front = (q->front + 1) % MAXSIZE;
return *(q->items + q->front);
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
