数据结构之栈与队列

# 1 栈与队列

栈是一个非常常见的数据结构，其特点是先进后出，操作系统在函数调用便会使用栈结构。

栈是一个不考虑排序的数据结构，因此查找最大最小元素的时间复杂度为 O(n)，若想要在 O(1) 时间内得到栈的最大最小值，则需要对栈做特殊的设计。

与栈不同的是，队列是先进先出，虽然这两个数据结构看起来针锋相对，但其实他们两个可以相互实现，可以用两个栈实现队列：

• 设置一个插入栈 A（先进后出），一个弹出栈 B（先进后出）；

• 若要插入元素，直接插入到队列 A 中；

• 若要弹出元素，（1）若弹出栈 B 中有元素，则弹出栈顶元素；（2）若弹出栈 B 为空，则将插入栈 A 中的元素依次插入 B 中，此时，若 B 不为空则弹出栈顶元素，否则抛出异常。

也可以用两个队列实现栈：

• 设置两个空队列；

• 若要插入元素，选择非空队列插入元素，若两个都是空队列则随机选一个；

• 若要弹出元素，将非空队列的元素（除最后一个元素外）依次插入到空队列中，然后将最后一个元素弹出。