在C++中,使用数组模拟队列通常涉及到两个主要的操作:入队(enqueue)和出队(dequeue)。由于数组是一个固定大小的数据结构,当使用数组模拟队列时,需要手动管理队列的头部和尾部位置。以下是使用数组模拟队列的一种简单实现方法:
#include <iostream>
#include <vector>
class ArrayQueue {
private:
std::vector<int> data; // 使用vector来动态管理数组的大小
int front; // 队列头部的索引
int rear; // 队列尾部的索引
int count; // 队列中元素的数量
public:
ArrayQueue() : front(0), rear(-1), count(0) {}
// 入队操作
bool enqueue(int value) {
if (count == data.size()) {
// 如果队列满了,需要扩容
if (data.size() == 0 || rear == 0) {
data.resize(data.size() * 2);
} else {
// 将队列元素向前移动,重新利用数组空间
for (int i = front; i != rear + 1; ++i) {
data[i - front] = data[i];
}
rear -= front;
front = 0;
}
}
data[++rear] = value;
++count;
return true;
}
// 出队操作
bool dequeue() {
if (count == 0) {
std::cout << "Queue is empty" << std::endl;
return false;
}
if (front == rear) {
// 队列为空,重置front和rear
front = rear = 0;
} else {
++front;
}
--count;
return true;
}
// 查看队首元素
int frontValue() const {
if (count == 0) {
throw std::runtime_error("Queue is empty");
}
return data[front];
}
// 检查队列是否为空
bool isEmpty() const {
return count == 0;
}
// 获取队列的大小
int size() const {
return count;
}
};
int main() {
ArrayQueue queue;
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
std::cout << "Front value: " << queue.frontValue() << std::endl; // 输出队首元素
queue.dequeue();
std::cout << "Front value after dequeue: " << queue.frontValue() << std::endl;
std::cout << "Queue size: " << queue.size() << std::endl; // 输出队列大小
while (!queue.isEmpty()) {
std::cout << "Dequeued: " << queue.frontValue() << std::endl;
queue.dequeue();
}
return 0;
}
这个例子中,我们使用了 std::vector
来避免固定大小数组带来的限制,使得队列可以根据需要自动扩容。front
和 rear
分别指向队列的头部和尾部,count
记录队列中的元素数量。
请注意,当数组填满时,我们可以选择扩容数组或者将数组中的元素向前移动,以重新利用数组空间。在这个例子中,我们选择了后者,这样可以避免频繁的内存分配和复制操作。但是,这种方法要求数组的初始位置不为0,或者在移动元素后更新 front
和 rear
的值。