C++自定义类型循环队列实现 |21xrx.com

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

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

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

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

评论区

()

相似文章