C++实现链式存储队列

"3.5队列链式存储主要探讨了如何使用链式结构来实现队列，并通过C++的类模板定义了一个链队列，包括其构造、入队、出队等基本操作。" 在计算机科学中，队列是一种线性数据结构，遵循先进先出（FIFO）的原则。在链式存储的队列中，元素不是存储在连续的内存位置，而是通过节点间的链接来组织。链队列通常包含两个指针，一个称为`front`，指向队列的头部，即最早进入的元素；另一个称为`rear`，指向队列的尾部，用于添加新元素。 链队列的非空状态如下所示： ``` front a1 a2 an ∧ rear ``` 其中，`front`指向队列的第一个元素，`rear`指向当前队列的最后一个元素。 链队列的空状态则是： ``` front ∧ rear ``` 此时，`front`和`rear`都指向同一个空节点。 在C++中，我们可以通过类模板来定义链队列，如下所示： ```cpp template<class DataType> class LinkQueue { public: LinkQueue(); // 构造函数 ~LinkQueue(); // 析构函数 void EnQueue(DataType x); // 入队操作 DataType DeQueue(); // 出队操作 DataType GetQueue(); // 获取队首元素 bool Empty(); // 判断队列是否为空 private: Node<DataType>* front, *rear; // 队首和队尾指针 }; ``` 链队列的构造函数初始化`front`和`rear`，创建一个空的链表： ```cpp template<class DataType> LinkQueue<DataType>::LinkQueue() { front = new Node<DataType>; front->next = NULL; rear = front; } ``` 入队操作（EnQueue）在链队列的尾部插入新元素： ```cpp template<class DataType> void LinkQueue<DataType>::EnQueue(DataType x) { s = new Node<DataType>; s->data = x; s->next = NULL; rear->next = s; rear = s; } ``` 出队操作（DeQueue）从队列头部移除并返回元素，更新`front`指针： ```cpp template<class DataType> DataType LinkQueue<DataType>::DeQueue() { if (front->next == NULL) throw "Queue is empty!"; Node<DataType>* p = front->next; front->next = p->next; if (p->next == NULL) // 如果出队后队列为空 rear = front; return p->data; } ``` 此外，`GetQueue`方法可以获取队首元素而不删除，`Empty`方法检查队列是否为空。这些基本操作构成了链队列的核心，使得我们可以高效地处理队列的各种操作。在实际应用中，链队列常用于任务调度、缓冲区管理等场景。