在C++中实现队列是一种常见的数据结构操作,它遵循先进先出(FIFO, First In First Out)的原则。在本文中,我们将深入探讨如何使用C++编程语言创建一个链式队列,其中包括一系列基本操作,如入队(push)、出队(pop)、查看队头元素(front_element)、查看队尾元素(back_element)、获取队列元素数量(size)以及判断队列是否为空(empty)。
我们定义了一个模板类`NODE`,用于表示队列中的节点。每个节点包含一个数据成员`data`和一个指向下一个节点的指针`next`。模板参数`<class T>`允许我们创建存储不同类型数据的队列。
接着,我们定义了主类`MyQueue`,同样使用模板。在类的构造函数中,我们初始化队列的头结点和尾结点,确保它们都指向同一个空节点。这样,队列在初始状态时为空。
队列的主要操作如下:
1. **入队(push)**:在队尾添加新元素。首先创建一个新的节点,存储传入的数据,然后将其`next`指针设为`NULL`。接着,将当前的`rear`节点的`next`指针设为新节点,并更新`rear`为新节点。如果内存分配失败,程序会显示错误信息。
2. **出队(pop)**:移除并返回队头元素。首先检查队列是否为空,如果是,则提示队列为空。否则,保存队头元素的值,将`front`指向下一个节点,然后更新`front`的`next`指针。如果此时`rear`与`front`相同,意味着队列只剩下一个元素,因此将`rear`重新设置为`front`。释放被移除节点的内存。
3. **查看队头元素(front_element)**:返回队头元素的值,但不移除。如果队列为空,提示队列为空。否则,返回`front`的下一个节点(即队头元素)的`data`。
4. **查看队尾元素(back_element)**:返回队尾元素的值,但不移除。同样,队列为空时提示队列为空,否则直接返回`rear`的`data`。
5. **获取队列元素数量(size)**:遍历队列计算元素个数。从`front`开始,遍历到`rear`,每次迭代增加计数器`count`。返回最终的`count`值。
6. **判断队列是否为空(empty)**:检查`front`是否等于`rear`。相等表示队列为空,返回`true`;否则,返回`false`。
在示例代码的`_tmain`函数中,我们创建了一个`MyQueue<int>`实例,并进行了一些操作,例如检查队列的初始大小、入队元素、查看队头和队尾元素,以及出队并检查队列是否为空。
这个C++实现的链式队列具有良好的灵活性和实用性,可以处理任何类型的数据,只要满足模板类的要求。此外,通过合理地管理内存,避免了内存泄漏的问题。在实际编程中,这种实现方式可作为基础,根据具体需求进行扩展,例如添加异常处理、多线程支持或其他队列操作。