【C++/数据结构】队列

零.导言

        和上次学习的栈一样，队列是一种数据结构，在后续的学习中可能经常使用，因此我们今天就来学习如何实现队列，以更好地使用它。

---

一.队列的模拟实现

        在类（class）Queue 中，包含成员变量和成员函数；同时，队列的实现要相对复杂一些。

我们先看代码：

#include<iostream> #include<cassert> using namespace std; typedef int QueueDataType; class Queue { public: Queue() { _phead = _ptail = nullptr; _size = 0; } ~Queue() { QueueNode* pcur = _phead; while (pcur) { QueueNode* next = pcur->_next; free(pcur); pcur = next; } _phead = _ptail = nullptr; _size = 0; } void Push(QueueDataType n) { QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == nullptr) { perror("malloc fail!"); exit(1); } newnode->_val = n; newnode->_next = nullptr; if (_phead == nullptr) { _phead = _ptail = newnode; } else { _ptail->_next = newnode; _ptail = _ptail->_next; } _size++; } bool isEmpty() { return _phead == nullptr; } void Pop() { assert(!isEmpty()); if (_phead == _ptail) { free(_phead); _phead = _ptail = nullptr; } else { QueueNode* next = _phead->_next; free(_phead); _phead = next; } _size--; } QueueDataType Front() { assert(!isEmpty()); return _phead->_val; } QueueDataType Back() { assert(!isEmpty()); return _ptail->_val; } int Size() { return _size; } private: class QueueNode { friend class Queue; QueueDataType _val; QueueNode* _next; }; QueueNode* _phead; QueueNode* _ptail; int _size; };

---

二.队列的相关解释

        如上：队列的实现需要定义两个结构体，第一是 QueueNode ，是链表的节点类型；第二是 Queue ，指向队列的头和尾。

        其中：构造函数和析构函数很容易辨认，Push 是向队尾插入数据，Pop 是从队头出数据，Front 是取队头数据，Back 是取队尾数据，Size 是返回有效元素个数。

---

三.队列的特性

        队列的特性是：所有数据都只能从队尾入，从队头出。和堆的形式相反，先进先出。运用这个特性，我们可以便捷的解决堆不好解决的问题。

---

四.相关链接

        【C++/数据结构】栈-CSDN博客

---

完