数据结构—顺序循环队列（附代码实现）

队列

概念 队列也是一种特殊的线性表。不过，线性表允许在任何位置插入和删除，而队列只允许在队尾插入，在队头删除，这样它就具有先进先出的性质

重点

顺序循环队列的假溢出问题 由于队尾指针rear的值和队头front的值不能由所定义存储空间的最大值自动转为所定义存储空间的最小值而产生

为了解决这个问题，有三种方法可以选择 1 少用一个存储单元 如果少用一个存储空间，则以队尾指针加1等于队头指针为队列满的判断条件，那么此时判断队列满的条件为 （rear+1）%Maxsize ==front 队列空的判断条件为： rear=front; (2)设置一个标志位

设置标志位为tag，初始时置tag=0；每当如队列操作成功，就置tag=1；每当出队列操作成功，就置tag=0. 此时队列空的判断条件为 rear==front && tag=0 队列满的条件为 rear==front && tag=1 (3)设置一个计数器 设计数器为count，初始时置count=0；每当如队列成功，就使count++；每当出队列成功，那就让count–。这样，计数器不仅具有计数功能，而且还具有标志位一样的标志作用，则此时队列空的判断条件为：count==0 队列满的条件为： count>0 &&rear==front; 还可以是: count=Maxsize; 附代码

#include<stdio.h>
#include<stdlib.h>
#define Maxsize 100

typedef int DataType;

typedef struct    //定义一个结构体
{
    DataType queue[Maxsize];
    int rear;        //队尾指针
    int front;       //队头指针
    int count;       //计数器
}SeqQueue;

void SeqQueueInitiate(SeqCQueue *Q)//队列初始化
{
    Q->rear=0;
    Q->front=0;
    Q->count=0;
}

int QueueNotEmpty(SeqQueue Q)//队列判空
{
    if(Q.count!=0)
        return 1;
    else return 0;
}
int QueueAppend(SeqQueue *Q,DataType x)//入队列
{
    if(Q->count >0 && Q->rear ==Q->front)
    {
        printf("队列已满无法插入");
        return 0;
    }
    else
    {
        Q->queue[Q->rear]=x;//将x插入队尾
        Q->rear=(Q->rear +1)%Maxsize;
        Q->count++;     //计数器加1
        return 1;
    }

}

int QueueDelete(SeqQueue *Q,DataType *d)//出队列
{
    if(Q->count ==0)
    {
        printf("队列已空
");
        return 0;
    }
    else
    {
        *d=Q->queue[Q->front];//用指针d保存要删除的元素
    Q->front=(Q->front+1)%Maxsize;  //队头元素都给前移一位
    Q->count--;
    return 1;
    }

}
int QueueGet(SeqQueue Q,DataType *d)//取数据
{
    if(Q.count ==0)
    {
        printf("队列已空无数据可取！
");
        return 0;
    }
    else
    {
        *d=Q.queue[Q.front];
        return 1;

    }
}