假设以数组base[m]存放循环队列的元素,同时设变量 rear 和 qlen 分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示:队空的条件:Q.qlen==0; 队满的条件:Q.qlen==m。
时间: 2024-10-27 20:02:38 浏览: 28
在 C++ 中,我们可以使用数组来实现循环队列(Circular Queue),因为它的性质非常适合这种数据结构,其中队尾和队首可以交替进行插入和删除操作而无需移动其他元素。这里我会给出一个简单的实现,包括 `enqueue`(入队)和 `dequeue`(出队)操作。
```cpp
#include <iostream>
class CircularQueue {
private:
int base[m]; // 存放元素的数组
int rear; // 队尾索引
int qlen; // 队列长度
public:
// 初始化队列
CircularQueue(int m) : rear(0), qlen(0), base{0} {}
// 入队操作(当队列未满)
void enqueue(int value) {
if (qlen < m) {
base[rear] = value;
rear = (rear + 1) % m; // 循环队列,后移一位
qlen++;
} else {
std::cout << "Queue is full.\n";
}
}
// 出队操作(当队列非空)
bool dequeue() {
if (qlen > 0) {
int removedValue = base[rear];
base[rear] = 0; // 或者设置为默认值或空,视情况而定
rear = (rear - 1 + m) % m; // 后移一位,如果溢出则绕回开始
qlen--;
return true; // 返回成功标志
} else {
std::cout << "Queue is empty.\n";
return false;
}
}
// 检查队列是否为空
bool isEmpty() const {
return qlen == 0;
}
// 检查队列是否已满
bool isFull() const {
return qlen == m;
}
};
int main() {
CircularQueue Q(m);
// 使用队列
Q.enqueue(1); // 入队
Q.dequeue(); // 出队
if (Q.isEmpty()) {
std::cout << "Queue is now empty.\n";
}
return 0;
}
```
在这个实现中,`enqueue` 函数检查队列是否已满,如果不满则将新元素添加到队尾并更新队尾指针;如果满,则输出错误消息。同样地,`dequeue` 函数检查队列是否为空,如果非空则移除队尾元素,更新队尾指针和队列长度,否则返回队列为空的消息。
阅读全文