堆栈和队列：双端队列与随机队列

此次作业[^1]是为了用数列和链表实现基本数据结构，并介绍泛型（generics）和迭代（iterators）

1 双端队列（Dequeue）

双端队列（double-ended queue or deque）支持从数据结构的前端或尾端添加或删除数据。

1.1 数据结构（Data type）

public class Deque<Item> implements Iterable<Item> {
   public Deque()                           // 构造一个空的双端队列 deque
   public boolean isEmpty()                 // 判断 deque 是否为空
   public int size()                        // 返回 deque 中有多少 item
   public void addFirst(Item item)          // add the item to the front
   public void addLast(Item item)           // add the item to the end
   public Item removeFirst()                // remove and return the item from the front
   public Item removeLast()                 // remove and return the item from the end
   public Iterator<Item> iterator()         // return an iterator over items in order from front to end
   public static void main(String[] args)   // unit testing
}

1.2 极端案例（Corner cases）

当添加的 item 为 null 时，抛出异常 java.lang.NullPointerException
如果从一个空的 deque 中删除一个 item，抛出异常 java.util.NoSuchElementException
如果在一个迭代器（iterator）中调用 remove()，抛出异常 java.lang.UnsupportedOperationException
如果在一个迭代器（iterator）中调用 next() 方法，但是没有下一个 item 可以返回，抛出异常 java.util.NoSuchElementException

1.3 性能要求（Performance requirements）

deque 的每个操作的最坏时间复杂度为常数（即 O(1) 步）
一个有 n 个 item 的 deque 最多占用 48n + 192 字节内存，并且占用空间正比于当前 deque 的 item 数量
迭代器必须支持每个操作（包括 construction）的最坏时间复杂度都是常数

2 随机队列（Randomized queue）

随机队列与 stack 和 queue 类似，除了删除时是从此时队列所有元素中随机选一个 item 删除并输出

2.1 数据结构（Data type）

public class RandomizedQueue<Item> implements Iterable<Item> {
   public RandomizedQueue()                 // construct an empty randomized queue
   public boolean isEmpty()                 // is the queue empty?
   public int size()                        // return the number of items on the queue
   public void enqueue(Item item)           // add the item
   public Item dequeue()                    // remove and return a random item
   public Item sample()                     // return (but do not remove) a random item
   public Iterator<Item> iterator()         // return an independent iterator over items in random order
   public static void main(String[] args)   // unit testing
}

2.2 极端案例（Corner cases）

一个随机队列的多个迭代器必须是相互独立的；每个迭代器必须维护自己的随机顺序
当添加的 item 为 null 时，抛出异常 java.lang.NullPointerException
如果从一个空的随机队列中 sample 或者 dequeue 一个 item，抛出异常 java.util.NoSuchElementException
如果在一个迭代器（iterator）中调用 remove()，抛出异常 java.lang.UnsupportedOperationException
如果在一个迭代器（iterator）中调用 next() 方法，但是没有下一个 item 可以返回，抛出异常 java.util.NoSuchElementException

2.3 性能要求（Performance requirements）

随机队列的每个操作（除了创建和迭代器）的平摊时间复杂度为常数
即，m 个随机队列的操作（从空队列开始），最坏情况下执行 cm 步（c 为常数）（即 O(m) 步）
一个有 n 个 item 的 deque 最多占用 48n + 192 字节内存，并且占用空间正比于当前 deque 的 item 数量
迭代器必须支持 next() 和 hasNext() 的最坏时间复杂度都是常数；construction 的时间复杂度为线性。每个迭代器需要使用线性大小的额外内存

3 Permutation client

写一个有 1 个命令行参数 k 的名为 Permutation.java 的 client program

1
2
3

public class Permutation {
   public static void main(String[] args)
}

用 StdIn.readString() 从标准输入读取字符串，并且随机打印出其中 k 个。每个 item 最多被打印一次。你可以假设 0 ≤ k ≤ n（n 为从标准输入读取的字符串数）

% more distinct.txt                        % more duplicates.txt
A B C D E F G H I                          AA BB BB BB BB BB CC CC

% java Permutation 3 < distinct.txt       % java Permutation 8 < duplicates.txt
C                                          BB
G                                          AA
A                                          BB
                                           CC
% java Permutation 3 < distinct.txt        BB
E                                          BB
F                                          CC
G                                          BB

Permutation 的运行时间和输入的大小成线性关系
你可能只用常数大小的内存加上一个最大为 n 的 Deque 或者 RandomizedQueue 对象（作为挑战，可以尝试只用一个最大为 k 的 Deque 或者 RandomizedQueue 对象）

4 解决方案（Solutions）

4.1 双端队列

题目要求 deque 的每个操作的最坏时间复杂度为 O(1)，考虑到可变数组有时需要调整数组大小，其时间复杂度并不是 0(1)，因此我采用了链表
删除链尾的结点时，我们需要找出指向 last 的结点，因此我采用了双向链表

4.2 随机队列

随机队列要求平摊时间复杂度为常数，因此我采用了可变数组

4.2.1 dequeue()

对于随机删除结点，我们有以下几种解决方案：

方案 1：
在队列（实际上是包含一些 null 元素的数组）中随机选出一个元素，如果该元素不是 null，则输出并删除该元素；如果该元素是 null，则重复以上过程
在重置数组长度（resizing）时，（顺手）删掉所有为 null 的元素
考虑到重置数组长度，null 的数量不会太多，至多是$\frac{3}{4}N$。可以通过所有测试
方案 2：
在删除结点之前，先用洗牌算法将队列洗牌，然后再删除。其中洗牌算法有以下几种：
- 费舍尔-耶茨洗牌算法（Fisher–Yates shuffle）：为数组中的每一项分配一个不重复的随机数，然后根据随机数大小排序
- 高德纳洗牌算法（Knuth shuffle）：对于第 i 项，随机产生一个 0 到 i 之间的随机数 r，交换 a[i] 和 a[r]
  1
  2
  3
  4
  for(i=0; i < a.length; i++){
  r = random(0, i);
  swap(a[i], a[r]);
  }
方案 3：
在 enqueue() 的时候，使用 **inside-out 算法**，在添加第 i 项时，随机产生一个 0 到 i 之间的随机数 r，如果 i ≠ r，交换 a[i] 和 a[r]
方案 4：
在 dequeue() 的时候，每次从 [0, numElements) 中随机取出一个 index，然后返回值就是这个 index 位置的元素，再把最后一个元素转移到这个 index 位置，numElements 减 1 返回即可

4.2.2 迭代器

对于迭代器，需要注意的是不同迭代器输出的顺序应该是互相独立的。有一种做法是，对于每个迭代器，建立一个数组保存对队列中元素的引用，然后用 StdRandom.shuffle() 对该数组进行随机打乱

4.3 Permutation

如果不想拿附加分，直接把 N 个字符串丢进一个 RandomizedQueue 对象里面，然后再弹出 k 个字符串，直接输出就好了，很简单。
如果要拿附加分，我们就需要将随机队列中的元素个数保持在 k 个以内。然而，我们会遇到一个障碍：N 是未知的，不然直接对每个字符串以 k/N 的概率留下或丢掉好了。
我们使用**水塘抽样算法（Reservoir sampling）**：

水塘抽样是一种随机算法，其目的在于从包含 n 个项目的集合 S 中选取 k 个样本，其中 n 为一很大或未知的数量，尤其适用于不能把所有 n 个项目都存放到主内存的情况。

从 S 中抽取首 k 项放入水塘中
对于每个 S[j] 项（j ≥ k）：
    随机产生一个范围从 0 到 j 的整数 r
    若 r < k 则把水塘中的第 r 项换成 S[j] 项

简略的证明过程：
设为 $P_n$ 每个字符串最后被输出的概率，共有 N 个字符串，需输出 k 个

当 n ≤ k，

$$P_n = \prod_{i=k+1}^N (1-\frac{1}{k} \cdot \frac{k}{i}) = \frac{k}{N}$$

当 n > k，

$$ P_n = \frac{k}{n} \cdot \prod_{i=n+1}^N (1-\frac{1}{k} \cdot \frac{k}{i}) = \frac{k}{N}$$

5 代码

见 GitHub 的 repo：PrincetonAlgs4

Deque.java
RandomizedQueue.java
Permutation.java

6 分析运行时间和占用内存（Analysis of running time and memory usage）

见分析报告

[^1]: 原文见 http://coursera.cs.princeton.edu/algs4/assignments/queues.html
也可以从网站 http://introcs.cs.princeton.edu/java/assignments/ 找到