C++实现循环队列 |21xrx.com

C++实现循环队列

2023-07-13 12:54:56 深夜i -- --

C++ 循环队列实现

循环队列是队列的一种常用实现方式，在C++中可以使用数组来实现。循环队列能够解决队列的顺序存储容易造成空间浪费的问题。

循环队列的实现方式是将数组当做一个环来看待，在队列头和队列尾相连的位置称为循环点。在空间上，我们可以预留一个位置来区分队列是否满了。队列的头指针front和尾指针rear分别指向队首和队尾元素。

下面是一个简单的C++实现循环队列的代码：


const int MAXSIZE = 5;  // 循环队列的大小
class MyQueue{
private:
  int data[MAXSIZE];
  int front;     // 队列头
  int rear;      // 队列尾
public:
  MyQueue()
    front = 0;
    rear = 0;
  
  ~MyQueue()
  
  // 判断队列是否为空
  bool isEmpty()
    return front == rear;
  
  // 判断队列是否为满
  bool isFull(){
    return (rear+1)%MAXSIZE == front;
  }
  // 入队
  bool enQueue(int val){
    if(isFull())
      return false;
    
    data[rear] = val;
    rear = (rear+1)%MAXSIZE;
    return true;
  }
  // 出队
  bool deQueue(int &val){
    if(isEmpty())
      return false;
    
    val = data[front];
    front = (front+1)%MAXSIZE;
    return true;
  }
  // 获取队首元素
  int getFront(){
    if(isEmpty())
      return -1;
    
    return data[front];
  }
  // 获取队尾元素
  int getRear(){
    if(isEmpty())
      return -1;
    
    return data[(rear-1+MAXSIZE)%MAXSIZE];
  }
  // 获取队列中元素个数
  int getSize(){
    return (rear-front+MAXSIZE)%MAXSIZE;
  }
};

在代码中，首先定义了循环队列的大小为5。然后实现了队列的初始化、判断队列是否为空/满、入队、出队、获取队首元素、获取队尾元素和获取队列中元素个数的方法。其中最重要的是判断队列是否满了，这里使用了模运算实现循环队列。

循环队列的操作时间复杂度为O(1)，因为不需要移动元素，只需要移动指针即可。但是要注意队列为空和队列为满时的特殊情况。

总之，循环队列是一种基于数组实现的队列，能够有效解决顺序存储造成的空间浪费问题，使用模运算来实现循环，能够很好地进行队列操作，C++实现循环队列非常简单。

上一篇: idea打包java可执行jar包

下一篇: Java多线程加锁的三种方法探究

评论区

()

相似文章