链队列及(C++)实现详解
围绕链表构建的动态队列比静态队列更直观。一个动态队列将作为一个空链表开始。在第一次入队操作中,增加了一个结点,并且 front 和 rear 指针均指向它。随着每个新项目被添加到队列中,新的结点被添加到链表的后面,并且 rear 指针被更新以指向新结点。
当有项目要出队时,使 front 指向链表中的下一个结点,然后删除先前 front 所指向的结点。 图 1 显示了一个动态队列的结构。
图 1 实现为链表的动态队列
动态整数队列类 DynIntQueue 的代码清单如下所示:
当有项目要出队时,使 front 指向链表中的下一个结点,然后删除先前 front 所指向的结点。 图 1 显示了一个动态队列的结构。
图 1 实现为链表的动态队列
动态整数队列类 DynIntQueue 的代码清单如下所示:
//DynIntQueue.h class DynIntQueue { struct QueueNode { int value; QueueNode *next; QueueNode(int value1, QueueNode *next1 = nullptr) { value = value1; next = next1; } }; // These track the front and rear of the queue QueueNode *front; QueueNode *rear; public: // Constructor and Destructor DynIntQueue(); ~DynIntQueue(); // Member functions void enqueue(int); void dequeue(int &); bool isEmpty() const; void clear(); }; //DynIntQueue.cpp #include <iostream> #include "DynIntQueue.h" #include <cstdlib> using namespace std; DynIntQueue::DynIntQueue() { front = nullptr; rear = nullptr; } DynIntQueue::~DynIntQueue() { QueueNode * garbage = front; while (garbage != nullptr) { front = front->next; garbage->next = nullptr; delete garbage; garbage = front; } } void DynIntQueue::enqueue(int num) { if (isEmpty()) { front = new QueueNode(num); rear = front; } else { rear->next = new QueueNode(num); rear = rear->next; } } void DynIntQueue::dequeue(int &num) { QueueNode *temp = nullptr; if (isEmpty()) { cout << "The queue is empty.\n"; exit(1); } else { num = front->value; temp = front; front = front->next; delete temp; } } bool DynIntQueue::isEmpty() const { if (front == nullptr) return true; else return false; } void DynIntQueue::clear() { int value; // Dummy variable for dequeue while (!isEmpty()) dequeue(value); }下面的程序是一个驱动模块程序,它演示了 DynIntQueue 类的使用:
// This program demonstrates the DynIntQueue class #include <iostream> #include "DynIntQueue.h" using namespace std; int main() { DynIntQueue iQueue; cout << "Enqueuing 5 items...\n"; // Enqueue 5 items for (int k = 1; k <= 5; k++) iQueue.enqueue(k*k); // Deqeue and retrieve all items in the queue cout << "The values in the queue were: \n"; while (!iQueue.isEmpty()) { int value; iQueue.dequeue(value); cout << value << " "; } return 0; }程序输出结果:
Enqueuing 5 items...
The values in the queue were:
1 4 9 16 25
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频