如何用C++编程语言详细地实现一个队列的数据结构,包括元素的插入和删除操作?
时间: 2024-11-30 09:14:07 浏览: 19
在C++中,我们可以使用标准库中的`std::queue`来实现队列,这是一个模板类,可以存储任意类型的元素。如果你需要自定义实现,可以考虑使用数组或链表。这里我将演示一个简单的基于动态数组的队列实现:
```cpp
template <typename T>
class CustomQueue {
private:
T* elements; // 存储元素的数组
size_t capacity; // 容量
size_t front; // 队首索引
size_t rear; // 队尾索引
public:
CustomQueue(size_t size = 0) : capacity(size), front(0), rear(0) {
if (size > 0)
elements = new T[capacity];
}
~CustomQueue() {
if (elements)
delete[] elements;
}
// 插入元素(尾部)
void enqueue(const T& value) {
if (isFull()) {
resize(capacity * 2); // 当队列满时,扩大容量
}
elements[rear++] = value; // 队尾后移一位
if (rear == capacity) rear = 0; // 循环数组索引
}
// 删除元素(头部)
T dequeue() {
if (isEmpty()) {
throw std::runtime_error("Queue is empty");
}
T result = elements[front]; // 获取队首元素
elements[front] = nullptr; // 清除队首位置
front = (front + 1) % capacity; // 队首前移一位
if (front == rear) // 队列变空
shrink_to_fit(); // 缩小数组大小,释放内存
return result;
}
// 检查队列是否为空
bool isEmpty() const {
return front == rear;
}
// 检查队列是否已满
bool isFull() const {
return rear == front + capacity;
}
private:
// 扩大数组容量
void resize(size_t new_capacity) {
T* temp = new T[new_capacity];
for (size_t i = 0; i < rear - front; ++i)
temp[i] = elements[(front + i) % capacity];
delete[] elements;
elements = temp;
capacity = new_capacity;
}
// 缩小数组容量
void shrink_to_fit() {
if (capacity / 4 > rear - front) // 只有当队列空余空间大于四分之一时才缩小
resize(capacity / 2);
}
};
```
阅读全文