行业知识
循环队列与循环双端队列
文章目录
- 前言
- 循环队列
- ���环双端队列
前言
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;};最后，感谢大家的观看！
上一篇：宝塔面板怎么运行asp？
下一篇：魔兽先行服务器怎么进去?
