【C++初阶】12. Stack(栈)和Queue(队列)-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++初阶】12. Stack(栈)和Queue(队列)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 栈和队列的介绍

栈的介绍
队列的介绍
【C++初阶】12. Stack(栈)和Queue(队列),C++初阶,c++,开发语言

2. 栈和队列的使用

最小栈

【C++初阶】12. Stack(栈)和Queue(队列),C++初阶,c++,开发语言

栈的压入、弹出序列

【C++初阶】12. Stack(栈)和Queue(队列),C++初阶,c++,开发语言

逆波兰表达式求值

【C++初阶】12. Stack(栈)和Queue(队列),C++初阶,c++,开发语言

拓展：如何从中缀变为后缀

【C++初阶】12. Stack(栈)和Queue(队列),C++初阶,c++,开发语言

3. 两种设计模式

设计模式目前分为26种，这里就只介绍两种

适配器模式
迭代器模式

在日常生活中，我们常见的适配器通常为电源适配器(充电器) – 电源电压为220v，但是我们的设备并不需要这么高的电压(起保护作用) 需要将电源电压适配到我们所需的电压:50v/36v…
适配器模式：将已有的东西通过封装转换成我们所需的东西
迭代器模式：不暴露底层的实现细节，经过封装后提供统一的方式来访问容器

4. 栈的模拟实现

gitee提交代码：栈的模拟实现
栈遵循"先入后出"的原则，我们是否需要重新实现一个数据结构呢？–能不能采用之前学习的数据结构进行转换呢？
【C++初阶】12. Stack(栈)和Queue(队列),C++初阶,c++,开发语言
加上缺省值

	template <class T,class Container = vector<T>>

5. 队列的模拟实现

gitee代码提交：队列的实现
【C++初阶】12. Stack(栈)和Queue(队列),C++初阶,c++,开发语言

6. deque的介绍(双端队列)

【C++初阶】12. Stack(栈)和Queue(队列),C++初阶,c++,开发语言

双端队列的结构：中控+buffer
在日常的使用场景比较少见，不像vector和list极致
使用场景：既支持头插头删，又支持尾插尾删对于随机访问和中间插入比较少
那么就是栈和队列了
所以，deque适合作为栈和队列的适配器
【C++初阶】12. Stack(栈)和Queue(队列),C++初阶,c++,开发语言

7. 优先级队列

7.1 优先级队列的介绍和使用

优先级队列文档介绍
【C++初阶】12. Stack(栈)和Queue(队列),C++初阶,c++,开发语言

数组中的第K个最大元素

思路1：建大堆 + pop K次

【C++初阶】12. Stack(栈)和Queue(队列),C++初阶,c++,开发语言

思路2：建K个数小堆

【C++初阶】12. Stack(栈)和Queue(队列),C++初阶,c++,开发语言

7.2 优先级队列的模拟实现

1. 基本框架的搭建

#include <iostream>
#include <vector>
using namespace std;
namespace hx
{
	template<class T,class Container = vector<T>>
	class priority_queue
	{
	public:

		// 建堆
		// 拿迭代器区间初始化
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:_con(first,last)
		{
			// 从最后一个非叶子结点开始向下调整 -- O(N)
			for (int i = (_con, size() - 1 - 1) / 2; i >= 0; i--)
			{
				adjust_down(i);
			}
			// 也可以采用向上调整建堆的方式
			// 但是时间复杂度是O(N*logN) -- 移动的路径更长
		}

		void adjust_down()
		{

		}
		void adjust_up()
		{

		}
		void push(const T& x)
		{
			// vector的尾插
			_con.push_back(x);
			// 将刚刚尾插的元素进行向上调整
			adjust_up(_con.size()-1);
		}
		void pop()
		{
			// 将堆顶的元素和最后一个元素交换
			swap(_con[0], _con[_con.size() - 1]);			
			// 堆顶元素删除
			_con.pop_back();
			// 再将换到堆顶的元素进行向下调整找到新的堆顶元素
			adjust_down(0);
		}
		const T& top() const
		{
			return _con[0];
		}
		bool empty() const
		{
			return _con.empty();
		}
		size_t size()const
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

2. 向上/下调整算法

不管是向上还是向下调整算法都面临建大堆还是建小堆的问题(都可以 – 无非就是改个判断条件)
假设我们构建的是大堆
【C++初阶】12. Stack(栈)和Queue(队列),C++初阶,c++,开发语言

		// 孩子结点 -- 往上调整
		void adjust_up(size_t child)
		{
			size_t parent = (child - 1) / 2;
			// 循环结束条件 拿child判断 当child = 0时循环结束 -- child到堆顶
			// 因为是size_t 所以不能用>=来判断(不然就是死循环)
			while (child > 0)
			{
				//大堆 -- 父 > 子
				if (_con[parent] < _con[child])
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}