博客

循环队列实际上是个线性空间，有最大空间限制，但是在逻辑上形成一个环状结构。

如何区分循环队列空、满状态？

这里使用闲置一个元素空间进行标记的方法。

（1）当队列空时，front == rear。

（2）当队列满时，(rear+1)%maxsize = = front。

取余操作实现了逻辑上的环路。

当队列非空时，front始终指向队首元素，rear始终指向队尾元素的下一个。

1、循环队列结构定义

#define MAXQSIZE 100    // 队列最大长度，实际可用空间要少一个
typedef char QElemType;
typedef struct
{
    QElemType *base;
    int front;  //始终指向队头
    int rear;   //始终指向非空队列队尾的下一个元素
}CircularQueue;

2、初始化

在这为队列申请内存空间，用以存放队列元素，并将队列状态置为空。

// 初始化工作：申请内存，队列置空
int init(CircularQueue *Q)
{
    Q->base = malloc(MAXQSIZE*sizeof(QElemType));
    if(!Q->base)//内存申请失败
    {
        return -1;
    }
    Q->rear = Q->front = 0;
    return 0;
}

3、销毁队列

在这，释放为队列申请的内存空间。

// 释放队列申请的内存
int destroy(CircularQueue *Q)
{
    free(Q->base);
    Q->base = NULL;
    Q->rear = Q->front = 0;
    return 0;
}

4、元素个数

// 获得队列元素个数
int length(CircularQueue *Q)
{
    return (Q->rear - Q->front + MAXQSIZE) % MAXQSIZE;
}

5、清空队列

// 将队列清空
int clear(CircularQueue *Q)
{
    Q->rear = Q->front = 0;
    return 0;
}

6、判空

// 判空
int empty(CircularQueue *Q)
{
    return (Q->rear == Q->front ? 1 : 0);
}

7、入队

在队列尾部加入新元素。

// 入队：在队尾加入元素
int push(CircularQueue *Q, QElemType e)
{
    if((Q->rear+1)%MAXQSIZE == Q->front)    //队列满
    {
        return -1;
    }
    Q->base[Q->rear] = e;
    Q->rear = (Q->rear+1)%MAXQSIZE;//rear始终指向下一个要插入的位置
    return 0;
}

8、获取队首元素

// 获取队首元素
int front(CircularQueue *Q, QElemType *e)
{

    if(empty(Q))
    {
        return -1;
    }
    *e = Q->base[Q->front];
    return 0;
}

9、出队

// 出队：删除队首元素
int pop(CircularQueue *Q)
{
    if(empty(Q)) //队列空
    {
        return -1;
    }
    Q->front = (Q->front+1) % MAXQSIZE;
    return 0;
}