【深入探索 C++ STL 容器适配器 stack 和 queue】 —— 数据战场的神秘指挥官，掌控代码节奏的幕后黑手

void TestConstructor()
{
	//构造空的stack
	stack<int> st;
	stack<string> st_str;
	stack<stack<int>> st_st;
	stack<vector<int>> st_vec;
 }

void TestConstructor()
{	
	// 此时st_v1的底层容器是v1
	// 栈顶为5，栈底为1
	vector<int>	v1= { 1, 2, 3 ,4, 5 };
	stack<int,vector<int>>  st_v1(v1);

	// 此时st_v2的底层容器是v2
	//栈顶为stack 栈底为queue
	vector<string>  v2 = { "queue","stack" };
	stack<string, vector<string>> st_v2(v2);
 }

void TestConstructor()
{	
	vector<int> v{ 1,3,5,7,9 };
	stack<int,vector<int>> st(v);
	//拷贝构造
	stack<int,vector<int>> st_cp(st);
 }

void Testempty()
{	
	//构造非空的stack
	vector<int> v{ 1,3,5,7,9 };
	stack<int,vector<int>> st1(v);
	if (!st1.empty())
		cout << "st1不为空" << endl;
	else
		cout << "st1为空" << endl;

	//构造空的stack
	stack<int> st2;
	if (!st2.empty())
		cout << "st2不为空" << endl;
	else
		cout << "st2为空" << endl;
 }

void Test_size_push()
{	
	vector<int> v{ 1,2,3,4,5};
	stack<int,vector<int>> st(v);
	cout << "st当前有效数据个数为：" << st.size() << endl;
	st.push(6);
	st.push(7);
	cout << "st当前有效数据个数为：" << st.size() << endl;
 }

void Test_top_pop()
{	
	vector<int> v{ 1,2,3,4,5};
	stack<int,vector<int>> st(v);
	//压栈 栈顶压入元素
	st.push(6);
	st.push(7);
	st.push(8);
	cout << "遍历前st有效元素个数：" << st.size() << endl;
	//使用top和pop接口遍历stack
	cout << "开始遍历st:" << endl;
	while (!st.empty())
	{
		//获取栈顶元素
		cout << st.top() << " ";
		//移除栈顶元素
		st.pop();
	}
	cout << endl;
	cout << "遍历后st有效元素个数：" << st.size() << endl;
 }

void Test_swap()
{
	vector<int> v1{ 1,3,5,7 };
	stack<int, vector<int>> st1(v1);
	vector<int> v2{ 2,4,6,8,10,12 };
	stack<int, vector<int>> st2(v2);
	//交换前
	cout << "swap前st1的size()为：" << st1.size() << endl;
	while (!st1.empty())
	{
		cout << st1.top() << " ";
		st1.pop();
	}
	cout << endl;
	st1.swap(st2);
	//交换后
	cout << "swap后st1的size()为：" << st1.size() << endl;
	while (!st1.empty())
	{
		cout << st1.top() << " ";
		st1.pop();
	}
	cout << endl;
}

#include<iostream>
#include<vector>
using namespace std;
namespace _Zwy
{
	template <class T,class Container=vector<T>>
  class Stack
  {
  public:
	  void push(const T& x)
	  {
		  _con.push_back(x);
	  }
	  void pop()
	  {
		  _con.pop_back();
	  }
	size_t size()
	  {
		return _con.size();
	  }
	const T& top()const
	{
		return _con.back();
	}
	bool empty()
	{
		return _con.empty();
	}
  private:
	  Container _con;
  };
}

void TestConstructor()
{
	//默认构造函数
	queue<int> qi;
	queue<string> qs;
	queue<vector<int>> qv;
	queue<char> qc;
}

void TestConstructor()
{
	//使用底层容器初始化的构造函数
	list<int> Mylist{ 1,3,5,7,9 };
	//使用Mylist作为q1的底层容器
	queue<int, list<int>> q1(Mylist);

	//使用Myvector作为q2的底层容器
	vector<char> Myvector{ 'a','c','e','g' };
	queue<char, vector<char>> q2(Myvector);
}

void TestConstructor()
{
	//拷贝构造函数
	list<int> Mylist{ 1,3,5,7,9 };
	//使用Mylist构造 q1
	queue<int, list<int>> q1(Mylist);
	
	//使用q1拷贝构造q2
	queue<int, list<int>> q2(q1);
}

void Testempty()
{
	//构造非空的queue
	list<int> l{ 1,3,5,7,9 };
	queue<int, list<int>> q1(l);
	if (!q1.empty())
		cout << "q1不为空" << endl;
	else
		cout << "q1为空" << endl;

	//构造空的queue
	queue<int> q2;
	if (!q2.empty())
		cout << "q2不为空" << endl;
	else
		cout << "q2为空" << endl;
}

void Testsize()
{
	list<int> l{ 1,3,5,7,9 ,11};
	queue<int, list<int>> q1(l);
	cout << "q1的有效数据个数size()：" << q1.size() << endl;

	queue<int> q2;
	cout << "q2的有效数据个数size()：" << q2.size() << endl;
}

void Test_push_pop()
{
	//使用list作为底层容器构造queue
	list<int> l{ 1,2,3,4,5};
	queue<int, list<int>> q(l);
	//push元素 入队列
	q.push(6);
	q.push(7);
	cout << "当前队列size为:" << q.size() << endl;
	//遍历队列
	cout << "开始遍历队列:" << endl;
	while (!q.empty())
	{
		//获取队头元素并删除
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl<< "当前队列size为:" << q.size() << endl;
}

void Test_front_back()
{
	//使用list作为底层容器构造queue
	list<int> l{ 1,2,3,4,5};
	queue<int, list<int>> q(l);
	cout << "初始队头元素front为：" << q.front() << endl;
	cout << "初始队尾元素back为：" << q.back() << endl;
	//push元素 入队列
	q.push(6);
	//pop 队头元素出队列
	q.pop();
	cout << "当前队头元素front为：" << q.front() << endl;
	cout << "当前队尾元素back为：" << q.back() << endl;
}

void Test_swap()
{
	list<int> l1{ 10,9,8,7,6 };
	queue<int, list<int>> q1(l1);
	list<int> l2{ -1,0,1,2,3,4,5 };
	queue<int, list<int>> q2(l2);
	//交换前
	cout << "swap前q1的size()为：" << q1.size() << endl;
	while (!q1.empty())
	{
		cout << q1.front() << " ";
		q1.pop();
	}
	cout << endl;
	q1.swap(q2);
	//交换后
	cout << "swap后q1的size()为：" << q1.size() << endl;
	while (!q1.empty())
	{
		cout << q1.front() << " ";
		q1.pop();
	}
	cout << endl;
}

namespace _Zwy
{
	template <class T, class Container = list<T>>
	class Queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_front();
		}
		size_t size()
		{
			return _con.size();
		}
		const T& front()const
		{
			return _con.front();
		}

		const T& back()const
		{
			return _con.back();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

class MinStack
{
public:
	void push(int x)
	{
		// 只要是压栈，先将元素保存到_elem中
		_elem.push(x);
		// 如果x小于_min中栈顶的元素，将x再压入_min中
		if (_min.empty() || x <= _min.top())
			_min.push(x);
	}
	void pop()
	{
		// 如果_min栈顶的元素等于出栈的元素，_min顶的元素要移除
		if (_min.top() == _elem.top())
			_min.pop(); _elem.pop();
	}
	int top() { return _elem.top(); }
	int getMin() { return _min.top(); }
private:
	// 保存栈中的元素
	std::stack<int> _elem;
	// 保存栈的最小值
	std::stack<int> _min;
};

class Solution {
public:
	bool IsPopOrder(vector<int> pushV, vector<int> popV) {
		//入栈和出栈的元素个数必须相同
		if (pushV.size() != popV.size())
			return false;
		// 用s来模拟入栈与出栈的过程
		int outIdx = 0;
		int inIdx = 0;
		stack<int> s;
		while (outIdx < popV.size())
		{
			// 如果s是空，或者栈顶元素与出栈的元素不相等，就入栈
			while (s.empty() || s.top() != popV[outIdx])
			{
				if (inIdx < pushV.size())
					s.push(pushV[inIdx++]);
				else
					return false;
			}
			// 栈顶元素与出栈的元素相等，出栈
			s.pop();
			outIdx++;
		}
		return true;
	}
};

class Solution 
{
public:
	int evalRPN(vector<string>& tokens) {
		stack<int> s;
		for (size_t i = 0; i < tokens.size(); ++i) 
		{
			string& str = tokens[i];
			// str为数字
			if (!("+" == str || "-" == str || "*" == str || "/" == str))
			{
				s.push(atoi(str.c_str()));
			}
			else
			{
				// str为操作符
				int right = s.top();
				s.pop();
				int left = s.top();
				s.pop();
				switch (str[0])
				{
				case '+':
					s.push(left + right);
					break;
				case '-':
					s.push(left - right);
					break;
				case '*':
					s.push(left * right);
					break;
				case '/':
					// 题目说明了不存在除数为0的情况
					s.push(left / right);
					break;
				}
			}
		}
		return s.top();
	}
};

#include<deque>
namespace _Zwy
{
	template<class T, class Con = deque<T>>
	//template<class T, class Con = vector<T>>
	//template<class T, class Con = list<T>>
	class stack
	{
	public:
		stack() 
		{}
		void push(const T& x) 
		{
			_deq.push_back(x);
		}
		void pop()
		{
			_deq.pop_back();
		}
		T& top() 
		{ 
			return _deq.back();
		}
		const T& top()const 
		{ 
			return _deq.back(); 
		}
		size_t size()const 
		{ 
			return _deq.size();
		}
		bool empty()const 
		{ 
			return _deq.empty(); 
		}
	private:
		Con _deq;
	};
}

#include<deque>
namespace _Zwy
{
	template<class T, class Con = deque<T>>
	//template<class T, class Con = list<T>>
	class queue
	{
	public:
		queue() 
		{}
		void push(const T& x) 
		{ 
			_deq.push_back(x); 
		}
		void pop() 
		{ 
			_deq.pop_front();
		}
		T& back()
		{ 
			return _deq.back();
		}
		const T& back()const 
		{ 
			return _deq.back();
		}
		T& front() 
		{
			return _deq.front();
		}
		const T& front()const 
		{ 
			return _deq.front();
		}
		size_t size()const 
		{
			return _deq.size();
		}
		bool empty()const
		{ 
			return _deq.empty(); 
		}
	private:
		Con _deq;
	};
}