【STL】stack与queue的底层原理及其实现

stack的介绍

（图片来自知乎）

1.stack是一种容器适配器，模拟了栈的数据结构。数据只能从一端进去，另一端出来（先进后出）。
2.stack适配器默认是由deque容器实现的，也可以显示要求stack的底层封装的容器类型。由于栈的特性，array和forward_list不能用来构造stack适配器。
3.stack的底层容器必须需要支持以下几个操作：
(1) empty：判空操作
(2)back：获取尾部元素操作
(3)push_back：尾部插入元素操作
(4)pop_back：尾部删除元素操作
这也意味着，即使底层封装的容器可能不一样，但我们能以统一的视角去看待以及操作stack。

对栈这种数据结构不了解的同学可以去看：
C语言模拟栈和队列

库中stack的使用

通过查看手册我们能看到stack有以下成员函数：

在c++98中，stack并没有显示设计自己的构造函数。作为适配器，使用编译器默认的构造函数即可，因为默认的构造函数会调用自定义类型成员的构造。析构也是如此。

empty()

stack是否为空取决于，底层封装容器对象是否为空。stack的empty()实际上是在调用底层容器的empty()。这一点在stack的其它成员函数也类似。
给出stack的常用函数功能：

栈的模拟实现

尝试用vector作为底层容器来模拟栈。

#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>


template<class T,class Container = std::vector<T> >
class stack {
public:
	//默认构造函数会自动调用自定义类型成员变量的构造函数
	//默认析构函数会自动调用自定义类型成员变量的析构函数
	size_t size() {
		return _con.size();
	}
	bool empty() {
		return _con.empty();
	}
	void push(const T& val) {
		_con.push_back(val);
	}
	T top() {
		return _con[_con.size() - 1];
	}
	void pop() {
		_con.pop_back();
	}

	void swap(stack<T>& x) {
		_con.swap(x._con);
	}

private:
	Container _con;
};

我们可以发现，这种用一种现成的容器去实现另一种容器的方式是非常方便且灵活的！帮我们节省了非常多的代码。这同样也是容器适配器的作用之一！

queue的介绍

（来自百度）

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

库中queue的使用

queue的模拟实现

#include<deque>

template<class T, class Container = std::deque<T> >
class queue {
public:
	//默认构造函数会自动调用成员变量的构造函数
	//默认析构函数会自动调用成员变量的析构函数
	size_t size() {
		return _con.size();
	}
	bool empty() {
		return _con.empty();
	}
	void push(const T& val) {
		_con.push_back(val);
	}
	T front() {
		return _con.front();
	}
	T back() {
		return _con.back();
	}
	void pop() {
		_con.pop_front();
	}

	void swap(stack<T>& x) {
		_con.swap(x._con);
	}

private:
	Container _con;
};