循环队列

为了解决顺序队列中的“假溢出”现象，充分利用数组的存储空间，可将顺序队列的头尾相连，构成一个循环队列。循环队列一般都是用数组来实现的。

在循环队列中，front和rear都是可以移动的。

当队列为空或满时，front = rear都成立，所以不能用这个条件来判断队列是空的还是满的。

为了解决这个问题，在循环队列中有一个约定：

少用一个元素空间，当队尾标识rear在队头标识front的上一个位置时，队列为满。此时，判断队列空和满的条件为：

队空：front == rear

对满：（rear+1）%MAXNUM == front  (MAXNUM为队列容量的大小)

循环队列中front和rear的移动不再是简单的加1，因为原本是循环的，所以可能原本指在末尾，前进一个单位就是又一个循环的开始，故每次移动都要对MAXNUM取模：

front = (front+1)%MAXNUM    

rear = (rear+1)%MAXNUM

求队列长度也不是简单的front和rear相减，因为rear的值有可能比front小。

循环队列求队列长度的方法：（rear+MAXNUM-front）%MAXNUM

循环队列的C语言实现：（codeblocks完美运行）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXNUM 50

//队列结构体
typedef struct queue
{
    int front;
    int rear;
    int data[MAXNUM];
}seqqueue;

//创建队列
seqqueue *create()
{
    seqqueue* sq = (seqqueue *)malloc(sizeof(seqqueue));
    sq->front = -1;
    sq->rear = -1;
    memset(sq->data,0,MAXNUM);
    return sq;
}

//获取队列长度
int getsize(seqqueue *sq)
{
    return (sq->rear+MAXNUM-sq->front)%MAXNUM;
}

//判断队列是否为空
int IsEmpty(seqqueue *sq)
{
    if(sq->rear == sq->front)
        return 1;
    return 0;
}

//判断队列是否满
int  IsFull(seqqueue *sq)
{
   if((sq->rear+1)%MAXNUM == sq->front)
        return 1;
    return 0;
}

//入队
int insert(seqqueue *sq,int val)
{
    if(IsFull(sq))
    {
        printf("队列已满!\n");
        return 0;
    }
    if(IsEmpty(sq))//如果队列为空
    {
        sq->front = sq->rear = 0;
        sq->data[sq->rear] = val;
        sq->rear++;
    }
    else
    {
        sq->data[sq->rear] = val;
        sq->rear = (sq->rear+1)%MAXNUM;
    }
}

//出队
int del(seqqueue *sq)
{
    if(IsEmpty(sq))
    {
        printf("队列已空！\n");
        return 0;
    }

    int temp = sq->data[sq->front];
    sq->front = (sq->front+1)%MAXNUM    ;
    return temp;
}

//获取队头元素
int getfront(seqqueue *sq)
{
    if(IsEmpty(sq))
    {
        printf("队列已空！\n");
        return 0;
    }
    return sq->data[sq->front];
}

//清空队列
void clear(seqqueue *sq)
{
    sq->front = sq->rear = -1;
    printf("队列已清空！\n");
}

//销毁队列
void destroy(seqqueue *sq)
{
    free(sq);
    printf("队列已销毁！\n");
}

int main()
{
    srand((unsigned)time(0));
    seqqueue *sq = create();            //创建队列
    int i;
    printf("入队30个元素！(从队尾插入)\n");
    for(i=0;i<30;i++)
    {
        insert(sq,rand()%300);
    }
    printf("队头为：%d\n",getfront(sq));
    printf("打印队列（同时是出队操作）\n");
    for(i=0;i<30;i++)
    {
        if(i%6 == 0)
            printf("\n");
        printf("%3d  ",del(sq));
    }
    printf("\n此时队列长度：%d\n",getsize(sq));

    clear(sq);
    destroy(sq);
    return 0;
}

运行界面：