3-Stacks And Queues

可变长数组 Resizing arrays

为了实现变长数组，同时尽可能降低增删元素的时间复杂度，我们需要对数组的大小做动态的调整。以Stack实现中的push 和 pop 方法为例：

Push

  • 如果数组元素已满，那么我们创建一个长度为原来数组长两倍的数组，并把所有的值都复制进去

  • 复杂度：插入N个元素需要 $N+(2+4+8+\cdots +N) = 3N-2$ 次数组访问操作

  • 这里我们用到了均摊分析：

    • 尽管插入某些元素时需要花费较长的时间，但是我们将这些操作平均到每一个元素上，便能够得到一个用来描述整个算法复杂度的平均值。

image.png

Pop

  • 若数组半满便缩减数组大小，则容易出现抖动现象，每次操作花费时间正比于N

    • image.png
  1. 当数组四分之一满时再减半数组大小。这样能够确保数组处于25%满与100%满之间，同时避免抖动现象

栈实现中可变长数组与链表的比较

链表

  • 每个操作最坏情况下也只需要常数时间
  • 但是需要使用额外的时间和空间来处理元素之间的连接

可变长数组

  • 每次操作平均花费常数时间
  • 使用的空间更少
  • 如果不希望出现某些花费较长时间的操作，而是希望保证不同操作花费时间平均，则更好的选择是链表

Java 中的泛型 Generics

  • Java中不支持泛型数组的创建，需要先创建Object类数组再进行类型转换。

  • （PS. 老爷子吐槽这实在是太丑陋了，而且这么写Java 还要警告你类型转换未经检查！这不都是被你逼的嘛！）

  • image.png

Java 迭代器 Iterators

迭代器的存在让使用者不需要关心某种数据结构具体的实现也能够遍历所有的元素。

  • foreach 语法就是使用的迭代器
  • image.png
  • 注意，java.util.stack 的 Iterator 遍历的顺序是 FIFO

Bag API

image.png

  • 例如：去掉pop的栈或者去掉dequene的队列

栈和队列的实际应用

函数调用

递归调用函数可以用显式地维护一个栈来代替。

image.png

表达式求值 Dijkstra's two-stack algorithm

求值中缀表达式的方法：

  • 对于数值，入栈数值栈

  • 对于操作符，入栈操作符栈

  • 对于左括号：忽略

  • 对于右括号：出栈数值栈的两个值，出栈操作符进行运算后将结果入栈数值栈

  • 为什么是正确的：不难理解

    • image.png

逆波兰表达式

将所有的括号去掉，操作符放在两个数值后面，便得到了逆波兰表达式。

image.png

Q.E.D.