【数据结构与算法】设计循环队列

简介: 【数据结构与算法】设计循环队列

👑前言


🚩前面我们 用队列实现了一个栈 ,用栈实现了一个队列 ,相信大家随随便便轻松拿捏,而本章将带大家上点难度,我们来 设计一个循环队列。

🚩对于循环队列,重点就在一个 “ 循环 ”,意思也就是该队列首尾相连形成一个环,但其本质还是不变,队列 先进先出 的性质依旧存在,只不过环的大小有限定(限定放多少数据就只能放多少数据)。

🚩那么我们如何来设计这样的一个环,使它既能够像队列一样,又可以体现循环的性质?下面就带大家探讨一波。


如何设计循环队列


  • 那么该如何设计一个循环队列呢?首先第一步当然就是选取一个存储结构来存放数据,是选顺序表的数组呢还是链表呢?
  • 我们先来看看对循环队列的介绍:循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。


由以上所说,既然是队尾被连接在队首之后形成一个循环,并且之前我们讲解的队列是选用的链式储存结构,那我们第一个想到的就是选用链式的储存结构来存储数据,因为只要链表的尾节点的next指向头节点就形成了循环,这是很容易想到的。那我们就先对链式这一储存结构进行分析,看到底合不合适。


抽象图:



113e2772704a4fb6a45ab9b6e621ad81.png

既然是队列,那就需要两个指针,一个命名为front指向头,一个命名为rear指向尾。由于是循环队列,刚开始就将空间开好(固定长度),那么此时front和rear都指向同一个节点,如下:

e521c13b0e6347e4b839c4ae56a52026.png


那么此时入队列的操作过程如下:


2cf970123f944676b272fb4df6ab699e.gif



可以看到,rear指向有效数据节点的下一个位置。当队列入满的时候,rear指针此时又与front指针相等了,我们再来看看出队列的过程(出队列数据可以不用抹去,访问不到):


c6b1399c47924a8eae4686fcea59e792.gif

由上面的两个操作我们不难发现,当队列为空的时候,front指针与rear指针相等,当队列满的时候,front指针与rear指针也相等,这不免就会出现冲突问题:判空和判满将如何判断呢?


这里有两种方案:


第一个是多创建一个变量来统计数据的个数,当判空和判满的时候根据这个变量就可以实现;

第二个是多开一个空间(注意不是哨兵位节点),也就是规定长度为多少,开空间的时候开长度加一个空间,如下图:


fc8dd466b7334d9ca1d0e3c9417d2151.png

可以看到,方案二当循环队列为空的时候,front == rear,当循环队列为满的时候,如下图:


e27b4df4ffe949b4a9ea874430884b50.png


由此图不难得出,当循环队列为满时,有rear->next == front,所以,方案二对于判空和判满的区分也是挺不错的。不过,大家有没有观察到,对于链式储存结构,无论是方案一还是方案二,都不好找队尾数据,因为它处在rear指针的前一个节点,实在是要找的话,就需要遍历一遍循环队列,或者在一开始就另外再定义一个prev指针,指向rear指针的前一个节点,这些都是比较麻烦的。那么根据此问题,由于数组存储形式支持随机访问,所以下面我们再来看看数组的存储形式怎么样。


对于数组的存储形式,整体上来说与链式存储形式差不太多。由于循环队列的长度是固定的,因此数组的存储形式抛弃了扩容这一弱点。


数组存储形式图:b859188a0724494ebbded111a4cea179.png

有了链式存储的分析判断,不难得出,上图的数组存储形式也会出现判空和判满实现的冲突问题。因此这里也需要解决方案,而数组存储形式的解决方案与链式存储形式的解决方案是相同的,无非就是多定义一个变量来统计数据的个数,或者多开一个空间。多定义一个变量来统计数据的个数固然可以实现,但这里我们选取多开一个空间的形式来进行分析。


如果是多开一个空间,那么当循环队列满时,有以下情况:



e11e84013c98467999dfb94f4ed319d5.png


b81dc793ad4849c6a09241c8a766156c.png


(注意:front与rear两个指针分别是对应数据的下标 | 设规定的长度为k)


如果是2情况,判满可以判断 rear + 1 == front ? ,但还有1情况rear + 1不会等于front,并且会超出数组的下标范围,因此这里可以对rear + 1取模,也就是判断 (rear + 1) % (k + 1) == front ? 即可。有了这种判断方式,无论rear是否指向数组的最后一个位置,他都可以判断,因为:当rear不是指向数组的尾时,它加一模上一个(k + 1)完全不会受到影响,就相当于是判断 rear + 1 == front ? 一样。而rear指向数组的尾时,这样操作最终就是判断 front == 0 ? 一样。


那数组的判满解决了,判空如何呢?其实判空很简单,只需要判断rear是否等于front即可。


由于是数组存储形式,因此支持下标的随机访问,所以这里获取队头和队尾元素都非常的方便。


如果是获取队头元素,直接返回front指向的数据即可;如果是获取队尾元素,只需要返回rear的前一个位置的数据即可,但是,如果rear此时指向数组的开头又该怎么找队尾元素呢?

e503017409b748259221576753505dcc.png


这里我们将 rear + k 然后模上 k + 1 即可。因为,如果rear是指向数组开头,rear加上k后刚好指向数组的最后一个位置,也就是循环队列的队尾。如果rear不是指向数组开头, (rear + k) % (k + 1) 刚好是rear的前一个位置,所以,这样的取模的方式,完美的实现了取队尾的功能。

综上来看,链式储存结构与数组储存结构还是数组储存结构更胜一筹,因为在取队尾元素这一块数组储存结构碾压链式储存结构,所以,这里我们选择数组储存结构来实现循环队列。


这里我们采用多开一个空间的方式来实现。


确定了以数组存储结构来存储数据后,那么该如何实现数据的入队和出队呢?


首先来看看数据入队列示意图:


0d7cf6e6e0014e4ab622bad0968bac05.gif

f8b7b069489a489b972352f33f569aad.gif

对于第一张图的入队列,就是在当前rear位置插入,然后rear加加即可。但是对于第二张图,rear在最后位置的时候插入数据,此时rear加加就超过数组的长度了,因此我们每次在rear加加后需要执行一下 rear %= (k + 1) 这条语句,这样做,rear在数组的尾插入数据时,会将rear转算成0,也就是指向数组的开头位置,如果rear不在数组的尾插入数据,此时rear的位置不会受任何的影响。


然后再来看看数据出队列示意图:

0e4e15feb9554a009fd3afa1f22d2c1d.gif


4171ab3a3f394da68c70e8bf246162c6.gif


对于第一张图,每次删除其实只需要front加加即可,如果为空就不能删了。对于第二张图,当front指向数组的最后一个位置时,出队过后,front加加会越过数组,因此,每次出队列完成,都需要执行 front %= (k + 1) 这条语句,情况其实与上面入队列时的rear一样。


入队列与出队列介绍过了,后面就是一些队列基本的接口操作了。有取队头数据,取队尾数据,判空和判满,还有循环队列的销毁。


入队列与出队列介绍过了,后面就是一些队列基本的接口操作了。有取队头数据,取队尾数据,判空和判满,还有循环队列的销毁。


接下来就带大家来实现喽!


设计循环队列


  • 这里我们直接以题目的方式来实现,题目链接:->传送门<-


题目描述:设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。


9145193c7b9348028c626582f1121104.png



9dd64add0c114d599d875ffd45bcd99e.png



该题提供的需要我们实现的接口:

typedef struct {
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
}
int myCircularQueueFront(MyCircularQueue* obj) {
}
int myCircularQueueRear(MyCircularQueue* obj) {
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
}
void myCircularQueueFree(MyCircularQueue* obj) {
}


接下来,就是对循环队列的一系列功能接口的实现了:

1.

  • 首先当然是定义一个循环队列的结构体。

相关代码实现:

// 循环队列的结构
typedef struct {
  // 底层存储结构为数组
    int* a;
    // 指向队头
    int front;
    // 指向队尾
    int rear;
    // 规定的循环队列的长度
    // 这里存放一下规定的循环队列的长度是为了后面取模更方便
    int k;
} MyCircularQueue;


2.

  • 然后便是对一个循环队列的创造。
  • 这里开辟一段连续的空间,可以存放规定的长度加一个数据,但其实总有一个空间是用不上的。
  • 然后将frontrear都指向循环队列的队头,就是置为0
  • 最后将规定的长度存起来即可。

相关代码实现:


// 循环队列的创造(构造器),规定创造的循环队列的长度为k
MyCircularQueue* myCircularQueueCreate(int k) {
  // 先开辟一个循环队列的空间
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    // assert防止开辟空间失败
    assert(obj);
  // 多开一个空间,也就是开辟(k + 1)个数据空间
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    // 开始头指针和尾指针都指向0(也就是队头)
    obj->front = obj->rear = 0;
    // 存放规定的队列长度
    obj->k = k;
    return obj;
}


  • 这里是入队列的实现。
  • 入队列就是在当前的rear位置插入数据,然后rear加加。
  • 根据前面的解析,入队列之后都需要取模一次,避免rear越过数组。(当然也可以通过判断的方式来处理特殊情况)
  • 当队列为满的时候就不能入队列了。

相关代码实现:

// 入队列插入数据,插入成功返回true,不成功(队列已满)那就返回false
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  // 如果此时循环队列已经满了,说明入队列不能进行,直接返回 false
    if (myCircularQueueIsFull(obj)) return false;
  // 在rear位置上插入数据,然后rear加加
    obj->a[obj->rear ++ ] = value;
    // 每次都模上个 (k + 1)
    obj->rear %= (obj->k + 1);
  // 入队列成功返回true
    return true;
}
  • 接下来是出队列操作。
  • 出队列就是front加加,根据前面的讲解,每次出队列后都要记得需模上(k + 1)。(当然也可以通过判断的方式来处理特殊情况)
  • 当队列为空的时候就不能出队列了。

相关代码实现:

// 出队列删除数据,删除成功返回true,不成功(队列为空)那就返回false
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  // 当循环队列为空,说明不能再出队列了,表明出队列失败,直接返回false
    if (myCircularQueueIsEmpty(obj)) return false;
  // 出队列直接front加加
    obj->front ++ ;
    // 每次都模上个 (k + 1)
    obj->front %= (obj->k + 1);
  // 出队列成功返回true
    return true;
}


  • 获取队头数据,直接返回front此时指向的那个位置上的数据即可。
  • 如果循环队列为空的话,就取不了了,依题目要求直接返回-1

相关代码实现:

// 获取队头元素,如果队列为空,返回-1
int myCircularQueueFront(MyCircularQueue* obj) {
  // 如果循环队列为空,说明没有数据,直接返回-1
    if (myCircularQueueIsEmpty(obj)) return -1;
    return obj->a[obj->front];
}


  • 获取队尾数据,根据前面的分析,采用取模的方式获取。(当然也可以通过判断的方式)
  • 如果循环队列为空的话,就取不了了,依题目要求直接返回-1

相关代码实现:

// 获取队尾元素,如果队列为空,返回-1
int myCircularQueueRear(MyCircularQueue* obj) {
  // 如果循环队列此时为空,直接返回-1
    if (myCircularQueueIsEmpty(obj)) return -1;
    // 以取模的方式来获取
    return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}


  • 对于判空,就是判断front是否等于rear即可。

相关代码实现:

// 判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}
  • 对于判满,根据前面的分析,也是通过取模的方式来实现的。(当然也可以通过判断的方式来处理特殊情况)

相关代码实现:

// 判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}


  • 最后就是销毁循环链表,malloc了几次,就free(释放)几次。

相关代码实现:

// 销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj) {
  // 有内到外依次释放空间
  // 释放数组
    free(obj->a);
    // 释放循环队列
    free(obj);
}


整体的代码


// 循环队列的结构
typedef struct {
  // 底层存储结构为数组
    int* a;
    // 指向队头
    int front;
    // 指向队尾
    int rear;
    // 规定的循环队列的长度
    int k;
} MyCircularQueue;
// 在这声明一下判空和判满
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
// 循环队列的创造(构造器),规定创造的循环队列的长度为k
MyCircularQueue* myCircularQueueCreate(int k) {
  // 先开辟一个循环队列的空间
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    // assert防止开辟空间失败
    assert(obj);
  // 多开一个空间,也就是开辟(k + 1)个数据空间
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    // 开始头指针和尾指针都指向0(也就是队头)
    obj->front = obj->rear = 0;
    // 存放规定的队列长度
    obj->k = k;
    return obj;
}
// 入队列插入数据,插入成功返回true,不成功(队列已满)那就返回false
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) return false;
    obj->a[obj->rear ++ ] = value;
    obj->rear %= (obj->k + 1);
    return true;
}
// 出队列删除数据,删除成功返回true,不成功(队列为空)那就返回false
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return false;
    obj->front ++ ;
    obj->front %= (obj->k + 1);
    return true;
}
// 获取队头元素,如果队列为空,返回-1
int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return -1;
    return obj->a[obj->front];
}
// 获取队尾元素,如果队列为空,返回-1
int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return -1;
    return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}
// 判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}
// 判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
// 销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}


📯写在最后


💝设计一个循环队列还是有些复杂的呢,不过看过本文章,相信大家也可以轻松拿捏。

❤️‍🔥后续将会持续输出有关数据结构与算法的文章,你们的支持就是我写作的最大动力!

感谢阅读本小白的博客,错误的地方请严厉指出噢~

相关文章
|
7月前
|
存储 Java 容器
深入浅出 栈和队列(附加循环队列、双端队列)
深入浅出 栈和队列(附加循环队列、双端队列)
|
7月前
|
存储
【数据结构】循环队列
【数据结构】循环队列
62 0
|
7月前
|
算法 调度 C++
【C/C++ 数据结构 线性表】C/C++中队列的原理与实现:从基础到循环队列
【C/C++ 数据结构 线性表】C/C++中队列的原理与实现:从基础到循环队列
155 0
数据结构第九弹---循环队列
数据结构第九弹---循环队列
|
6月前
|
存储 算法
【数据结构和算法】--队列的特殊结构-循环队列
【数据结构和算法】--队列的特殊结构-循环队列
34 0
|
2月前
|
存储
【初阶数据结构】深入解析循环队列:探索底层逻辑
【初阶数据结构】深入解析循环队列:探索底层逻辑
|
5月前
|
存储 索引
【数据结构OJ题】设计循环队列
力扣题目——设计循环队列
38 1
【数据结构OJ题】设计循环队列
|
4月前
|
算法
【数据结构与算法】循环队列
【数据结构与算法】循环队列
26 0
|
6月前
|
存储 算法 调度
【数据结构与算法】详解循环队列:基于数组实现高效存储与访问
【数据结构与算法】详解循环队列:基于数组实现高效存储与访问
|
6月前
|
存储 算法
数据结构和算法学习记录——设计循环队列(数组实现循环队列)核心思路、题解过程、完整题解
数据结构和算法学习记录——设计循环队列(数组实现循环队列)核心思路、题解过程、完整题解
50 1