文章目录

• 前言
• 循环队列
• 循环双端队列

  ---

  前言

  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;
  };
  

  以上就是我的分享了

  最后，感谢大家的观看！

   
   怎么建设网站教程  一键生成网页  家具设计网站  专业做网站建设的公司  厦门网站建设方案  网络技术开发