数组模拟循环队列

• 简介

队列（queue）在计算机科学中，是一种先进先出的线性表。

它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。

为充分利用向量空间，克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表的方式来在实际编程应用中来实现。

本文采用数组模拟循环队列。

• 判断循环队列为空或满

首先我们初始化一个长度为5的数组，如下图，我们让front和rear都指向它的首部

在使用循环队列，我们把它想象成一个环形结构，如图

由上图我们可以知道当front=rear时，循环队列为空。

队列为满的情况比较复杂，如果我们完全填满队列，会发现满时front=rear,此时满和空的条件重复，不能判断，因此我们留一个位置不用来存储数据，如下图

可以发现，如果从左边圆环判断为满，应该是rear+1=front，但是我们不能忽略这个循环队列本质是由数组实现的，若rear+1，就已经超过数组范围，如何又与front比较呢

因此正确的比较方法应该是 （rear+1）%QueueSize=front

其中QueueSize是循环队列分配数组的长度

• 实现代码+注释

//622 。 设计循环队列
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int ElemType;
 
 
 
typedef struct//循环队列结构 
{
    ElemType* base;
    int front;
    int rear;
    int capacity;
} MyCircularQueue;
 
bool myCircularQueueIsEmpty(MyCircularQueue* obj)//判断循环队列是否为空，为空返回true 
{
    assert(obj);
    if (obj->front == obj->rear)
        return true;
    return false;
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj)//判断循环队列是否为满，为满返回true 
{
    assert(obj);
    if ((obj->rear + 1) % (obj->capacity) == (obj->front))
        return true;
    return false;
}
 
MyCircularQueue* myCircularQueueCreate(int k)//传入循环队列大小，生成需要的循环队列 
{
    MyCircularQueue* CycleQueue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if (!CycleQueue)
    {
        perror("malloc fail");
        exit(0);
    }
    CycleQueue->base = (ElemType*)malloc(sizeof(ElemType) * (k+1));
    if (!CycleQueue->base)
    {
        perror("malloc fail");
        exit(0);
    }
    CycleQueue->front = 0;
    CycleQueue->rear = 0;
    CycleQueue->capacity = k+1;
    return CycleQueue;
}
 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//在对尾插入元素 
{
    assert(obj);
    if (myCircularQueueIsFull(obj))//如果队列满 
    {
        return false;
    }
    obj->base[obj->rear] = value;
    obj->rear = (obj->rear + 1) % obj->capacity;//加入元素后队列rear后移 
    return true;//成功加入队列返回true 
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj)//出队列 
{
    assert(obj);
    if (myCircularQueueIsEmpty(obj))//若队列为空 
    {
        return false;
    }
    obj->front = (obj->front + 1) % obj->capacity;//加入元素后队列front后移 
    return true;//成功出队列返回true 
}
 
int myCircularQueueFront(MyCircularQueue* obj)//返回队头 
{
    assert(obj);
    if (myCircularQueueIsEmpty(obj))//若为空队列 
    {
        return -1;
    }
    return obj->base[obj->front];//返回队头 
}
 
int myCircularQueueRear(MyCircularQueue* obj)//返回队尾 
{
    assert(obj);
    if (myCircularQueueIsEmpty(obj))//若为空队列 
    {
        return -1;
    }
    return obj->base[(obj->rear - 1+obj->capacity)%obj->capacity];//返回队尾 
}
 
 
 
void myCircularQueueFree(MyCircularQueue* obj)//销毁循环队列 
{
    assert(obj);
    assert(obj->base);
    free(obj->base);
    obj->base = NULL;
    free(obj);
    obj = NULL;
}
 
int main()//测试用例 
{
    MyCircularQueue* obj = myCircularQueueCreate(3);
    myCircularQueueEnQueue(obj, 1);
    myCircularQueueEnQueue(obj, 2);
    myCircularQueueEnQueue(obj, 3);
    //myCircularQueueEnQueue(obj, 4);
    while (!myCircularQueueIsEmpty(obj))
    {
        printf("%d", myCircularQueueFront(obj));
        myCircularQueueDeQueue(obj);
    }
 
 
    return 0;
}