循环队列出队-数据结构与算法

循环队列

实际中我们还会用到一种队列叫做循环队列，这种队列把存储空间前后连接起来，形成像环一样的结构，解决了内存空间浪费的问题

这里我们用顺序结构来实现，因为为了防止溢出的情况，这里我们需要多开一个数据的空间用作缓冲，这部分不用于存数据，用于防止溢出，当数组访问到这一部分时就将他归零，实现循环的结构。

每次入数据通过队尾指针入，出数据通过队首指针出，和队列的操作方法差不多，每一步骤的具体实现思路会在下面写出

数据结构

typedef int DataType;

代码语言：javascript复制

    typedef struct 
    {
        DataType* queue;
        int front;
        int rear;
        int length;
    } CircularQueue;

实现的接口

CircularQueue* CircularQueueCreate(int k);

代码语言：javascript复制

    //循环队列初始化
    bool CircularQueueEnQueue(CircularQueue* obj, DataType value);
    //循环队列入队
    bool myCircularQueueDeQueue(CircularQueue* obj);
    //循环队列出队
    DataType CircularQueueFront(CircularQueue* obj);
    //获取循环队列队首
    DataType CircularQueueRear(CircularQueue* obj);
    //获取循环队列队尾
    int CircularQueueSize(CircularQueue* obj);
    //循环队列长度
    bool CircularQueueIsEmpty(CircularQueue* obj);
    //判断循环队列是否为空
    bool CircularQueueIsFull(CircularQueue* obj);
    //判断循环队列是否已满
    void CircularQueueFree(CircularQueue* obj);
    //销毁循环队列

循环队列初始化

CircularQueue* CircularQueueCreate(int k)

代码语言：javascript复制

    {
        CircularQueue* cq = (CircularQueue*)malloc(sizeof(CircularQueue));
        cq->queue = (DataType*)malloc((k   1) * sizeof(DataType));
        cq->front = 0;
        cq->rear = 0;
        cq->length = k   1;
        return cq;
    }

初始化时多开一个空间，防止溢出。

入队列

bool CircularQueueEnQueue(CircularQueue* obj, DataType value)

代码语言：javascript复制

    {
        if ((obj->rear   1) % obj->length == obj->front)
            return false;
        obj->queue[obj->rear  ] = value;
        if (obj->rear == obj->length)
            obj->rear = 0;
        return true;
    }

我们首先要判断队列是否已满循环队列出队，如果满了则返回false，为什么使用这个公式我会在下面的判断队满的函数中写到，没满则将数据存到队尾指针的位置，如果队尾指针达到了我们多开的那个位置，则让队尾指针归零

出队列

bool myCircularQueueDeQueue(CircularQueue* obj)

代码语言：javascript复制

    {
        if (obj->front == obj->rear)
            return false;;
          obj->front;
        if (obj->front == obj->length)
            obj->front = 0;
        return true;
    }

首先判断是否队空循环队列出队，然后使队头指针走一步，当队头指针到达多开的空间时，归零

获取队首元素

DataType CircularQueueFront(CircularQueue* obj)

代码语言：javascript复制

    {
        if (obj->front == obj->rear)
            return -1;
        else
            return obj->queue[obj->front];
    }

获取队尾元素

DataType CircularQueueRear(CircularQueue* obj)

代码语言：javascript复制

    {
        if (obj->front == obj->rear)
            return -1;
        else if (obj->rear == 0)
            return obj->queue[obj->length - 1];
        else
            return obj->queue[obj->rear - 1];
    }

获取队列中有效元素个数

int CircularQueueSize(CircularQueue* obj)

代码语言：javascript复制

    {
        return (obj->rear - obj -> front   obj->length) % obj->length;
    }

首先用队尾位置减去队首位置，然后因为是循环队列，位置不断变化可能会出现负数和得不到正确的结果，我们就需要先加上总长度在对总长度取模，这样得到的才是他们真正的位置差，也就是有效元素个数

检测循环队列是否为空

bool CircularQueueIsEmpty(CircularQueue* obj)

代码语言：javascript复制

    {
        if (obj->rear == obj->front)
            return true;
        else
            return false;
    }

当队首和队尾处于同一位置时说明循环队列为空，因为此时他们的相对位置为零

检测循环队列是否已满

bool CircularQueueIsFull(CircularQueue* obj)

代码语言：javascript复制

    {
        if ((obj->rear   1) % obj->length == obj->front)
            return true;
        else
            return false;
    }

当队满的时候队首应该在队尾的下一个位置，但因为循环队列位置不断变化，可能出现超过总长度或者归零的情况，所以我们需要对总长度取模来获取他们的相对位置

销毁循环队列

void CircularQueueFree(CircularQueue* obj)

代码语言：javascript复制

    {
        free(obj->queue);
        obj->queue = NULL;
        free(obj);
        obj = NULL;
    }

完整代码

头文件

#pragma once

代码语言：javascript复制

    #include 
    #include 
    #include 
    typedef int DataType;
    typedef struct {
        DataType* queue;
        int front;
        int rear;
        int length;
    } CircularQueue;
    CircularQueue* CircularQueueCreate(int k);
    //循环队列初始化
    bool CircularQueueEnQueue(CircularQueue* obj, DataType value);
    //循环队列入队
    bool myCircularQueueDeQueue(CircularQueue* obj);
    //循环队列出队
    DataType CircularQueueFront(CircularQueue* obj);
    //获取循环队列队首
    DataType CircularQueueRear(CircularQueue* obj);
    //获取循环队列队尾
    bool CircularQueueIsEmpty(CircularQueue* obj);
    //判断循环队列是否为空
    bool CircularQueueIsFull(CircularQueue* obj);
    //判断循环队列是否已满
    void CircularQueueFree(CircularQueue* obj);
    //销毁循环队列

函数实现

#pragma once

代码语言：javascript复制

    #include "CircularQueue.h"
    CircularQueue* CircularQueueCreate(int k) 
    {
        CircularQueue* cq = (CircularQueue*)malloc(sizeof(CircularQueue));
        cq->queue = (DataType*)malloc((k   1) * sizeof(DataType));
        cq->front = 0;
        cq->rear = 0;
        cq->length = k   1;
        return cq;
    }
    bool CircularQueueEnQueue(CircularQueue* obj, DataType value) 
    {
        if ((obj->rear   1) % obj->length == obj->front)
            return false;
        obj->queue[obj->rear  ] = value;
        if (obj->rear == obj->length)
            obj->rear = 0;
        return true;
    }
    bool myCircularQueueDeQueue(CircularQueue* obj) 
    {
        if (obj->front == obj->rear)
            return false;;
          obj->front;
        if (obj->front == obj->length)
            obj->front = 0;
        return true;
    }
    DataType CircularQueueFront(CircularQueue* obj) 
    {
        if (obj->front == obj->rear)
            return -1;
        else
            return obj->queue[obj->front];
    }
    DataType CircularQueueRear(CircularQueue* obj) 
    {
        if (obj->front == obj->rear)
            return -1;
        else if (obj->rear == 0)
            return obj->queue[obj->length - 1];
        else
            return obj->queue[obj->rear - 1];
    }
    bool CircularQueueIsEmpty(CircularQueue* obj) 
    {
        if (obj->rear == obj->front)
            return true;
        else
            return false;
    }
    bool CircularQueueIsFull(CircularQueue* obj) 
    {
        if ((obj->rear   1) % obj->length == obj->front)
            return true;
        else
            return false;
    }
    void CircularQueueFree(CircularQueue* obj) 
    {
        free(obj->queue);
        obj->queue = NULL;
        free(obj);
        obj = NULL;
    }

本文共 734 个字数,平均阅读时长 ≈ 2分钟

ear int typedef 队列指针

0 人点赞

循环队列出队-数据结构与算法 | 循环队列