数据结构之栈与队列

# 1 栈与队列

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

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

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

  • 设置一个插入栈 A(先进后出),一个弹出栈 B(先进后出);

  • 若要插入元素,直接插入到队列 A 中;

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

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

  • 设置两个空队列;

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

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