C++实现循环队列示例及代码详解

本文主要介绍了如何在C++中实现一个循环队列（Circular Queue）的数据结构。循环队列是一种特殊的线性表，其特点是队尾接在队头之后形成一个循环，这样可以避免在队列满时频繁地进行数据结构的扩展和收缩操作，提高了空间效率。循环队列在许多算法和数据处理场景中有广泛应用，如消息传递、任务调度等。 首先，我们来看一下关键类`cirQueue`的定义。这是一个模板类，`template<class T>`表明它接受任何类型的参数T，用于存储队列中的元素。类中包含以下成员函数： 1. 构造函数`cirQueue(int sz)`：接受一个整数参数sz，表示队列的最大容量。在构造函数内部，创建了一个大小为sz的动态数组`element`来存储元素，并初始化队头`front`和队尾`rear`指针均为0。如果内存分配失败，会输出错误信息并终止程序。 2. 析构函数`~cirQueue()`：当`cirQueue`对象不再被使用时，释放动态分配的内存，防止内存泄漏。 3. 成员函数： - `void push(const T& elem)`：用于向队列末尾添加元素。如果队列未满（即`!isFull()`），将新元素存储在`element[rear]`，然后更新`rear`指针。 - `void pop(T& elem)`：从队列头部移除元素。如果队列非空，将`element[front]`的值赋给`elem`，然后更新`front`指针。若队列为空，不执行任何操作。 - `bool empty()`：检查队列是否为空，返回`front`和`rear`是否相等。 - `int getSize()`：返回队列中元素的数量，通过计算`rear - front`（模`maxsize`）得到，因为队列是循环的。 - `void clearQueue()`：清除队列中的所有元素，将`front`和`rear`都置为0。 - `void print()`：打印队列中的所有元素，通过遍历`element`数组实现。 - `int getFront()`和`int getRear()`：分别获取队列的队头和队尾索引。 - `bool getTop(T& elem)`：尝试读取队列顶部的元素（第一个元素），并将其赋值给`elem`。由于队列是循环的，这与`front`相同，如果队列为空则无效。 - `template<typename T> friend ostream& operator<<(ostream& os, cirQueue<T>& queue)`：友元函数，用于将队列内容输出到`ostream`，如控制台，方便调试和显示队列信息。 在类的实现中，还有一个辅助函数`bool full() const`，用于检查队列是否已满，条件是`rear + 1 == front`（模`maxsize`）。如果队列已满，试图添加元素会导致溢出。 这个C++实现的循环队列提供了基本的队列操作，包括入队、出队、查看队列状态、获取队列大小和元素数量，以及清理和打印队列内容的功能。通过使用模板，这个数据结构可以适用于不同类型的元素，增强了其通用性。循环队列的特性使得它在处理有限缓冲区或循环数据流时特别有用。