【C++】stack和queue

一、stack的介绍和使用

1.stack的介绍

栈：后进先出的原则

2.stack的使用

二、queue的介绍和使用

1.queue的介绍

1. 队列是一种容器适配器，专门用于在FIFO(先进先出)上下文中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
   empty：检测队列是否为空
   size：返回队列中有效元素的个数
   front：返回队头元素的引用
   back：返回队尾元素的引用
   push_back：在队列尾部入队列
   pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque

队列：先进先出的原则

2.queue的使用

三、容器适配器

上面在介绍stack和queue的时候都有提到容器适配器，那什么又是容器适配器呢？有什么作用？

四、stack和queue的实现

讲他们的实现之前我们先来看一下STL库中他们是如何定义的

1.stack

stack的接口的主要共功能有push数据，pop数据，判空，数据个数，取栈顶元素这几个功能，所以匹配我们的容器适配器只要有尾插数据，尾删数据，获取尾部数据，判空就OK了，下面我们来实现一波

template<class T ,class Container=deque<T>>
//这里的容器适配器换成别的也行，只要这个容器有push_back(),pop_back()……等等这些功能都可以
//stack的实现主要就是依靠容器适配器来帮他完成他想要的功能
class stack
{
public:
	void push(const T& val)
	{
		_con.push_back(val);
	}
	void pop()
	{
		_con.pop_back();
	}
	T& top()
	{
		return _con.back();
	}
	size_t size()
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
private:
	Container _con;
};

我们在调用这个容器适配器stack的时候，不传参默认调用stack,他底层是deque，如果你想换成vector或者list，可以给他传参，stack<int,vector>类似这样

2.queue

queue也是一个容器适配器，他实现起来和stack简直不要太像，那我们就直接开干

template <class T,class Container=deque<T>>
class queue
{
public:
	void push(const T& val)
	{
		_con.push_back(val);
	}
	void pop()
	{
		_con.pop_front();
	}
	T& front()
	{
		return _con.front();
	}
	T& back()
	{
		return _con.back();
	}
	bool empty()
	{
		return _con.empty();
	}
	size_t size()
	{
		return _con.size();
	}
private:
	Container _con;
};

细心的朋友肯定会发现，我这两个类都没有写构造函数，因为我们这里使用的是容器适配器来完成的，不写构造函数编译器会自动生成一个默认构造，这个容器适配器是一个自定义类，默认构造会调用自定义类的构造来初始化我们的容器

stack和queue暂且就到这里，我们下篇接着聊✋