在Dec++中如何实现栈、队列的应用算法:循环队列中利用count记录队中元素个数/设置标志位flag来区分队空/队满,实现基本操作。
时间: 2024-11-14 15:23:37 浏览: 38
在C++中,循环队列是一种特殊的线性表结构,它通过两个指针front和rear分别表示队首和队尾,当队列满时, rear 指针会重新指向 queue 的开始位置,形成一个循环。以下是使用 C++ 实现循环队列的基本操作(包括入队 Enqueue 和出队 Dequeue),并利用 count 记录元素个数以及 flag 标志判断队空和队满:
```cpp
#include <iostream>
using namespace std;
template <typename T>
class CircularQueue {
private:
T* queue; // 存储数据的数组
int capacity; // 队列容量
int front; // 队首索引
int rear; // 队尾索引
int count; // 元素个数
bool isFull; // 标志队是否已满
bool isEmpty; // 标志队是否为空
public:
CircularQueue(int size) : capacity(size), front(0), rear(0), count(0), isFull(false), isEmpty(true) {
queue = new T[capacity];
}
~CircularQueue() {
delete[] queue;
}
// 入队操作 (Enqueue)
void enqueue(T data) {
if (isFull && rear != front) { // 如果队满且不是首次溢出
rear = (rear + 1) % capacity; // 更新 rear 并使其回到队首
}
queue[rear] = data; // 添加新元素到队尾
rear = (rear + 1) % capacity; // 更新 rear
count++; // 提升元素计数
isEmpty = false; // 队列不再为空
if (rear == front) isFull = true; // 当 rear 回到 front 时,队满
}
// 出队操作 (Dequeue)
void dequeue() {
if (isEmpty) { // 如果队空
throw runtime_error("Queue is empty"); // 抛出异常
}
T data = queue[front]; // 获取队首元素
front = (front + 1) % capacity; // 更新 front
count--; // 减少元素计数
if (front == rear) isFull = false; // 当 front 到达 rear 时,队列非满
isEmpty = count == 0; // 队列为空的情况
}
// 查询队列长度 (Size)
int size() const {
return count;
}
// 判断队空 (IsEmpty)
bool empty() const {
return isEmpty;
}
// 判断队满 (IsFull)
bool full() const {
return isFull;
}
};
// 示例
int main() {
CircularQueue<int> cq(5);
cq.enqueue(1); // ...其他元素...
while (!cq.empty()) {
cout << cq.dequeue() << " ";
}
cout << "\nQueue Size: " << cq.size() << endl;
return 0;
}
```
阅读全文