Deques and Randomized Queues

实现泛型双端队列和随机队列。

Deque.java

双端队列使用链表实现，双向链表，有next和prev两个引用，分别指向下一个和上一个结点。

import java.util.Iterator; import java.util.NoSuchElementException; import edu.princeton.cs.algs4.StdIn; import edu.princeton.cs.algs4.StdOut; /** * The {@code Deque} class represents a double-ended queue or deque, which is * a generalization of a stack and a queue that supports adding and removing * items from either the front or the back of the data structure. * <p> * This implementation uses a double-linked list with a non-static nested class for * linked-list nodes. * * @author zhangyu * @date 2017.3.10 */ public class Deque<Item> implements Iterable<Item> { private int n; private Node first; private Node last; private Node sentinel; // helper linked list class private class Node { private Item item; private Node next; private Node prev; } /** * Initializes an empty deque. */ public Deque() { first = null; last = first; sentinel = new Node(); sentinel.next = first; n = 0; } /** * Returns whether the deque is empty. * * @return true if this deque is empty; false otherwise */ public boolean isEmpty() { return sentinel.next == null; } /** * Returns the number of items on this deque. * * @return the number of items on this deque */ public int size() { return n; } /** * Add the item to the front of the deque. * * @param item the item to add * @throws NullPointerException if the item to be added is null */ public void addFirst(Item item) { if (item == null) throw new NullPointerException("Null item"); Node oldFirst = first; first = new Node(); first.item = item; first.next = oldFirst; first.prev = sentinel; if (!isEmpty()) oldFirst.prev = first; else last = first; sentinel.next = first; n++; } /** * Add the item to the end of the deque. * * @param item the item to add * @throws NullPointerException if the item to be added is null */ public void addLast(Item item) { if (item == null) throw new NullPointerException("Null item"); if (isEmpty()) addFirst(item); else { Node oldLast = last; last = new Node(); last.item = item; oldLast.next = last; last.prev = oldLast; last.next = null; n++; } } /** * Remove and return the item from the front of the deque. * * @return the item on the front of this deque * @throws NoSuchElementException if this deque is empty */ public Item removeFirst() { if (isEmpty()) throw new NoSuchElementException("Deque underflow"); Item item = first.item; // save item to return first = first.next; sentinel.next = first; // delete first node if (isEmpty()) last = null; // to avoid loitering else first.prev = sentinel; n--; return item; // return the saved item } /** * Remove and return the item from the end of the deque. * * @return the item on the end of this deque * @throws NoSuchElementException if this deque is empty */ public Item removeLast() { if (isEmpty()) throw new NoSuchElementException("Deque underflow"); Item item = last.item; last = last.prev; last.next = null; if (isEmpty()) // to avoid loitering { first = null; last = first; } n--; return item; } /** * Returns an iterator over items in order from front to end. * * @return an iterator over items in order from front to end * @see java.lang.Iterable#iterator() */ public Iterator<Item> iterator() { return new ListIterator(); } // an iterator, doesn't implement remove() since it's optional private class ListIterator 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; } } /** * Unit tests the {@code Deque} data type. * * @param args the command-line arguments */ public static void main(String[] args) { Deque<String> deque = new Deque<String>(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) deque.addLast(item); else if (!deque.isEmpty()) deque.removeFirst(); for (String str : deque) StdOut.print(str + " "); StdOut.println("\t" + deque.isEmpty()); } } }

RandomizedQueue.java

随机队列使用可调整大小的数组实现。

import java.util.Iterator; import java.util.NoSuchElementException; import edu.princeton.cs.algs4.StdIn; import edu.princeton.cs.algs4.StdOut; import edu.princeton.cs.algs4.StdRandom; /** * The {@code RandomizedQueue} class represents a randomized queue, which is * similar to a stack or queue, except that the item removed is chosen uniformly * at random from items in the data structure. * <p> * This implementation uses a resizing array, which double the underlying array * when it is full and halves the underlying array when it is one-quarter full. * * @author zhangyu * @date 2017.3.10 */ public class RandomizedQueue<Item> implements Iterable<Item> { private Item[] a; private int n; /** * Constructs an empty randomized queue. */ public RandomizedQueue() { a = (Item[]) new Object[2]; n = 0; } /** * Returns whether the randomized queue is empty. * * @return true if this randomized queue is empty; * false otherwise */ public boolean isEmpty() { return n == 0; } /** * Returns the number of items on the queue. * * @return the number of items on the queue */ public int size() { return n; } // resize the underlying array private void resize(int capacity) { assert capacity >= n; Item[] temp = (Item[]) new Object[capacity]; for (int i = 0; i < n; i++) temp[i] = a[i]; a = temp; } /** * Adds the item to this queue. * * @param item the item to add * @throws NullPointerException if the item to be added is null */ public void enqueue(Item item) { if (item == null) throw new NullPointerException("Null item"); if (n == a.length) resize(2 * a.length); // double the size of array if necessary a[n++] = item; } /** * Removes and returns a random item * * @return a random item on this queue * @throws NoSuchElementException if the queue is empty */ public Item dequeue() { if (isEmpty()) throw new NoSuchElementException("Empty randomized queue"); int randomizedIdx = StdRandom.uniform(n); Item item; item = a[randomizedIdx]; a[randomizedIdx] = a[n - 1]; // move the last item to the empty position a[--n] = null; // to avoid loitering // shrink the size of array if necessary if (n > 0 && n == a.length/4) resize(a.length/2); return item; } /** * Returns (but do not removes) a random item. * * @return a random item on this queue without removing it * @throws NoSuchElementException if the queue is empty */ public Item sample() { if (isEmpty()) throw new NoSuchElementException("Empty randomized queue"); int randomizedIdx = StdRandom.uniform(n); return a[randomizedIdx]; } /** * Returns an independent iterator over items in random order. * * @return an independent iterator over items in random order * @see java.lang.Iterable#iterator() */ public Iterator<Item> iterator() { return new ListIterator(); } // an iterator, doesn't implement remove() since it's optional private class ListIterator implements Iterator<Item> { private int[] randomIndices = StdRandom.permutation(n); private int i = 0; public boolean hasNext() { return i < n; } public void remove() { throw new UnsupportedOperationException(); } public Item next() { if (!hasNext()) throw new NoSuchElementException(); return a[randomIndices[i++]]; } } /** * Unit tests the {@code RandomizedQueue} data type. * * @param args the command-line arguments */ public static void main(String[] args) { RandomizedQueue<String> rq = new RandomizedQueue<String>(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) rq.enqueue(item); else if (!rq.isEmpty()) rq.dequeue(); for (String str : rq) StdOut.print(str + " "); StdOut.println("\t" + rq.isEmpty()); } } }

Permutation.java

Permutation中，为了能够尽量少使用内存，使用了StringBuilder类的append()方法接收到来的字符串。接收完毕将StringBuilder对象转化为String对象，这相比于直接用String对象进行’+’操作（平方时间）要快很多。然后将接收的字符串分割成为字符串数组，再调用StdRandom的permutation()生成指定大小的随机化字符串索引数组，将数组包含的索引对应的字符串入队。最后遍历。与直接将接收的字符串入队相比，用的内存要少一点，得到了一个bonus：)。

import edu.princeton.cs.algs4.StdIn; import edu.princeton.cs.algs4.StdOut; import edu.princeton.cs.algs4.StdRandom; /** * The {@code Permutation} class implements a client that takes a command-line * integer k; reads in a sequence of strings from standard input; and prints * exactly k of them, uniformly at random. * <p> * Each item from the sequence is printed at most once. * * @author zhangyu * @date 2017.3.10 */ public class Permutation { /** * Creates one {@code RandomizedQueue} object * of maximum size at most k. * * @param args the command-line arguments */ public static void main(String[] args) { RandomizedQueue<String> rq = new RandomizedQueue<String>(); StringBuilder builder = new StringBuilder(); int cnt = 0; while (!StdIn.isEmpty()) { builder.append(StdIn.readString()).append(' '); cnt++; } if (builder.length() > 0) builder.deleteCharAt(builder.length() -1); String[] strs = builder.toString().split(" "); // splits converted str into a String array int k = Integer.parseInt(args[0]); int[] indices = StdRandom.permutation(cnt, k); for (int i = 0; i < k; ++i) rq.enqueue(strs[indices[i]]); for (String s : rq) StdOut.println(s); } }

这里编译有两个警告，是因为Java不允许创建泛型数组（某些历史和技术原因），所以泛型数组只能通过强制类型转换(Item[]) new Object[cap];实现。因此出现的警告不可避免，忽略即可。

ASSESSMENT SUMMARY Compilation: PASSED (0 errors, 2 warnings) API: PASSED Findbugs: PASSED Checkstyle: PASSED Correctness: 43/43 tests passed Memory: 54/53 tests passed Timing: 110/110 tests passed Aggregate score: 100.19% [Compilation: 5%, API: 5%, Findbugs: 0%, Checkstyle: 0%, Correctness: 60%, Memory: 10%, Timing: 20%]

参考我的github