提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

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

2023-02-18 16:47:34 时间

循环队列

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

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

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

数据结构

   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);
    //获取循环队列队尾
    int CircularQueueSize(CircularQueue* obj);
    //循环队列长度
    bool CircularQueueIsEmpty(CircularQueue* obj);
    //判断循环队列是否为空
    bool CircularQueueIsFull(CircularQueue* obj);
    //判断循环队列是否已满
    void CircularQueueFree(CircularQueue* obj);
    //销毁循环队列

  循环队列初始化

   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;
    }

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

  出队列

   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];
    }

  获取队列中有效元素个数

   int CircularQueueSize(CircularQueue* obj)

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

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

  检测循环队列是否为空

   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;
    }

  完整代码

  头文件

   #pragma once

    #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

    #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分钟

相关文章