首页 > 代码库 > Coursera Algorithms Programming Assignment 2: Deque and Randomized Queue
Coursera Algorithms Programming Assignment 2: Deque and Randomized Queue
这次作业与第一周作业相比，稍微简单一些。有三个编程练习：双端队列（Deque）设计、随机队列（Randomized Queue）设计，还有一个排列组合类Permutation。
一、双端队列Deque
设计要求：A double-ended queue or deque (pronounced "deck") 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.
异常处理要求：Throw a java.lang.IllegalArgumentException if the client attempts to add a null item; throw a java.util.NoSuchElementException if the client attempts to remove an item from an empty deque; throw a java.lang.UnsupportedOperationException if the client calls the remove() method in the iterator; throw a java.util.NoSuchElementException if the client calls the next() method in the iterator and there are no more items to return.
性能要求：Your deque implementation must support each deque operation (including construction) in constant worst-case time. A deque containing n items must use at most 48n + 192 bytes of memory and use space proportional to the number of items currently in the deque. Additionally, your iterator implementation must support each operation (including construction) in constant worst-case time.
分析：
要求可以同时从头尾移除元素，那么该队列内部采用链表更合适，代码如下
1 import java.util.Iterator; 2 import java.util.NoSuchElementException; 3 4 public class Deque<Item> implements Iterable<Item> { 5 private Node first; // 8 bytes 6 private Node last; // 8 bytes 7 private int size; // 4 bytes 8 9 private class Node { // 16字节对象开销+8字节内部类额外开销+8+8+8=48 bytes, n个节点就是48n bytes 10 private Node preNode; // 前一个节点的引用 11 private Item item; 12 private Node nextNode; // 后一个节点的引用 13 } 14 15 private class ListIterator implements Iterator<Item> { 16 // 16字节对象开销+8字节内部类额外开销+8=32 bytes 17 private Node curr = first; 18 19 @Override 20 public boolean hasNext() { 21 // TODO Auto-generated method stub 22 return curr != null; 23 } 24 25 @Override 26 public Item next() { 27 // TODO Auto-generated method stub 28 if (curr == null) 29 throw new NoSuchElementException("there are no more items!"); 30 Item item = curr.item; 31 curr = curr.nextNode; 32 return item; 33 } 34 //remove不用设计，父类Iterator的remove方法就抛出UnsupportedOperationException("remove"); 35 } 36 37 public Deque() { 38 // construct an empty deque 39 size = 0; 40 first = null; 41 last = null; 42 } 43 44 public boolean isEmpty() { 45 // is the deque empty? 46 return (size == 0); 47 } 48 49 public int size() { 50 // return the number of items on the deque 51 return size; 52 } 53 54 public void addFirst(Item item) { 55 // add the item to the front 56 valivate(item); 57 Node newNode = new Node(); 58 newNode.item = item; 59 if (size == 0) { // 空队列的情况 60 newNode.preNode = null; 61 newNode.nextNode = null; 62 first = newNode; 63 last = newNode; 64 } else { 65 newNode.preNode = null; 66 newNode.nextNode = first; 67 first.preNode = newNode; 68 first = newNode; 69 } 70 size++; 71 } 72 73 public void addLast(Item item) { 74 // add the item to the end 75 valivate(item); 76 Node newNode = new Node(); 77 newNode.item = item; 78 if (size == 0) { // 空队列的情况 79 newNode.preNode = null; 80 newNode.nextNode = null; 81 first = newNode; 82 last = newNode; 83 } else { 84 last.nextNode = newNode; 85 newNode.preNode = last; 86 newNode.nextNode = null; 87 last = newNode; 88 } 89 size++; 90 } 91 92 public Item removeFirst() { 93 // remove and return the item from the front 94 if (size == 0) 95 throw new NoSuchElementException("the deque is empty!"); 96 Item returnItem = null; 97 if (size == 1) { 98 returnItem = first.item; 99 first = null; 100 last = null; 101 } else { 102 Node oldfirst = first; 103 returnItem = oldfirst.item; 104 first = oldfirst.nextNode; 105 first.preNode = null; 106 oldfirst.nextNode = null; 107 oldfirst.item = null; 108 } 109 size--; 110 return returnItem; 111 } 112 113 public Item removeLast() { 114 // remove and return the item from the end 115 if (size == 0) 116 throw new NoSuchElementException("the deque is empty!"); 117 Item returnItem = null; 118 if (size == 1) { 119 returnItem = first.item; 120 first = null; 121 last = null; 122 } else { 123 Node oldlast = last; 124 returnItem = oldlast.item; 125 last = oldlast.preNode; 126 last.nextNode = null; 127 oldlast.preNode = null; 128 oldlast.item = null; 129 } 130 size--; 131 return returnItem; 132 } 133 134 public Iterator<Item> iterator() { 135 // return an iterator over items in order from front to end 136 return new ListIterator(); 137 } 138 139 private void valivate(Item item) { 140 if (item == null) 141 throw new IllegalArgumentException("the item is null!"); 142 } 143 144 public static void main(String[] args) { 145 // unit testing (optional) 146 Deque<String> queue = new Deque<String>(); 147 System.out.println(queue.size); 148 queue.addFirst("a"); 149 queue.addFirst("b"); 150 queue.addLast("c"); 151 queue.addFirst("d"); 152 queue.addLast("e"); 153 System.out.println(queue.size); 154 Iterator<String> iter = queue.iterator(); 155 while (iter.hasNext()) { 156 System.out.println(iter.next()); 157 } 158 } 159 }
二、随机队列Randomized Queue
设计要求：A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random from items in the data structure.
异常处理：The order of two or more iterators to the same randomized queue must be mutually independent; each iterator must maintain its own random order. Throw a java.lang.IllegalArgumentException if the client attempts to add a null item; throw a java.util.NoSuchElementException if the client attempts to sample or dequeue an item from an empty randomized queue; throw a java.lang.UnsupportedOperationException if the client calls the remove() method in the iterator; throw a java.util.NoSuchElementException if the client calls the next() method in the iterator and there are no more items to return.
性能要求： Your randomized queue implementation must support each randomized queue operation (besides creating an iterator) in constant amortized time. That is, any sequence of m randomized queue operations (starting from an empty queue) should take at most cm steps in the worst case, for some constant c. A randomized queue containing n items must use at most 48n + 192 bytes of memory. Additionally, your iterator implementation must support operations next() and hasNext() in constant worst-case time; and construction in linear time; you may (and will need to) use a linear amount of extra memory per iterator.
分析：
该队列每次移除的元素是随机的，性能要求提到迭代器的next方法必须是常数时间，很容易发现链表不容易满足该需求，需要用数组，代码如下：
1 import java.util.Iterator; 2 import java.util.NoSuchElementException; 3 import edu.princeton.cs.algs4.StdRandom; 4 5 public class RandomizedQueue<Item> implements Iterable<Item> { 6 private Item[] rqArrays; 7 private int size; 8 9 private class RandomIterator implements Iterator<Item> { 10 private int rank; // rank 记录便利的次数 11 private Item[] iterArrays; //两个迭代器必须相互独立，并且拥有自己的随机顺序 12 13 public RandomIterator(){ 14 rank = size; 15 iterArrays = (Item[]) new Object[rank]; 16 for(int i = 0; i<size; i++){ 17 iterArrays[i] = rqArrays[i]; 18 } 19 } 20 @Override 21 public boolean hasNext() { 22 // TODO Auto-generated method stub 23 return (rank > 0); 24 } 25 @Override 26 public Item next() { 27 // TODO Auto-generated method stub 28 if (rank == 0) 29 throw new NoSuchElementException("there are no more items!"); 30 int r = StdRandom.uniform(0, rank); // 随机选取一个位置的元素返回 31 rank--; 32 Item item = iterArrays[r]; 33 iterArrays[r] = iterArrays[rank]; 34 iterArrays[rank] = item; // 将已经遍历过的元素放置队列末尾，这样下次迭代就不会被选到 35 return item; 36 } 37 } 38 39 public RandomizedQueue() { 40 // construct an empty randomized queue 41 rqArrays = (Item[]) new Object[1]; 42 size = 0; 43 } 44 45 private void valivate(Item item) { 46 if (item == null) 47 throw new IllegalArgumentException("the item is null!"); 48 } 49 50 public boolean isEmpty() { 51 // is the queue empty? 52 return (size == 0); 53 } 54 55 public int size() { 56 // return the number of items on the queue 57 return size; 58 } 59 60 private void resize(int cap) { 61 Item[] temp = (Item[]) new Object[cap]; 62 for (int i = 0; i < size; i++) 63 temp[i] = rqArrays[i]; 64 rqArrays = temp; 65 } 66 67 public void enqueue(Item item) { 68 // add the item 69 valivate(item); 70 rqArrays[size++] = item; 71 if (size == rqArrays.length) 72 resize(2 * rqArrays.length); 73 } 74 75 public Item dequeue() { 76 // remove and return a random item 77 // 随机选取一个位置，将这个位置的元素与队列末尾的元素交换位置 78 // dequeue末尾元素时就达到随机remove元素的目的 79 if (size == 0) 80 throw new NoSuchElementException("the RandomizeQueue is empty!"); 81 int r = StdRandom.uniform(0, size); 82 size--; 83 Item delItem = rqArrays[r]; 84 rqArrays[r] = rqArrays[size]; 85 rqArrays[size] = null; 86 if (size > 0 && size == rqArrays.length / 4) 87 resize(rqArrays.length / 2); 88 return delItem; 89 } 90 91 public Item sample() { 92 // return (but do not remove) a random item 93 if (size == 0) 94 throw new NoSuchElementException("the RandomizeQueue is empty!"); 95 return rqArrays[StdRandom.uniform(0, size)]; 96 } 97 98 public Iterator<Item> iterator() { 99 // return an independent iterator over items in random order 100 return new RandomIterator(); 101 } 102 103 public static void main(String[] args) { 104 // unit testing (optional) 105 RandomizedQueue<String> rq = new RandomizedQueue<String>(); 106 rq.enqueue("a"); 107 rq.enqueue("b"); 108 rq.enqueue("c"); 109 rq.enqueue("d"); 110 rq.enqueue("e"); 111 rq.enqueue("f"); 112 rq.enqueue("g"); 113 rq.dequeue(); 114 Iterator<String> iter1 = rq.iterator(); 115 Iterator<String> iter2 = rq.iterator(); 116 while (iter1.hasNext()) { 117 System.out.print(iter1.next() + ","); 118 } 119 System.out.println(); 120 while (iter2.hasNext()) { 121 System.out.print(iter2.next() + ","); 122 } 123 System.out.println(); 124 125 } 126 }
三、 排列组合类Permutation
设计要求：Write a client program Permutation.java that takes a command-line integer k; reads in a sequence of strings from standard input using StdIn.readString(); and prints exactly k of them, uniformly at random. Print each item from the sequence at most once.
性能要求：The running time of Permutation must be linear in the size of the input. You may use only a constant amount of memory plus either one Deque or RandomizedQueue object of maximum size at most n. (For an extra challenge, use only one Deque or RandomizedQueue object of maximum size at most k.)
输出示例：
分析：
显然Permutation要做的事情就是读取一个k，并且从加载的输入文件内容中选取k个String进行展示，故采用RandomizedQueue比较合适。将文件中所有String都放入RandomizedQueue的话其size就是n，如果只放入k个String的话，RandomizedQueue的size就会是k，目前我只实现了size==n的方法，作业提交得分100。size==4的方法需要再斟酌下，若有进展，及时更新。
1 import edu.princeton.cs.algs4.StdIn; 2 3 public class Permutation { 4 public static void main(String[] args) { 5 RandomizedQueue<String> rq = new RandomizedQueue<String>(); 6 int k = Integer.parseInt(args[0]); 7 while (!StdIn.isEmpty()) { 8 rq.enqueue(StdIn.readString()); 9 // System.out.println(StdIn.readString()); 10 } 11 while (k > 0) { 12 System.out.println(rq.dequeue()); 13 k--; 14 } 15 } 16 }
Coursera Algorithms Programming Assignment 2: Deque and Randomized Queue