實現(xiàn)一個泛型的雙端隊列和隨機化隊列塘雳，用數(shù)組和鏈表的方式實現(xiàn)基本數(shù)據(jù)結(jié)構录煤，主要介紹了泛型和迭代器壳澳。
Dequeue. 實現(xiàn)一個雙端隊列罩息，它是棧和隊列的升級版嗤详，支持首尾兩端的插入和刪除。Deque的API如下
deque的操作實現(xiàn)必須是常數(shù)時間瓷炮，使用空間是當前元素個數(shù)葱色，迭代器的實現(xiàn)next()和hasNext()操作也是常數(shù)時間和常數(shù)空間,所以Deque采用Linked-list實現(xiàn)方式.
private class Node {
private Item item;
private Node prev;
private Node next;
}
雙端隊列使用Linked-List實現(xiàn)，那么使用一個哨兵sentinel來輔助實現(xiàn)Deque娘香，這在Programming Tricks and Common Pitfalls中有講到苍狰，每個Assignment中checklist的內(nèi)容對于理解和實現(xiàn)有很大幫助。
使用哨兵指向deque的隊首元素烘绽，而隊尾元素指向哨兵淋昭，現(xiàn)在我們來分析每個方法實現(xiàn)。
Deque(): 初始Deque沒有元素安接，元素個數(shù)為0翔忽，那么哨兵的prev和next也都指向自身。
addFirst(): 隊首添加元素時候，就是簡單的鏈表操作在sentinel和第一個Node之間插入一個新的Node歇式，并記得把元素個數(shù)加1.
addLast(): 同理
removeFirst(): 首先要判斷驶悟，deque是否為空，能否支持刪除操作材失，可以的話痕鳍，刪除首元素，更新第二個元素和sentinel之間的關系龙巨，然后元素個數(shù)減1
removeLast(): 同理
isEmpty()和size(): 用一直維護元素個數(shù)變量來進行操作
迭代器Iterator的操作也十分簡單了, 我們只需要獲取sentinel哨兵笼呆，然后遍歷就可以實現(xiàn)。hasNext()直到下一個元素又走回了sentinel哨兵旨别，那么我們就已經(jīng)遍歷完了所有元素诗赌。
Randomized queue. 隨機化隊列也和棧和隊列十分相似，區(qū)別在于它的remove操作是隨機刪除隊列中的一個元素昼榛。API如下:
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() // delete and return a random item
public Item sample() // return (but do not delete) a random item
public Iterator<Item> iterator() // return an independent iterator over items in random order
public static void main(String[] args) // unit testing
}
Randomized queue和一般的queue基本操作都是一樣境肾，由于隨機出隊，那入隊元素也不一定按照正常的隊列來使用胆屿，我們只需要把隊列的元素維護在連續(xù)起始開始的一段就可以了奥喻。
那么我們只需要使用一個tail尾指針，當插入元素的時候非迹，把元素直接插入在隊尾:
public void enqueue(Item item) {
if (item == null)
throw new java.lang.NullPointerException("can't add a null item");
if (N == q.length) resize(2*q.length);
q[tail++] = item;
N++;
}
public Item dequeue() {
if (isEmpty())
throw new java.util.NoSuchElementException("underflow");
int index = StdRandom.uniform(N);
Item item = q[index];
//because random, just simply put q[tail-1] to q[index]
q[index] = q[--tail];
q[tail] = null;
N--;
if (N > 0 && N == q.length/4) resize(q.length/2);
return item;
}
迭代器的操作环鲤，不能需改原來的元素，需要重新申請空間憎兽，隨機化的出隊思考起來也很簡單冷离，我們使用Elementary Sort中介紹的Shuffle的方法來對元素重新組合一下
for (int i = 0; i < N; i++) {
int r = StdRandom.uniform(i+1);
Item tmp = array[i];
array[i] = array[r];
array[r] = tmp;
}
