Coursera-Algorithm-Part-One-Deques-and-Randomized-Queues

前言

​ Algorithm-Part-One 第二周主要是讲栈和队列，这基本上是大学时期都讲烂的东西，但还是认真看完了视频。本周的作业当然也是跟队列有关的。主要是实现一个双端队列和一个随机队列，这可以说是所有课程当中最轻松的一个变成作业了。难度不大，但需要认真和细心。

Assignment

具体Assignment可以查看这里：http://coursera.cs.princeton.edu/algs4/assignments/queues.html。

本周任务主要是实现如下API：

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

实现

任务1

对于第一个任务，使用链表数据结构来完成。相对节省内存。

package part1_week2;
import edu.princeton.cs.algs4.StdOut;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class Deque<Item> implements Iterable<Item> {
    private Node first;
    private Node last;
    private int size;
    public Deque() {
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public int size() {
        return size;
    }
    public void addFirst(Item item) {
       if (item == null) throw new IllegalArgumentException();
       Node node = new Node();
       node.value = item;
       node.next = first;
       node.prev = null;
       if (first != null) {
           first.prev = node;
       }
        if (last == null) last = node;
        first = node;
       size++;
    }
    public void addLast(Item item) {
        if (item == null) throw new IllegalArgumentException();
        Node node = new Node();
        node.value = item;
        node.next = null;
        node.prev = last;
        if (last != null) {
            last.next = node;
        }
        if (first == null) first = node;
        last = node;
        size++;
    }
    public Item removeFirst() {
        if (isEmpty()) throw new NoSuchElementException();
        Node tempFirst = first;
        first = first.next;
        if (first != null) first.prev = null;
        tempFirst.prev = null;
        tempFirst.next = null;
        size--;
        return tempFirst.value;
    }
    public Item removeLast() {
        if (isEmpty()) throw new NoSuchElementException();
        Node tempLast = last;
        last = last.prev;
        if (last != null) last.next = null;
        tempLast.prev = null;
        tempLast.next = null;
        size--;
        if (isEmpty()) first = null;
        return tempLast.value;
    }
    public Iterator<Item> iterator() {
        return new Itr(first);
    }
    private class Node {
        private Item value;
        private Node prev;
        private Node next;
    }
    public static void main(String[] args) {
//        Deque<Integer> deque = new Deque<>();
//        deque.addFirst(0);
//        deque.addFirst(1);
//        deque.removeFirst();
//        //deque.removeLast();
//        // expected 2 1
        Deque<Integer> deque = new Deque<Integer>();
        deque.addFirst(0);
        deque.removeLast();
        // expected empty
        for (Integer i : deque) {
            StdOut.println(i);
        }
    }
    private class Itr implements Iterator<Item> {
        Node firstNode;
        public Itr(Node first) {
            if (first != null) {
                this.firstNode = new Node();
                this.firstNode.value = first.value;
                this.firstNode.prev = first.prev;
                this.firstNode.next = first.next;
            }
        }
        @Override
        public boolean hasNext() {
            return firstNode != null;
        }
        @Override
        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item next = firstNode.value;
            firstNode = firstNode.next;
            return next;
        }
        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}

任务2

对于第一个任务，参考了Java自带的ArrayList实现方法，使用数组来保存内部元素。

package part1_week2;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class RandomizedQueue<Item> implements Iterable<Item> {
    private static final int INITIAL_CAPACITY = 16;
    private static final int GROW_CAPACITY = 16;
    private Item[] items;
    private int size;
    public RandomizedQueue() {
        items = (Item[]) new Object[INITIAL_CAPACITY];
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public int size() {
        return size;
    }
    public void enqueue(Item item) {
        if (item == null)
            throw new IllegalArgumentException();
        ensureCapacity(size + 1);
        items[size++] = item;
    }
    public Item dequeue() {
        if (isEmpty())
            throw new NoSuchElementException();
        int index = StdRandom.uniform(size);
        Item oldValue = items[index];
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(items, index + 1, items, index,
                    numMoved);
        items[--size] = null;
        return oldValue;
    }
    public Item sample() {
        if (isEmpty())
            throw new NoSuchElementException();
        int index = StdRandom.uniform(size);
        return items[index];
    }
    public Iterator<Item> iterator() {
        return new Itr();
    }
    private void ensureCapacity(int minCapacity) {
        if (minCapacity > items.length) {
            int oldCapacity = items.length;
            int newCapacity = oldCapacity + GROW_CAPACITY;//(oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            items = Arrays.copyOf(items, newCapacity);
        }
    }
    private class Itr implements Iterator<Item> {
        private Item[] randomItems;
        int cursor = 0;
        public Itr() {
            randomItems = Arrays.copyOf(items, size);
            StdRandom.shuffle(randomItems);
        }
        @Override
        public boolean hasNext() {
            return cursor < size;
        }
        @Override
        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            return randomItems[cursor++];
        }
        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
    public static void main(String[] args) {
        RandomizedQueue<Integer> queue = new RandomizedQueue<>();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        queue.enqueue(4);
        queue.dequeue();
        queue.dequeue();
        for (Integer i : queue) {
            StdOut.println(i);
        }
    }
}

想要查看全部源码，传送门：Princeton-Algorithm

总结

尽管题目简单，但是想要写好一个高效可用的Queue，需要考虑内部数据结构如何存储、边界条件，甚至要考虑多线程的情况。优化了很久，最终还是只得了97分，略微遗憾。我知道忙不是借口，但是的确分身乏术，公司的事情还是得优先考虑，后面有时间一定会继续优化！