修改有关循环队列的设计,取消队 尾指针rear,以front和length分 别表示循环队列中的队头位置和队列中所含元素的个数。试完成循环队列判断队空、入队和出队函数的实现。
时间: 2024-10-09 19:16:21 浏览: 51
在修改后的循环队列设计中,我们不再使用传统的队尾指针`rear`,而是使用`front`表示队头的位置,`length`表示队列中的元素个数。这里是一个基于这种设计的C++实现:
```cpp
#include <iostream>
using namespace std;
class CircularQueue {
private:
int front; // 队头索引
int capacity; // 队列容量
int count; // 队列元素个数
int* buffer; // 存储队列元素的数组
public:
// 构造函数,初始化队列为空
CircularQueue(int size) {
front = -1;
capacity = size;
count = 0;
buffer = new int[capacity];
}
// 检查队列是否为空
bool isEmpty() {
return front == -1 || front >= count;
}
// 入队操作
void enqueue(int value) {
if (count == capacity) {
cout << "Queue is full, cannot enqueue." << endl;
return;
}
if (front == -1) {
front = 0;
} else {
front = (front + 1) % capacity; // 循环更新队头
}
buffer[front] = value;
count++;
}
// 出队操作
int dequeue() {
if (isEmpty()) {
throw runtime_error("Queue is empty");
}
int value = buffer[(front + count - 1) % capacity]; // 循环获取队尾元素
if (front == count - 1) { // 清理队尾,当只剩下一个元素时
delete[] buffer;
buffer = nullptr;
front = -1;
count = 0;
} else {
front = (front + 1) % capacity; // 更新队头
count--;
}
return value;
}
~CircularQueue() {
if (buffer != nullptr) {
delete[] buffer;
}
}
};
// 示例使用
int main() {
CircularQueue cq(5);
cq.enqueue(1);
cq.enqueue(2);
cq.enqueue(3);
if (!cq.isEmpty()) {
cout << "Dequeued element: " << cq.dequeue() << endl;
}
return 0;
}
```
在这个实现中,入队时,我们将新元素存储在`front`指向的位置,并更新队头。出队时,我们首先检查队列是否为空,然后根据循环性质确定要删除的元素,同时处理特殊情况,如队列仅剩一个元素的情况。
阅读全文