假设以数组Q[m]存放循环队列中的元素,同时设置一个标 志tag,以 tag= =0 和 tag= =1来区别在队头指针(front)和队尾指针 (rear)相等时,队列状态为“空”还是“满”。试使用C++编写与此结构相 应的插入(EnQueue)和删除(DeQueue)算法。
时间: 2024-10-10 18:15:18 浏览: 45
在C++中,我们可以设计一个基于数组的循环队列结构,其中`Q[m]`存储元素,`front`和`rear`分别表示队头和队尾指针。当队列满(即`rear - front == m - 1`且`tag = 1`),或者队列空(即`front == rear`且`tag = 0`)时,我们分别处理插入(EnQueue)和删除(DeQueue)操作。
首先,让我们定义一个简单的循环队列类:
```cpp
#include <iostream>
class CircularQueue {
private:
int capacity; // 队列容量
int front; // 队头指针
int rear; // 队尾指针
bool tag; // 标记队列状态
public:
CircularQueue(int size) : capacity(size), front(0), rear(0), tag(0) {}
// 插入元素到队尾 (EnQueue)
void enqueue(int value) {
if ((rear + 1) % capacity == front && tag == 1) {
std::cout << "Queue is full.\n";
return;
}
rear = (rear + 1) % capacity; // 循环队列的特性
Q[rear] = value;
if (front == rear) {
tag = 0; // 队列变为空
} else {
tag = 1; // 队列非空
}
}
// 删除并返回队头元素 (DeQueue)
int dequeue() {
if (front == rear && tag == 0) {
std::cout << "Queue is empty.\n";
return -1; // 返回无效值,表示队列已空
}
int removedValue = Q[front];
front = (front + 1) % capacity; // 移动队头指针
tag = (front != rear) ? 1 : 0; // 更新队列状态
return removedValue;
}
// 其他辅助函数...
};
```
在这个例子中,`enqueue()`函数会检查队列是否满,并相应调整队尾。如果队列空,它还会更新队列状态为非空。`dequeue()`函数则会在队列非空时移除队头元素,并根据实际情况更新队列状态。
阅读全文