21xrx.com
2025-07-13 22:42:33 Sunday
文章检索 我的文章 写文章
C++自定义类型循环队列实现
2023-06-23 12:08:14 深夜i     --     --
C++ 自定义类型 循环队列 实现

C++作为一门面向对象编程语言,在实现数据结构时通常会用到自定义类型,其中循环队列作为非常常见的一种数据结构,也可以通过自定义类型来实现。

在循环队列的实现中,需要首先定义这个自定义类型,包括队列中元素的类型和队列的相关属性。在这里,我们以实现一个整型自定义类型为例:

class MyQueue{
private:
  int *arr; // 存储队列的数组
  int front; // 队列头
  int rear; // 队列尾
  int size; // 队列的大小
public:
  MyQueue(int size); // 构造函数,初始化队列
  bool isEmpty(); // 判断队列是否为空
  bool isFull(); // 判断队列是否已满
  void enqueue(int item); // 入队操作
  int dequeue(); // 出队操作
  ~MyQueue(){ // 析构函数,释放内存
    delete[] arr;
  }
};

在这个自定义类型中,我们定义了四个关键属性:`arr`表示存储队列的数组,`front`表示队列头,`rear`表示队列尾,`size`表示队列的大小。构造函数用来初始化队列,两个函数`isEmpty`和`isFull`分别表示判断队列是否为空和已满。`enqueue`和`dequeue`则是队列的入队和出队操作。

接下来,我们需要实现具体的操作。例如:

MyQueue::MyQueue(int size){
  arr = new int[size]; // 分配内存
  front = -1; // 初始化队列头
  rear = -1; // 初始化队列尾
  this->size = size; // 初始化队列大小
}
bool MyQueue::isEmpty(){
  return front == -1; // 队列头等于-1时为空
}
bool MyQueue::isFull(){
  return (front == 0 && rear == size-1) || (rear == (front-1)%(size-1)); // 队列满的条件
}
void MyQueue::enqueue(int item){
  if(isFull()) return; // 队列已满
  if(front == -1){ // 如果队列为空,队列头和队列尾都为0
    front = rear = 0;
    arr[rear] = item;
  }else if(rear == size-1 && front != 0){ // 队列的尾部到达了最后一个元素但前面还有空位置,这时候rear指针要恢复到起始位置
    rear = 0;
    arr[rear] = item;
  }else{ // 正常情况下直接插入元素
    rear++;
    arr[rear] = item;
  }
}
int MyQueue::dequeue(){
  if(isEmpty()) return -1; // 队列为空
  int item = arr[front];
  if(front == rear){ // 队列只有一个元素时,头尾指针都要置为-1
    front = rear = -1;
  }else if(front == size-1){ // 头部指针已经到达最后一个元素,需要从头开始
    front = 0;
  }else{ // 正常情况下头部指针自增
    front++;
  }
  return item;
}

通过定义上述自定义类型和函数,我们就可以实现循环队列了。在实现其它类型的队列时同样可以借鉴这些思路。

  
  
下一篇: C++中的7的倍数

评论区