Question

栈是一个非常常见的数据结构，它在计算机领域中被广泛应用，比如操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址及临时变量等。栈的特点是后进先出，即最后被压入（push）栈的元素会第一个被弹出（pop）。在面试题22栈的压入、弹出序列中，我们再详细分析进栈和出栈序列的特点。

通常栈是一个不考虑排序的数据结构，我们需要O（n）时间才能找到栈中最大或者最小的元素。如果想要在O（1）时间内得到栈的最大或者最小值，我们需要对栈做特殊的设计，详见面试题21包含min函数的栈。

队列是另外一种很重要的数据结构。和栈不同的是，队列的特点是先进先出，即第一个进入队列的元素将会第一个出来。在2.3.4节介绍的树的宽度优先遍历算法中，我们在遍历某一层树的结点时，把结点的子结点放到一个队列里，以备下一层结点的遍历。详细的代码参见面试题23从上到下遍历二叉树。

栈和队列虽然是特点针锋相对的两个数据结构，但有意思的是它们却相互联系。请看面试题7用两个栈实现队列，同时读者也可以考虑如何用两个队列实现栈。