C语言 循环队列

什么是队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

什么是循环队列

在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。指针从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。

使用循环队列虽然可以解决顺序队列中浪费内存的问题，但这里任然存在一个问题，就是对于循环队列而言，队空和队满的条件都是rear==front，导致两种情况无法区分。

解决这个问题有两个办法：一是增加一个参数，用来记录数组中当前元素的个数；第二个办法是，少用一个存储空间，也就是数组的最后一个存数空间不用，当（rear+1）%maxsiz=front时，队列满；

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define Maxsize 100
using namespace std;
 
typedef struct quenue{
    int data[Maxsize];
    int fronts;
    int rear;
}SqQuenue;
//初始化
int Init_SqQuenue(SqQuenue &S)
{
    S.fronts=S.rear=0;
}
//入队
bool EnQuenue(SqQuenue &Q,int x)
{
    if((Q.rear+1)%Maxsize==Q.fronts)
        return false;
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%Maxsize;
    return true;
}
//出队
bool DeQuenu(SqQuenue &Q,int &x)
{
    if(Q.rear==Q.fronts)
        return false;
    x=Q.data[Q.fronts];
    Q.fronts=(Q.fronts+1)%Maxsize;
    return true;
}
//打印
int show_SqQuenue(SqQuenue Q)
{
    for(int i=Q.fronts;i<Q.rear;i++)
    {
        printf("%d ",Q.data[i]);
    }
}
int main()
{
    SqQuenue Q;
    Init_SqQuenue(Q);
    EnQuenue(Q,1);
    EnQuenue(Q,2);
    EnQuenue(Q,3);
    show_SqQuenue(Q);
    int x;
    DeQuenu(Q,x);
    printf("%d\n",x);
    show_SqQuenue(Q);
    return 0;
}