Visits: 281

Princeton Alhorithms Deques and Randomized Queues

普林斯顿大学算法课第 2 次作业“双端队列与随机队列 ”。

作业要求： https://coursera.cs.princeton.edu/algs4/assignments/queues/specification.php

这一次作业算是比较基本的作业，就是实现双端队列与随机队列，可以说是巩固链表和数组的基本知识的好作业，而且，初步认识到了不可变类型，初步了解到了什么是“多次调用不产生副作用”。

本次代码获得 95 分，正确性满分，空间复杂度满分（还有附加分），时间复杂度稍微扣了点分，但是也懒得去改了。

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

public class Deque<Item> implements Iterable<Item> {

    private Node<Item> head;
    private Node<Item> tail;
    private int size;

    // construct an empty deque
    public Deque() {
    }

    // is the deque empty?
    public boolean isEmpty() {
        return size == 0;
    }

    // return the number of items on the deque
    public int size() {
        return size;
    }

    // add the item to the front
    public void addFirst(Item item) {
        if (item == null) {
            throw new IllegalArgumentException();
        }
        Node<Item> node = new Node<>(item);
        node.setNext(head);
        if (isEmpty()) {
            tail = node;
        }
        head = node;
        size++;
    }

    // add the item to the back
    public void addLast(Item item) {
        if (size == 0) {
            addFirst(item);
        } else {
            if (item == null) {
                throw new IllegalArgumentException();
            }
            Node<Item> node = new Node<>(item);
            tail.setNext(node);
            tail = node;
            if (isEmpty()) {
                head = tail;
            }
            size++;
        }
    }

    // remove and return the item from the front
    public Item removeFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Item item = head.getItem();
        head = head.getNext();
        size--;
        if (isEmpty()) {
            tail = head;
        }
        return item;
    }

    // remove and return the item from the back
    public Item removeLast() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        if (size == 1) {
            return removeFirst();
        }
        Node<Item> cur = head;
        while (cur.getNext() != tail) {
            cur = cur.getNext();
        }
        Item item = tail.getItem();
        tail = cur;
        tail.setNext(null);
        size--;
        return item;
    }

    // return an iterator over items in order from front to back
    @Override
    public Iterator<Item> iterator() {
        return new Iterator<Item>() {
            private Node<Item> cur = head;

            @Override
            public boolean hasNext() {
                return cur != null;
            }

            @Override
            public Item next() {
                if (cur == null) {
                    throw new NoSuchElementException();
                }
                Item item = cur.getItem();
                cur = cur.getNext();
                return item;
            }
        };
    }

    // unit testing (required)
    public static void main(String[] args) {
        Deque<Integer> dq = new Deque<>();
        dq.addFirst(0);
        System.out.println(dq.removeFirst());
        dq.addFirst(1);
        System.out.println(dq.removeLast());
        dq.addLast(2);
        System.out.println(dq.removeFirst());
        dq.addLast(3);
        System.out.println(dq.removeLast());
        System.out.println(dq.isEmpty());
        dq.addFirst(200);
        dq.addFirst(100);
        dq.addLast(300);
        dq.addLast(400);
        System.out.println(dq.size());
        Iterator<Integer> it = dq.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }

}

class Node<Item> {
    private final Item item;
    private Node<Item> next;

    public Node(Item item) {
        this.item = item;
        next = null;
    }

    public void setNext(Node<Item> next) {
        this.next = next;
    }

    public Node<Item> getNext() {
        return next;
    }

    public Item getItem() {
        return item;
    }
}

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

import edu.princeton.cs.algs4.StdRandom;

public class RandomizedQueue<Item> implements Iterable<Item> {

    private Node<Item> head;
    private int size;

    // construct an empty randomized queue
    public RandomizedQueue() {
    }

    // is the randomized queue empty?
    public boolean isEmpty() {
        return size == 0;
    }

    // return the number of items on the randomized queue
    public int size() {
        return size;
    }

    // add the item
    public void enqueue(Item item) {
        if (item == null) {
            throw new IllegalArgumentException();
        }
        Node<Item> node = new Node<>(item);
        node.setNext(head);
        head = node;
        size++;
    }

    private Item randomize(boolean delete) {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        int r = StdRandom.uniform(0, size);
        if (r == 0) {
            // remove head only
            Item item = head.getItem();
            if (delete) {
                head = head.getNext();
                size--;
            }
            return item;
        }
        // go through, and keep pre and cur
        Node<Item> pre = head;
        Node<Item> cur = head.getNext();
        for (int i = 1; i < r; i++) {
            pre = cur;
            cur = cur.getNext();
        }
        Item item = cur.getItem();
        if (delete) {
            pre.setNext(cur.getNext());
            size--;
        }
        return item;
    }

    // remove and return a random item
    public Item dequeue() {
        return randomize(true);
    }

    // return a random item (but do not remove it)
    public Item sample() {
        return randomize(false);
    }

    // return an independent iterator over items in random order
    @Override
    public Iterator<Item> iterator() {
        return new Iterator<Item>() {

            int left = size;
            boolean[] visited = new boolean[left];

            @Override
            public boolean hasNext() {
                return left > 0;
            }

            @Override
            public Item next() {
                if (left == 0) {
                    throw new NoSuchElementException();
                }
                int r = StdRandom.uniform(size);
                while (visited[r]) {
                    r = StdRandom.uniform(size);
                }
                visited[r] = true;
                left--;
                Node<Item> cur = head;

                for (int i = 0; i < r; i++) {
                    cur = cur.getNext();
                }
                return cur.getItem();
            }
        };
    }

    // unit testing (required)
    public static void main(String[] args) {
        RandomizedQueue<Integer> rq = new RandomizedQueue<>();
        rq.enqueue(1);
        rq.enqueue(2);
        rq.enqueue(3);
        System.out.println(rq.isEmpty());
        System.out.println(rq.size());
        System.out.println(rq.sample());
        System.out.println(rq.dequeue());
        Iterator<Integer> it = rq.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }

}

class Node<Item> {
    private final Item item;
    private Node<Item> next;

    public Node(Item item) {
        this.item = item;
        next = null;
    }

    public void setNext(Node<Item> next) {
        this.next = next;
    }

    public Node<Item> getNext() {
        return next;
    }

    public Item getItem() {
        return item;
    }
}

import edu.princeton.cs.algs4.StdIn;

import java.util.NoSuchElementException;

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