队列，同栈一样是一个非常基础、常用的数据结构。
队列的基本操作：后进先出。
队列有以下类型：
1. 顺序队列
2. 链式队列
3. 循环队列：队满条件：(tail + 1) % n == head，队空条件：head == tail，tail 位置不存储数据
4. 阻塞队列
5. 并发队列
6. 优先队列
循环队列是是顺序队列，为了优化顺序队列，极好避免空间浪费，仅 tail 位置不存放数据。
阻塞队列和并发队列这里不进行讲解。
常用的队列是链式队列。
优先队列是基于二叉堆实现的，一种顺序结构，这在后续会详细讲解。
显然，队列会比栈更加复杂一些，但是相比更高级的数据结构而言，自然简单许多。
为了满足后进先出规则，相比于栈只需要一个 top 指针而言，队列需要两个指针：队头指针 head，队尾指针 tail。
同样，c/c++开发分享DSA_06：队列模拟一个 c++ stl queue。接口及注释已经写于源码。
注：为了区别栈的接口，源码中将 push、pop 接口替换为 enqueue、dequeue。
队列基础插入模型：
源码：
#include <iostream> #include <iomanip> /* 链式队列 */ template<typename _ty> class queue { // 定义节点结构 struct node { _ty data; node* next = nullptr; explicit node(const _ty& _data) :data(_data) {} }; public: queue() = default; ~queue(); // 队列是否为空 bool empty() const { return n_size == 0; } // or return head/tail == nullptr // 返回队列长度 size_t size() const { return n_size; } // 返回队头数据引用 _ty& front() const; // 返回队尾数据引用 _ty& back() const; // 压队列 void enqueue(const _ty& _data); // 出队列 void dequeue(); private: node* head = nullptr; node* tail = nullptr; size_t n_size = 0; }; template<typename _ty> queue<_ty>::~queue() { node* temp = head; while (temp != nullptr) { head = head->next; delete temp; temp = head; } tail = nullptr; n_size = 0; } template<typename _ty> _ty& queue<_ty>::front() const { if (head == nullptr) throw std::exception("queue is empty."); else return head->data; } template<typename _ty> _ty& queue<_ty>::back() const { if (tail == nullptr) throw std::exception("queue is empty."); else return tail->data; } template<typename _ty> void queue<_ty>::enqueue(const _ty& _data) { node* temp = new node(_data); if (tail == nullptr) { head = tail = temp; } else { tail->next = temp; tail = temp; } temp = nullptr; ++n_size; } template<typename _ty> void queue<_ty>::dequeue() { if (head == nullptr) return; node* temp = head; head = head->next; delete temp; --n_size; } int main() { std::cout.setf(std::ios_base::boolalpha); queue<int> qu; std::cout << "empty?: " << qu.empty() << std::endl; std::cout << "push datas..." << std::endl; for (int i = 0; i < 5; ++i) qu.enqueue(i + 1); std::cout << "now empty?: " << qu.empty() << std::endl; std::cout << "now size: " << qu.size() << std::endl; std::cout << "now front: " << qu.front() << std::endl; std::cout << "now back: " << qu.back() << std::endl; std::cout << "dequeue..." << std::endl; qu.dequeue(); std::cout << "now empty?: " << qu.empty() << std::endl; std::cout << "now size: " << qu.size() << std::endl; std::cout << "now front: " << qu.front() << std::endl; std::cout << "now back: " << qu.back() << std::endl; return 0; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/599986.html