此前了解的栈与队列和堆
python中的大小堆 heapq - PiaYie - 博客园 (cnblogs.com)
队列 - PiaYie - 博客园 (cnblogs.com)
树的遍历 - PiaYie - 博客园 (cnblogs.com)
队列是先进先出，栈是先进后出，堆是满足特定结构
此外队列还有双端队列
栈和队列是STL（C++标准库）里面的两个数据结构，C++标准库有很多版本，要知道自己使用标准是啥，和堆栈的底层实现
关于栈
Stack in C++ STL - GeeksforGeeks
栈是C++标准库中的一种数据结构，栈是一种后进先出(LIFO，last in first out)类型的容器适配器，即在一端(顶部)添加一个新元素，然后从(顶部)删除一个元素。Stack使用封装的vector或deque(默认情况下)或list(顺序容器类)对象作为其底层容器，提供一组特定的成员函数来访问其元素。
堆栈的语法:为了创建堆栈，我们必须在代码中包含<stack>头文件。
The functions associated with stack are:
empty() – Returns whether the stack is empty – Time Complexity : O(1)
size() – Returns the size of the stack – Time Complexity : O(1)
top() – Returns a reference to the top most element of the stack – Time Complexity : O(1)
push(g) – Adds the element ‘g’ at the top of the stack – Time Complexity : O(1)
pop() – Deletes the top most element of the stack – Time Complexity : O(1)
栈四个问题
C++中stack 是容器么？
是一种数据结构，STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）
我们使用的stack是属于那个版本的STL？
SGI-STL
我们使用的STL中stack是如何实现的？
SGI STL栈的底层实现是用双端队列deque实现的。
P.s 栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）,默认是deque
- 我们也可以指定vector为栈的底层实现，初始化语句如下：
std::stack<int, std::vector<int> > third; // 使用vector为底层容器的栈
- 队列也可以指定list 为其底层实现，初始化queue的语句如下：
std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列
stack 提供迭代器来遍历stack空间么？
不提供，只有特定的方法 top push pop empty等等
关于队列
Queue in C++ Standard Template Library (STL) - GeeksforGeeks
队列是一种采用先进先出(FIFO, first in first out)方式操作的容器适配器。元素被插入到后面(末端)，并从前面删除。队列使用封装的deque或list(顺序容器类)对象作为其底层容器，提供一组特定的成员函数来访问其元素。
队列四个问题
C++中queue是容器么？
是容器适配器
我们使用的queue是属于那个版本的STL？
SGI-STL
我们使用的STL中queue是如何实现的？
默认是双端队列deque
queue 提供迭代器来遍历queue空间么？
不提供，只有一些方法，Methods of Queue are:
| Method | Definition |
|---|---|
| queue::empty() | Returns whether the queue is empty. |
| queue::size() | Returns the size of the queue. |
| queue::swap() | Exchange the contents of two queues but the queues must be of the same type, although sizes may differ. |
| queue::emplace() | Insert a new element into the queue container, the new element is added to the end of the queue. |
| queue::front() | Returns a reference to the first element of the queue. |
| queue::back() | Returns a reference to the last element of the queue. |
| queue::push(g) | Adds the element ‘g’ at the end of the queue. |
| queue::pop() | Deletes the first element of the queue. |
用栈实现队列
用队列实现栈