## C++循环队列
简介
循环队列是一种基于数组实现的队列，它克服了普通队列“假溢出”的问题。 普通队列在数组中使用两个指针：`front` 指向队头元素，`rear` 指向队尾元素的下一个位置。当 `rear` 指针到达数组末尾时，即使数组中还有空闲空间，也无法继续入队，这就是“假溢出”。循环队列通过让 `rear` 指针绕回到数组开头来解决这个问题，从而充分利用数组空间。### 1. 循环队列的数据结构循环队列通常使用一个数组和两个整数变量来实现：
`data[]`:
一个数组，用于存储队列元素。
`front`:
指向队头元素的索引。
`rear`:
指向队尾元素的下一个位置的索引。为了区分队列为空和队列已满的情况，需要引入一个额外的变量 `size` 来记录队列中元素的数量，或者采用其他策略，例如约定当 `front == rear` 时队列为空，当 `(rear + 1) % capacity == front` 时队列为满（其中 `capacity` 是数组的容量）。### 2. 循环队列的操作以下描述循环队列的常见操作，并提供C++代码示例：#### 2.1 入队 (Enqueue)入队操作将一个元素添加到队列尾部。```c++
#include template
class CircularQueue {
private:T data[capacity];int front = 0;int rear = 0;int size = 0;public:bool enqueue(const T& item) {if (isFull()) {std::cout << "Queue is full!\n";return false;}data[rear] = item;rear = (rear + 1) % capacity;size++;return true;}// ... other methods ...
};
````isFull()` 方法用来检查队列是否已满：```c++
bool isFull() const { return size == capacity; }
```#### 2.2 出队 (Dequeue)出队操作将队列头部的元素移除。```c++
template
T CircularQueue::dequeue() {if (isEmpty()) {std::cout << "Queue is empty!\n";// 处理空队列的情况，例如抛出异常或返回默认值return T{}; //返回默认构造的T对象}T item = data[front];front = (front + 1) % capacity;size--;return item;
}
````isEmpty()` 方法用来检查队列是否为空：```c++
bool isEmpty() const { return size == 0; }
```#### 2.3 获取队头元素 (Front)获取队头元素但不移除它。```c++
template
T CircularQueue::front() const {if (isEmpty()) {std::cout << "Queue is empty!\n";// 处理空队列的情况return T{}; //返回默认构造的T对象}return data[front];
}
```#### 2.4 获取队列大小 (Size)```c++
template
int CircularQueue::size() const {return size;
}
```### 3. 完整的 C++ 代码示例```c++
#include template
class CircularQueue {
private:T data[capacity];int front = 0;int rear = 0;int size = 0;public:bool enqueue(const T& item) {if (isFull()) {std::cout << "Queue is full!\n";return false;}data[rear] = item;rear = (rear + 1) % capacity;size++;return true;}T dequeue() {if (isEmpty()) {std::cout << "Queue is empty!\n";return T{}; //返回默认构造的T对象}T item = data[front];front = (front + 1) % capacity;size--;return item;}T front() const {if (isEmpty()) {std::cout << "Queue is empty!\n";return T{}; //返回默认构造的T对象}return data[front];}bool isEmpty() const { return size == 0; }bool isFull() const { return size == capacity; }int size() const { return size; }
};int main() {CircularQueue queue;queue.enqueue(10);queue.enqueue(20);queue.enqueue(30);std::cout << "Front: " << queue.front() << std::endl; // Output: Front: 10std::cout << "Dequeue: " << queue.dequeue() << std::endl; // Output: Dequeue: 10queue.enqueue(40);queue.enqueue(50);// queue.enqueue(60); // This will print "Queue is full!"while (!queue.isEmpty()) {std::cout << queue.dequeue() << " ";}std::cout << std::endl; // Output: 20 30 40 50return 0;
}
```### 4. 优点和缺点
优点:
高效利用空间:
避免了普通队列的“假溢出”问题，充分利用数组空间。
实现简单:
相对容易理解和实现。
缺点:
容量固定:
队列的容量在创建时就固定了，无法动态调整。 需要预先估计最大容量。
可能需要模运算:
使用模运算 (`%`) 可能会略微降低效率，但现代编译器通常能够很好地优化模运算。这个详细的解释和代码示例应该能够帮助你理解C++循环队列。记住根据你的具体需求调整队列的容量。 对于需要动态调整容量的情况，可以考虑使用链表来实现队列。
C++循环队列**简介**循环队列是一种基于数组实现的队列，它克服了普通队列“假溢出”的问题。 普通队列在数组中使用两个指针：`front` 指向队头元素，`rear` 指向队尾元素的下一个位置。当 `rear` 指针到达数组末尾时，即使数组中还有空闲空间，也无法继续入队，这就是“假溢出”。循环队列通过让 `rear` 指针绕回到数组开头来解决这个问题，从而充分利用数组空间。
1. 循环队列的数据结构循环队列通常使用一个数组和两个整数变量来实现：* **`data[]`:** 一个数组，用于存储队列元素。
* **`front`:** 指向队头元素的索引。
* **`rear`:** 指向队尾元素的下一个位置的索引。为了区分队列为空和队列已满的情况，需要引入一个额外的变量 `size` 来记录队列中元素的数量，或者采用其他策略，例如约定当 `front == rear` 时队列为空，当 `(rear + 1) % capacity == front` 时队列为满（其中 `capacity` 是数组的容量）。
2. 循环队列的操作以下描述循环队列的常见操作，并提供C++代码示例：
2.1 入队 (Enqueue)入队操作将一个元素添加到队列尾部。```c++
include template
class CircularQueue {
private:T data[capacity];int front = 0;int rear = 0;int size = 0;public:bool enqueue(const T& item) {if (isFull()) {std::cout << "Queue is full!\n";return false;}data[rear] = item;rear = (rear + 1) % capacity;size++;return true;}// ... other methods ...
};
````isFull()` 方法用来检查队列是否已满：```c++
bool isFull() const { return size == capacity; }
```
2.2 出队 (Dequeue)出队操作将队列头部的元素移除。```c++
template
T CircularQueue::dequeue() {if (isEmpty()) {std::cout << "Queue is empty!\n";// 处理空队列的情况，例如抛出异常或返回默认值return T{}; //返回默认构造的T对象}T item = data[front];front = (front + 1) % capacity;size--;return item;
}
````isEmpty()` 方法用来检查队列是否为空：```c++
bool isEmpty() const { return size == 0; }
```
2.3 获取队头元素 (Front)获取队头元素但不移除它。```c++
template
T CircularQueue::front() const {if (isEmpty()) {std::cout << "Queue is empty!\n";// 处理空队列的情况return T{}; //返回默认构造的T对象}return data[front];
}
```
2.4 获取队列大小 (Size)```c++
template
int CircularQueue::size() const {return size;
}
```
3. 完整的 C++ 代码示例```c++
include template
class CircularQueue {
private:T data[capacity];int front = 0;int rear = 0;int size = 0;public:bool enqueue(const T& item) {if (isFull()) {std::cout << "Queue is full!\n";return false;}data[rear] = item;rear = (rear + 1) % capacity;size++;return true;}T dequeue() {if (isEmpty()) {std::cout << "Queue is empty!\n";return T{}; //返回默认构造的T对象}T item = data[front];front = (front + 1) % capacity;size--;return item;}T front() const {if (isEmpty()) {std::cout << "Queue is empty!\n";return T{}; //返回默认构造的T对象}return data[front];}bool isEmpty() const { return size == 0; }bool isFull() const { return size == capacity; }int size() const { return size; }
};int main() {CircularQueue queue;queue.enqueue(10);queue.enqueue(20);queue.enqueue(30);std::cout << "Front: " << queue.front() << std::endl; // Output: Front: 10std::cout << "Dequeue: " << queue.dequeue() << std::endl; // Output: Dequeue: 10queue.enqueue(40);queue.enqueue(50);// queue.enqueue(60); // This will print "Queue is full!"while (!queue.isEmpty()) {std::cout << queue.dequeue() << " ";}std::cout << std::endl; // Output: 20 30 40 50return 0;
}
```
4. 优点和缺点**优点:*** **高效利用空间:** 避免了普通队列的“假溢出”问题，充分利用数组空间。
* **实现简单:** 相对容易理解和实现。**缺点:*** **容量固定:** 队列的容量在创建时就固定了，无法动态调整。 需要预先估计最大容量。
* **可能需要模运算:** 使用模运算 (`%`) 可能会略微降低效率，但现代编译器通常能够很好地优化模运算。这个详细的解释和代码示例应该能够帮助你理解C++循环队列。记住根据你的具体需求调整队列的容量。 对于需要动态调整容量的情况，可以考虑使用链表来实现队列。
