双端队列 Deque 与 随机化队列 RandomizedQueue 的实现

双端队列，也就是栈和队列的结合，同时可以从头和尾进行进出栈 / 队列的功能，看一下他的数据结构就懂了：

public class Deque<Item> implements Iterable<Item> {
   public Deque()                           // construct an empty deque
   public boolean isEmpty()                 // is the deque empty?
   public int size()                        // return the number of items on the deque
   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 (optional)
}

双端队列的实现还是比较简单的（虽然实际上还会是踩了一些微小的坑）。

首先，回忆一下链表和队列的数据结构，有以下几种实现：

1. 链表实现
2. 数组实现

链表实现和数组实现的各操作时间复杂度不用赘述，链表对于收尾操作非常轻松，对于随机访问却比较复杂，而数组访问起来简单。

对于这样一个双端队列，我们不需要考虑随机访问的操作，所以选择链表去实现明显是更为合适的。

Deque 的代码地址

之后的 RandomizedQueue 坑比较多一点：

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 (optional)
}

首先我们要考虑到他需要随机删除队列中的一个数，那么删除时肯定会访问到数列中的随机一个数，因此用数组的实现更好。

在这里，我们假定是随机选择出队，所以入队操作是同样顺序的。在出队上，最初我想着 Random 第 n 个元素出队，结果遇到的麻烦是复杂度不是常数时间，而是线性的，所以我们换了一个方法，将 random 到的元素与最后一个元素交换，这样为空的就永远是最后的元素了，不需要使用循环来探测元素。

在迭代器的构件上，为了保证每个迭代器的元素都不同，我们使用了 shuffle 函数来保证独立的乱序，这样在遍历时只要顺序遍历下去就行了。

RandomizedQueue 的代码