stack/queue的简单介绍及使用

【写在前面】

虽然 cplusplus 把 stack 和 queue 归类到了 Containers 下，但是严格来说 stack and queue 不再是容器了，而属于容器适配器 or 容器配接器，适配器做的功能是转换 —— 它不是直接实现的，而是由其它容器封装转换实现的，在下面的模拟实现我们会细谈。
它做为容器适配器，它与容器有一个具大的差别之一就是它没有迭代器，不是说它不能实现迭代器，而是没有必要实现迭代器，因为它如果实现了迭代器，就没法保障 stack “Last In First Out” 和 queue “First In First Out” 的原则。
其次对于 stack 和 queue 的使用比较简单，我们大概过一下，以 OJ 的形式来了解它们。

一、stack的介绍及使用

💦 stack的介绍

stack文档介绍

1. stack 是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2. stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层，元素特定容器的尾部(即栈顶)被压入和弹出。
3. stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
   ➡ empty：判空操作
   ➡ back：获取尾部元素操作
   ➡ push_back：尾部插入元素操作
   ➡ pop_back：尾部删除元素操作
4. 标准容器 vector、deque、list 均符合这些需求，默认情况下，如果没有为 stack 指定特定的底层容器，默认情况下使用 deque。
   

💦 stack的使用

#include<iostream>
#include<stack>
using namespace std;
void test_stack()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
		
	while(!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl;
}
int main()
{
	test_stack();
	return 0;
}

💦 stack的模拟实现

vector 模拟实现 stack。

#include<vector>
namespace bit
{
	template<class T>
	class stack
	{
	public:
		stack(){}
		//先进
		void push(const	T& x){_ve.push_back(x);}
		//后出
		void pop(){_ve.pop_back();}
		const T& top(){return _ve.back();}
		size_t size(){return _ve.size();}
		bool empty(){return _ve.empty();}
	private:
		std::vector<T> _ve;
	};
}

二、queue的介绍及使用

💦 queue的介绍

queue文档介绍

1. 队列是一种容器适配器，专门用于在 FIFO 上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。

2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
   ➡ empty：检测队列是否为空
   ➡ size：返回队列中有效元素的个数
   ➡ front：返回队头元素的引用
   ➡ back：返回队尾元素的引用
   ➡ push_back：在队列尾部入队列
   ➡ pop_front：在队列头部出队列

4. 标准容器类 deque 和 list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器类，则使用标准容器 deque。
   

💦 queue的使用

#include<iostream>
#include<queue>
using namespace std;
void test_queue()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
		
	while(!q.empty())
	{
		//queue与stack相同的是入数据都是push,但出数据stack是top,queue是front
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;
}
int main()
{
	test_queue();
	return 0;
}

💦 queue的模拟实现

list 模拟实现 queue。

#include<list>

namespace bit
{
	template class<T>
	class queue
	{
	public:
		queue(){}
		//先进
		void push(const T& x){_qu.push_back(x);}
		//先出
		void pop(){_qu.pop_front();}
		const T& front(){return _qu.front();}
		size_t size(){return _qu.size();}
		bool empty(){return _qu.empty();}  
	private:	
		std::list<T> _qu;
	};
}