DS初阶:循环队列的实现
循环队列是有自己的应用场景的!!
创作不易,给个三连吧!!
一、前言
对于循环队列,博主也是源自于一道力扣的OJ题
后来我在网上查过,这个循环队列是有自己的应用场景的!!并不是出题者为了出题而产生的,所以我觉得不光要能做会这道题,还得多去探究这道题的不同方式。而且这道题虽然是循环队列,看似好像要把头和尾连起来,但实际上实现过程中是可以不需要的!这也是他非常特别的一点,因此在这我会重点介绍他的数组实现和链式结构实现。
二、数组实现循环队列
怎么用数组去实现循环队列呢?我们来画图研究一下:
2.1 结构体的创建
typedef int QDataType;
typedef struct MyCircularQueue
{
QDataType* a;//动态数组
int capacity;//记录循环队列的容量
int front;//记录队首
int rear;//记录队尾
} MyCircularQueue;
2.2 构造一个k长度的队列并返回
根据我们之前的思路,我们要多创建一块空间!!
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if (obj == NULL)
{
perror("malloc obj fail");
exit(1);
}
obj->a = (QDataType*)malloc(sizeof(QDataType) * (k + 1));
if (obj->a == NULL)
{
perror("malloc obj->a fail");
exit(1);
}
obj->front = obj->rear = 0;
obj->capacity = k;
return obj;
}
2.3 向循环队列插入一个元素。如果成功插入则返回真。
我们要往循环队列中插入一个元素,那么首先必须确保队列不为满(后面会封装),那我们之前分析过队列不为满的情况是rear指针的下一个位置是front,但是我们要注意一个特殊情况,如下图:
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value)
{
if (myCircularQueueIsFull(obj))
return false;
obj->a[obj->rear] = value;
obj->rear++;
obj->rear %= (obj->capacity + 1);
return true;
}
但是我们要注意的是实际上我们是多开了一个空间!!!%的时候要把多的空间算上
2.4 向循环队列删除一个元素。如果成功删除则返回真。
我们要往循环队列中删除一个元素,那么首先必须确保队列不为空(后面会封装),front++就行了,同样front也会遇到上面这种情况,处理当时一样,++完后%上数组的实际大小
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if (myCircularQueueIsEmpty(obj))
return false;
obj->front++;
obj->front %= (obj->capacity + 1);
return true;
}
2.5 从队首获取元素。如果队列为空,返回 - 1
直接取头指针就行了
int myCircularQueueFront(MyCircularQueue* obj)
{
if (myCircularQueueIsEmpty(obj))
return -1;
return obj->a[obj->front];
}
2.6 从队尾获取元素。如果队列为空,返回 - 1
要注意rear指针指向的是最后一个元素的下一个位置,所以要取得的话就要找到rear的前一个位置的下标,这里我们不能直接让rear--,因为我们只是获取队列尾的元素,并不能去改变rear的指向,所以我们要算出rear前面那个位置的下标,其实也是一样,利用%的修正,让rear加上数组实际大小-1,然后再%数组的大小,就刚还是rear前面的位置的下标了!!
int myCircularQueueRear(MyCircularQueue* obj)
{
if (myCircularQueueIsEmpty(obj))
return -1;
return obj->a[(obj->rear + obj->capacity) % (obj->capacity + 1)];
}
2.7 判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->front == obj->rear;
}
2.8 判断循环队列是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
return (obj->rear + 1)%(obj->capacity + 1) ==obj->front;//rear为k的时候正好
}
2.9 销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a);//没必要置空,因为obj用不了,obj->a也用不了 front rear k 也没必要释放
free(obj);
//obj = NULL;
}
2.10 全部代码
2.10.1 MyCircularQueue.h
#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
typedef int QDataType;
typedef struct MyCircularQueue
{
QDataType* a;//动态数组
int capacity;//记录循环队列的容量
int front;//记录队首
int rear;//记录队尾
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k);//构造一个k长度的队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value);// 向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj);// 向循环队列删除一个元素。如果成功删除则返回真。
int myCircularQueueFront(MyCircularQueue* obj); //从队首获取元素。如果队列为空,返回 - 1 。
int myCircularQueueRear(MyCircularQueue* obj);//从队尾获取元素。如果队列为空,返回 - 1 。
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//判断循环队列是否为空
bool myCircularQueueIsFull(MyCircularQueue* obj);//判断循环队列是否为满
void myCircularQueueFree(MyCircularQueue* obj);//销毁循环队列
2.10.2 MyCircularQueue.c
#include"MyCircularQueue.h"
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if (obj == NULL)
{
perror("malloc obj fail");
exit(1);
}
obj->a = (QDataType*)malloc(sizeof(QDataType) * (k + 1));
if (obj->a == NULL)
{
perror("malloc obj->a fail");
exit(1);
}
obj->front = obj->rear = 0;
obj->capacity = k;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value)
{
if (myCircularQueueIsFull(obj))
return false;
obj->a[obj->rear] = value;
obj->rear++;
obj->rear %= (obj->capacity + 1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if (myCircularQueueIsEmpty(obj))
return false;
obj->front++;
obj->front %= (obj->capacity + 1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj)
{
if (myCircularQueueIsEmpty(obj))
return -1;
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if (myCircularQueueIsEmpty(obj))
return -1;
return obj->a[(obj->rear + obj->capacity) % (obj->capacity + 1)];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->front == obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
return (obj->rear + 1)%(obj->capacity + 1) ==obj->front;//rear为k的时候正好
}
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a);//没必要置空,因为obj用不了,obj->a也用不了 front rear k 也没必要释放
free(obj);
//obj = NULL;
}
2.11 相关选择题
5.现有一循环队列,其队头指针为front,队尾指针为rear;循环队列长度为N。其队内有效长度为?(假设队头不存放数据)( ?)
A (rear - front + N) % N + 1
B (rear - front + N) % N
C (rear - front) % (N + 1)
D (rear - front + N) % (N - 1)
答:这题就是根据我们上面那道题的一个变形,所以我们知道肯定是%上长度的,所以可以直接选B
三、链式结构实现循环队列
怎么用链式结构来实现循环队列呢?我们来分析一下:
3.1 结构体的创建
我们按照链式队列的思路,创建一个队列结构体来管理头尾指针,同时加上capacity(容量)和size(有效数据)
typedef int QDataType;
typedef struct QNode
{
struct QNode* next;//节点
QDataType val;//数据域
}QNode;
typedef struct MyCircularQueue
{
QNode* front;//链表的头指针
QNode* rear;//链表的尾指针
int capacity;//记录链表的容量
int size;//记录链表的有效节点
}MyCircularQueue;
3.2 构造一个k长度的队列并返回
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if (obj == NULL)
{
perror("malloc fail");
exit(1);
}
obj->front = obj->rear = NULL;
obj->size = 0;
obj->capacity = k;
return obj;
}
3.3 向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value)
{
//如果为满了,直接就返回false
if (myCircularQueueIsFull(obj))
return false;
//不满足就创建节点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->val = value;
newnode->next = NULL;
//创建成功,要考虑队列为空和不为空的情况
if (myCircularQueueIsEmpty(obj))//为空,让新节点成为头
obj->front = obj->rear = newnode;
else//不为空,让tail继续往后遍历
{
obj->rear->next = newnode;
obj->rear = newnode;
}
obj->size++;
return true;
}
3.4 向循环队列删除一个元素。如果成功删除则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
//为空就没有删的必要了
if (myCircularQueueIsEmpty(obj))
return false;
//不为空,删除头节点,让下一个节点成为新的头,然后释放掉
QNode* cur = obj->front->next;
free(obj->front);
obj->front = cur;
obj->size--;
return true;
}
3.5 从队首获取元素。如果队列为空,返回 - 1
int myCircularQueueFront(MyCircularQueue* obj)
{
//为空,返回1
if (myCircularQueueIsEmpty(obj))
return -1;
//不为空,就获取头指针的数据
return obj->front->val;
}
3.6 从队尾获取元素。如果队列为空,返回 - 1
int myCircularQueueRear(MyCircularQueue* obj)
{
//为空,返回1
if (myCircularQueueIsEmpty(obj))
return -1;
//不为空,就获取尾指针的数据
return obj->rear->val;
}
3.7 判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->size == 0;
}
3.8 判断循环队列是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
return obj->size == obj->capacity;
}
3.9 销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj)
{
//本质是链表,要一个个释放
QNode* pcur = obj->front;//用来遍历删除的
while (pcur)
{
QNode* next= pcur->next;
free(pcur);
pcur = next;
}
free(obj);
}
3.10 全部代码
3.10.1 MyCircularQueue.h
#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
typedef int QDataType;
typedef struct QNode
{
struct QNode* next;//节点
QDataType val;//数据域
}QNode;
typedef struct MyCircularQueue
{
QNode* front;//链表的头指针
QNode* rear;//链表的尾指针
int capacity;//记录链表的容量
int size;//记录链表的有效节点
}MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k);//构造一个k长度的队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value);// 向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj);// 向循环队列删除一个元素。如果成功删除则返回真。
int myCircularQueueFront(MyCircularQueue* obj); //从队首获取元素。如果队列为空,返回 - 1 。
int myCircularQueueRear(MyCircularQueue* obj);//从队尾获取元素。如果队列为空,返回 - 1 。
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//判断循环队列是否为空
bool myCircularQueueIsFull(MyCircularQueue* obj);//判断循环队列是否为满
void myCircularQueueFree(MyCircularQueue* obj);//销毁循环队列
3.10.2 MyCircularQueue.c
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if (obj == NULL)
{
perror("malloc fail");
exit(1);
}
obj->front = obj->rear = NULL;
obj->size = 0;
obj->capacity = k;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value)
{
//如果为满了,直接就返回false
if (myCircularQueueIsFull(obj))
return false;
//不满足就创建节点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->val = value;
newnode->next = NULL;
//创建成功,要考虑队列为空和不为空的情况
if (myCircularQueueIsEmpty(obj))//为空,让新节点成为头
obj->front = obj->rear = newnode;
else//不为空,让tail继续往后遍历
{
obj->rear->next = newnode;
obj->rear = newnode;
}
obj->size++;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
//为空就没有删的必要了
if (myCircularQueueIsEmpty(obj))
return false;
//不为空,删除头节点,让下一个节点成为新的头,然后释放掉
QNode* cur = obj->front->next;
free(obj->front);
obj->front = cur;
obj->size--;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj)
{
//为空,返回1
if (myCircularQueueIsEmpty(obj))
return -1;
//不为空,就获取头指针的数据
return obj->front->val;
}
int myCircularQueueRear(MyCircularQueue* obj)
{
//为空,返回1
if (myCircularQueueIsEmpty(obj))
return -1;
//不为空,就获取尾指针的数据
return obj->rear->val;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->size == 0;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
return obj->size == obj->capacity;
}
void myCircularQueueFree(MyCircularQueue* obj)
{
//本质是链表,要一个个释放
QNode* pcur = obj->front;//用来遍历删除的
while (pcur)
{
QNode* next= pcur->next;
free(pcur);
pcur = next;
}
free(obj);
}
四、总结
我们会发现,在这边无论是用数组实现和链表实现,本质上我们只是从逻辑层次上把它认为是相连的,但是物理层次上并没有把它连在一起,虽然链表是可以做到相连的,但是相连的话会比较复杂,不相连我们也可以解决,只要保证我们能够控制得住边界问题就行!!
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)