前言
1、学习循环队列和循环双端队列能加深我们对队列的理解,提高我们的编程能力。
2、本文循环队列使用的是数组,循环双端队列用的是双向链表
3、题目连接:设计循环队列 ,设计循环双端队列。
循环队列
1、什么是循环队列?
循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
2、实现的功能
(1)MyCircularQueue(k): 构造器,设置队列长度为 k 。
(2)Front: 从队首获取元素。如果队列为空,返回 -1。
(3)Rear: 获取队尾元素。如果队列为空,返回 -1 。
(4)enQueue(value):向循环队列插入一个元素。如果成功插入则返回真。
(5)deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
(6)isEmpty(): 检查循环队列是否为空。
(7)isFull(): 检查循环队列是否已满。
3、设计
有两种方案:a:利用数组来存储数据,b:利用链表来存储数据
我们这里使用数组的方式
(1)我们设置一个头指针,和一个尾指针(指的时最后一个有数据位置的下一个位置,为什么不直接指向最后有数据那个位置呢?因为这样能更好的判断队列是否为空和队列是否已经满的情况),头指针(front),尾指针(rear),容量(k)。
(2) 为了解决尾指针指向最后一个数据后一个的问题,我们可以多申请一个空间,就不会使尾指针指的位置超出数组了,这个问题也叫假溢出。
(3)判断空,当front=rear时为空
(4)判断满,当 front=(rear+1)%(k+1) 为空
(5)删除队头元素,使front=(front+1)%(k+1)即可, 也可以通过判断front是否在(k+1)的位置,在的话就使front=0,不在的话front=front+1即可
(6)进队,将数据放到数组下标rear位置上,然后使 rear=(rear+1)%(k+1) 即可,原理同上。
(7)获取队头元素,直接返回队头下标的位置的数据即可
(8)获取队尾元素,返回 (rear-1+k+1)%(k+1) 位置的数据即可,也可以判断rear是不是在0的位置,在的话top=k,不在0的位置的话就top=rear-1
4、代码实现:
//队列结构体
typedef struct {
//储存数据
int *arr;
//头
int front;
//指向尾的下一个
int rear;
//大小
int k;
} MyCircularQueue;
//初始化循环队列
MyCircularQueue* myCircularQueueCreate(int k) {
//队列
MyCircularQueue* obj=( MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//初始化成员
obj->arr=(int*)malloc(sizeof(int)*(k+1));
obj->front=0;
obj->rear=0;
obj->k=k;
return obj;
}
//是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
//当队头的下标等于队尾的下标时队列为空
return obj->front==obj->rear;
}
//是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
//当队头的下标等于队尾加一模上k+1时队列满了
return obj->front==(obj->rear+1)%(obj->k+1);
}
//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//当队列满了就返回false
if(myCircularQueueIsFull(obj))
return false;
//放到rear位置上
obj->arr[obj->rear]=value;
//这样当rear+1==k+1时,让rear回到0这个位置上
obj->rear=(obj->rear+1)%(obj->k+1);
return true;
}
//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//空时返回false
if(myCircularQueueIsEmpty(obj))
return false;
//队头下标加1,莫上k+1当front+1==k+1时能回到0那个位置
obj->front=(obj->front+1)%(obj->k+1);
return true;
}
//查看头元素
int myCircularQueueFront(MyCircularQueue* obj) {
//空时返回-1
if(myCircularQueueIsEmpty(obj))
return -1;
//直接展示front位置即可
int tmp=obj->arr[obj->front];
return tmp;
}
//查看队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
//空时返回-1
if(myCircularQueueIsEmpty(obj))
return -1;
//因为返回的是rear-1位置上的数据,当rear>0时,查看的位置时rear-1,当rear=0时就是查看k位置的数据了
int tmp=obj->arr[(obj->rear-1+obj->k+1)%(obj->k+1)];
return tmp;
}
//释放
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->arr);
free(obj);
}
循环双端队列
1、循环双端队列就是在循环队列的基础上增加了一些接口,如:可以进行队头的插入,进行尾部的删除。
2、实现的功能接口:
实现 MyCircularDeque 类:
(1)MyCircularDeque(int k) :构造函数,双端队列最大为 k 。
(2)boolean insertFront():将一个元素添加到双端队列头部。 如果操作成功返回 true ,否则返回 false 。
(3)boolean insertLast() :将一个元素添加到双端队列尾部。如果操作成功返回 true ,否则返回 false 。
(4)boolean deleteFront() :从双端队列头部删除一个元素。 如果操作成功返回 true ,否则返回 false 。
(5)boolean deleteLast() :从双端队列尾部删除一个元素。如果操作成功返回 true ,否则返回 false 。
(6)int getFront() ):从双端队列头部获得一个元素。如果双端队列为空,返回 -1 。
(7)int getRear() :获得双端队列的最后一个元素。 如果双端队列为空,返回 -1 。
(8) boolean isEmpty() :若双端队列为空,则返回 true ,否则返回 false 。(9)boolean isFull() :若双端队列满了,则返回 true ,否则返回 false 。
3、设计
(1)用双向链表的节点,这样方便找到尾部的上一个节点,利于队尾的删除。
(2)定义size来判断空和满,再定义两个节点指针,分别指向队头(front),队尾(rear),容量(k),前驱指针(next),后驱指针(next1)。
(3)判断为空,当size=0时为空。
(4)判断是否满,当size=k时为满。
(5)队头插入数据,申请一个节点tmp,再将tmp和front连起来,最后front=tmp即可
(6)队尾插入数据,申请一个节点tmp,再将tmp和rear连接起来,最后rear=tmp即可
(7)队头删除,先保存队头的后一个节点next,再将front释放,最后将front=next并把front->next1=NULL即可,注意顺序不能乱。
(8)队尾删除,先保存前一个节点next1,再将rear释放,最后将rear=next1并把rear->next=NULL即可,注意顺序不能乱。
(9)获取队头元素,直接返回front的数据即可。
(10)获取队尾元素,直接返回rear的数据即可。
4、代码实现:
//双向链表的结构体
typedef struct ls
{
//前驱
struct ls *next;
//后驱
struct ls *next1;
//数据
int val;
}ls;
class MyCircularDeque {
public:
//初始化
MyCircularDeque(int k) {
//容量
this->k=k;
//大小
this->size=0;
this->rear=NULL;
this->front=NULL;
}
//队头插入数据
bool insertFront(int value) {
// 满了,就返回
if(isFull())
return false;
//没满
//申请一个节点
ls *tmp(ls*)malloc(sizeof(ls));
tmp->next=NULL;
tmp->next1=NULL;
tmp->val=value;
//空的话头和尾指向第一个节点
if(front==NULL)
{
front=rear=tmp;
}
//不空,插入头
else
{
front->next1=tmp;
tmp->next=front;
front=tmp;
}
//大小加1
size++;
return true;
}
//队尾插入数据
bool insertLast(int value) {
if(isFull())
return false;
//申请节点
ls *tmp=(ls*)malloc(sizeof(ls));
tmp->next=NULL;
tmp->next1=NULL;
tmp->val=value;
if(rear==NULL)
{
front=rear=tmp;
}
//尾插到rear后面
else
{
tmp->next1=rear;
rear->next=tmp;
rear=tmp;
}
//大小加1
size++;
return true;
}
//删队头
bool deleteFront() {
//为空
if(isEmpty())
return false;
//只有一个元素
ls *tmp=front->next;
free(front);
if(tmp==NULL)
front=rear=tmp;
//多个元素
else
{
front=tmp;
front->next1=NULL;
}
//大小-1
size--;
return true;
}
//删队尾
bool deleteLast() {
if(isEmpty())
return false;
//只有一个元素
ls *tmp=rear->next1;
free(rear);
if(tmp==NULL)
{
rear=front=tmp;
}
else
{
tmp->next=NULL;
rear=tmp;
}
// 大小-1
size--;
return true;
}
//显示头元素
int getFront() {
//为空
if(isEmpty())
return -1;
//直接返回头节点的数据
return front->val;
}
//显示尾节点元素
int getRear() {
//为空
if(isEmpty())
return -1;
//直接返回尾节点数据
return rear->val;
}
//判断是否为空
bool isEmpty() {
//当size==0是为空
return size==0;
}
//判断是否为满
bool isFull() {
//size==k就满了
return size==k;
}
//释放链表
~MyCircularDeque()
{
ls* tmp=front;
while(tmp)
{
ls*p=tmp->next;
free(tmp);
tmp=p;
}
}
//头和尾
ls* front;
ls* rear;
//容量和大小
int k;
int size;
};
以上就是我的分享了
最后,感谢大家的观看!