https://github.com/hym105289/Deques-and-Randomized-Queues

1.雙端隊列

操作要求：實現(xiàn)一個雙端隊列，可以在隊頭插入，也可以在隊尾插入，可以在隊頭刪除，也可以在隊尾刪除。
時間要求：每次插入或刪除的時間復雜度為常量。
內(nèi)存要求：一個包含n個對象的隊列最多使用48n+192字節(jié)的內(nèi)存。
思路：要實現(xiàn)常量時間內(nèi)的插入和刪除，可以采用雙向鏈表實現(xiàn)
①隊列的變量：長度，first頭結點，last尾結點；
②Node：Item和pre、next雙向結點；
③注意要實現(xiàn)Iterable<Item>接口中的hasNext、next、remove函數(shù)；
④插入要考慮當?shù)谝粋€元素插入的情況:隊頭插入則記得修改隊尾隊尾插入則記得修改隊頭；刪除也要考慮到只有一個元素的情況，隊頭刪除記得修改隊尾，隊尾刪除記得修改隊頭；
⑤因為是雙向鏈表，所以要記得更改與插入和刪除元素相連接的結點，尤其要考慮到只有一個結點時的特殊情況；

import java.util.Iterator;
import java.util.NoSuchElementException;

import edu.princeton.cs.algs4.In;

public class Deque<Item> implements Iterable<Item> {
    private int n;
    private Node first;
    private Node last;

    private class Node {
        private Item item;
        private Node pre;
        private Node next;
    }

    public Deque() {
        n = 0;
        first = null;
        last = null;
    }

    public boolean isEmpty() {
        if (first == null)
            return true;
        else
            return false;
    }

    public int size() {
        return n;
    }

    public void addFirst(Item item) {
        if (item == null) {
            throw new IllegalArgumentException();
        }
        Node temp = new Node();
        temp.item = item;
        temp.next = first;
        temp.pre = null;
        if (first != null) {
            first.pre = temp;
        }
        first = temp;
        n++;
        if (n == 1) {
            last = first;
        }
    }

    public void addLast(Item item) {
        if (item == null) {
            throw new IllegalArgumentException();
        }
        Node temp = new Node();
        temp.item = item;
        temp.pre = last;
        temp.next = null;
        if (last != null) {
            last.next = temp;
        }
        last = temp;
        n++;
        if (n == 1) {
            first = last;
        }

    }

    public Item removeFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Item item = first.item;
        first = first.next;
        if (first != null)
            first.pre = null;
        n--;
        if (n == 0) {
            last = null;
        }
        return item;
    }

    public Item removeLast() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Item item = last.item;
        last = last.pre;
        if (last != null)
            last.next = null;
        n--;
        if (n == 0) {
            first = null;
        }
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new DequeIterator();
    }

    private class DequeIterator implements Iterator<Item> {
        private Node current = first;

        public boolean hasNext() {
            return current != null;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public Item next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

    public static void main(String[] args) {
        String[] test = new In(args[0]).readAllStrings();
        for (String s : test) {
            System.out.println(s);
        }
        System.out.println();
        Deque<String> deque = new Deque<String>();
        for (int i = 0; i < test.length; i++) {
            deque.addLast(test[i]);
        }
        for (String w : deque) {
            System.out.println(w);
        }
        for (int i = 0; i < test.length; i++) {
            test[i] = deque.removeLast();
            System.out.println(test[i]);
        }
    }
}

2.隨機隊列

操作要求：按順序的進行插入元素，但是隨機地刪除隊列中的一個元素，迭代器也要求隨機地訪問所有元素；
性能要求：刪除隊列中的一個元素，均攤為常量時間；
內(nèi)存要求：n個元素的隊列，48n+192字節(jié)內(nèi)存空間；
思路：采用動態(tài)數(shù)組來實現(xiàn)隨機隊列，隨機隊列可以隨機地刪除一個元素，首先產(chǎn)生一個均勻分布的在[0, N)之間的隨機數(shù)，并與N-1交換，然后彈出items[N-1]；其迭代器也要求隨機遍歷元素，實現(xiàn)方式是取出數(shù)組下標構成一個index[]數(shù)組，同樣用StdRandom對index[]進行隨機洗牌，然后按照產(chǎn)生的隨機數(shù)組下標遍歷容器中的元素。

import java.util.Iterator;
import java.util.NoSuchElementException;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;

public class RandomizedQueue<Item> implements Iterable<Item> {
    private int N;
    private Item[] items;

    public RandomizedQueue() {
        N = 0;
        items = (Item[]) new Object[1];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    public void enqueue(Item item) {
        if (N == items.length) {
            resize(2 * items.length);
        }
        if (item == null) {
            throw new IllegalArgumentException();
        }
        items[N++] = item;
    }

    private void resize(int length) {
        Item[] temp = (Item[]) new Object[length];
        for (int i = 0; i < N; i++) {
            temp[i] = items[i];
        }
        items = temp;
    }

    private void randomSwap() {
        if (N <= 1)
            return;
        int random = StdRandom.uniform(N);
        Item temp = items[random];
        items[random] = items[N - 1];
        items[N - 1] = temp;
    }

    public Item dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        randomSwap();
        Item item = items[N - 1];
        items[N - 1] = null;
        N--;
        if (N > 0 && N == items.length / 4)
            resize(items.length / 2);
        return item;
    }

    public Item sample() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        randomSwap();
        return items[N - 1];
    }

    public Iterator<Item> iterator() {
        return new RandomQueueIterator();
    }

    private class RandomQueueIterator implements Iterator<Item> {
        private final int[] index;
        private int current;

        public RandomQueueIterator() {
            index = new int[N];
            for (int i = 0; i < N; i++) {
                index[i] = i;
            }
            for (int i = N - 1; i >= 0; i--) {
                int random = StdRandom.uniform(i + 1);
                int temp = index[random];
                index[random] = index[i];
                index[i] = temp;
            }
            current = N - 1;
        }

        public boolean hasNext() {
            return current >= 0;
        }

        public Item next() {
            if (current < 0) {
                throw new NoSuchElementException();
            }
            return items[index[current--]];
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    public static void main(String[] args) {
        RandomizedQueue<String> rq = new RandomizedQueue<String>();
        String[] test = new In(args[0]).readAllStrings();
        for (int i = 0; i < test.length; i++) {
            rq.enqueue(test[i]);
        }
        for (String s : rq) {
            StdOut.println(s);
        }
        StdOut.println();
        String t = rq.dequeue();
        StdOut.println(t);
    }
}

要注意兩點：
① items = (Item[]) new Object[1];會報警告（是因為[Java]不允許創(chuàng)建泛型數(shù)組（某些歷史和技術原因），所以泛型數(shù)組只能通過強制類型轉換(Item[]) new Object[cap]）實現(xiàn)。因此出現(xiàn)的警告不可避免，忽略即可。
②插入元素前判斷是否需要擴容，刪除元素后判斷是否需要縮減容量；
③尤其注意迭代器的實現(xiàn)，利用了一個額外的index數(shù)組，來實現(xiàn)隨機排列；

3.Permutation

操作要求：輸入一組元素，插入到隊列中，從命令行讀取個數(shù)k，從中輸出k個隨機的元素。
要求：不能利用額外的String數(shù)組來保存輸入的String對象

import edu.princeton.cs.algs4.StdIn;

public class Permutation {
    public static void main(String[] args) {
        int k = Integer.parseInt(args[0]);
        RandomizedQueue<String> rq = new RandomizedQueue<String>();
        while (!StdIn.isEmpty()) {
            rq.enqueue(StdIn.readString());
        }
        for (int i = 0; i < k; i++) {
            String temp = rq.dequeue();
            System.out.println(temp);
        }
    }
}