【数据结构】循环队列的实现



前言

(来源)

在这里插入图片描述

建议基本掌握普通队列的操作及实现再看本文章


一、循环队列

循环队列是基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环
正常我们平时实现的普通队列,大部分是以链表的方式存储,循环队列当然也可以,
但是循环队列使用顺序表的方式较普遍。

原因是无论是链表还是顺序表实现,都要考虑它的三种状态

  • 空队列
  • 有元素但未满的队列
  • 满队列

在这里插入图片描述

而这时候,顺序表的判断操作比起链表要简单,故普遍使用顺序表来实现循环队列

二、实现循环队列

1.思路分析

用两个下标来标识

  1. front–>头
  2. rear–>尾

在这里插入图片描述

在这里插入图片描述

初始状态的时候,front和rear都指向开始的位置,
队列满的时候在这个没有多开一个空间的队列中,满了之后也会两个下标指向同一个位置,
这时候就无法区分front==rear是空队列还是满队列

考虑到要区分这两个状态,我们可以多开一个空间,使得rear+1==front就为满队列,原来的rear==front就为空队列

在这里插入图片描述

循环队列的动图

在这里插入图片描述

注意:上面动画中的n是队列的总长度,也就是它把多开的那个一个空间也算进去了,
我下面的N表示的是循环队列的有效长度,也就是没把多开的一个空间算进去,
N+1=上面动画的n

那么循环队列的三个状态中最主要的两个已经解决了,循环队列的实现也就基本可以实现了

下面就是在代码中如何实现上面的思路

2.代码中的循环队列


在这里插入图片描述

在这里插入图片描述

下面代码可以直接复制到LeetCode运行–>✨题目地址


typedef struct {
    int *a;//顺序表地址
    int Front;//头下标
    int rear;
    int N;
} MyCircularQueue;

//MyCircularQueue(k): 构造器,设置队列长度为 k 。
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->Front=obj->rear=0;
    obj->N=k+1;
    return obj;
}

//isEmpty(): 检查循环队列是否为空。
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {

    return obj->Front==obj->rear;
}

//isFull(): 检查循环队列是否已满。
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->Front==(obj->rear+1)%obj->N;
}

//enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;

    obj->a[obj->rear]=value;
    obj->rear++;
    obj->rear%=obj->N;
    return true;
}

//deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
         return false;
    obj->Front++;
    obj->Front%=obj->N;
    return true;
}

//Front: 从队首获取元素。如果队列为空,返回 -1 。
int myCircularQueueFront(MyCircularQueue* obj) {
     if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[obj->Front];
}


//Rear: 获取队尾元素。如果队列为空,返回 -1 。
int myCircularQueueRear(MyCircularQueue* obj) {
     if(myCircularQueueIsEmpty(obj))
        return -1;
        return obj->a[(obj->rear-1+obj->N)%obj->N];
}



void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

总结


以上就是今天要讲的内容,本文仅仅简单介绍了循环队列的实现,而更多的操作实现细节还需要各位自行实现才能知道

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>