Problem 1. (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. Create a generic data type Deque, based on the LinkedQueue.java code from the previous lab

import edu.princeton.cs.algs4.StdOut; import edu.princeton.cs.algs4.StdRandom; import java.util.Iterator; import java.util.NoSuchElementException;

// Deque implementation using a linked list. public class LinkedDeque implements Iterable { ...

// Helper doubly-linked list class. private class Node { private Item item; private Node next; private Node prev; }

// Construct an empty deque. public LinkedDeque() { ... }

// Is the dequeue empty? public boolean isEmpty() { ... }

// The number of items on the deque. public int size() { ... }

// Add item to the front of the deque. public void addFirst(Item item) { ... }

// Add item to the end of the deque. public void addLast(Item item) { ... }

// Remove and return item from the front of the deque. public Item removeFirst() { ... }

// Remove and return item from the end of the deque. public Item removeLast() { ... }

// An iterator over items in the queue in order from front to end. public Iterator iterator() { ... } // An iterator, doesn't implement remove() since it's optional. private class DequeIterator implements Iterator { ... DequeIterator() { ... }

public boolean hasNext() { ... }

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

public Item next() { ... } }

// A string representation of the deque. public String toString() { StringBuilder s = new StringBuilder(); for (Item item : this) { s.append(item + " "); } return s.toString().substring(0, s.length() - 1); } // Test client. [DO NOT EDIT] public static void main(String[] args) { LinkedDeque deque = new LinkedDeque(); String quote = "There is grandeur in this view of life, with its " + "several powers, having been originally breathed into a few " + "forms or into one; and that, whilst this planet has gone " + "cycling on according to the fixed law of gravity, from so " + "simple a beginning endless forms most beautiful and most " + "wonderful have been, and are being, evolved. ~ " + "Charles Darwin, The Origin of Species"; int r = StdRandom.uniform(0, quote.length()); for (int i = quote.substring(0, r).length() - 1; i >= 0; i--) { deque.addFirst(quote.charAt(i)); } for (int i = 0; i < quote.substring(r).length(); i++) { deque.addLast(quote.charAt(r + i)); } StdOut.println(deque.isEmpty()); StdOut.printf("(%d characters) ", deque.size()); for (char c : deque) { StdOut.print(c); } StdOut.println(); double s = StdRandom.uniform(); for (int i = 0; i < quote.length(); i++) { if (StdRandom.bernoulli(s)) { deque.removeFirst(); } else { deque.removeLast(); } } StdOut.println(deque.isEmpty()); } }

Problem 2. (Random Queue) A random queue is similar to a stack or queue, except that the item removed is chosen uniformly at random from items in the data structure. Create a generic iterable data type ResizingArrayRandomQueue in ResizingArrayRandomQueue.java

import edu.princeton.cs.algs4.StdIn; import edu.princeton.cs.algs4.StdOut; import edu.princeton.cs.algs4.StdRandom; import java.util.Iterator; import java.util.NoSuchElementException;

// Random queue implementation using a resizing array. public class ResizingArrayRandomQueue implements Iterable { ... // Construct an empty queue. public ResizingArrayRandomQueue() { ... }

// Is the queue empty? public boolean isEmpty() { ... }

// The number of items on the queue. public int size() { ... }

// Add item to the queue. public void enqueue(Item item) { ... }

// Remove and return a random item from the queue. public Item dequeue() { ... }

// Return a random item from the queue, but do not remove it. public Item sample() { ... }

// An independent iterator over items in the queue in random order. public Iterator iterator() { ... } // An iterator, doesn't implement remove() since it's optional. private class RandomQueueIterator implements Iterator { ... RandomQueueIterator() { ... } public boolean hasNext() { ... }

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

public Item next() { ... } }

// A string representation of the queue. public String toString() { StringBuilder s = new StringBuilder(); for (Item item : this) { s.append(item + " "); } return s.toString().substring(0, s.length() - 1); }

// Helper method for resizing the underlying array. private void resize(int max) { Item[] temp = (Item[]) new Object[max]; for (int i = 0; i < N; i++) { if (q[i] != null) { temp[i] = q[i]; } } q = temp; }

// Test client. [DO NOT EDIT] public static void main(String[] args) { ResizingArrayRandomQueue q = new ResizingArrayRandomQueue(); while (!StdIn.isEmpty()) { q.enqueue(StdIn.readInt()); } int sum1 = 0; for (int x : q) { sum1 += x; } int sum2 = sum1; for (int x : q) { sum2 -= x; } int sum3 = 0; while (q.size() > 0) { sum3 += q.dequeue(); } StdOut.println(sum1); StdOut.println(sum2); StdOut.println(sum3); StdOut.println(q.isEmpty()); } }