Learning objectives:

• Implement fundamental collections using resizing arrays and linked lists
• Work with generics and iterators in Java
• Practice modular programming with prescribed APIs

Preamble

A quick reminder on the course policy. The autograder provides feedback only, it does not determine your grade. See the assignment FAQ for more details on the grading policy.

Our recommendation. Write your own code from scratch and aim to complete every requirement by the completion deadline. Treat each assignment as if the autograder score determined your grade. Working code that you understand is the sweet spot: it makes demos easy and reflects real learning. Start early to give yourself time to debug.

You will need to know two Java concepts to complete this assignment: generics and iterators. We review them here, but you are free to skip this section if you are comfortable with the topics.

Working with generics

Generics allow you to write a single class that works with different types. Instead of implementing StackOfStrings, StackOfURLs, StackOfInts, etc., you can implement a single generic Stack<Item> that works with any reference type.

Type parameters. A generic class declares a type parameter (e.g., Item) as a placeholder for the concrete type (e.g., String or Apple). When a client creates an instance, they specify a type argument:

Stack<String> stack = new Stack<>();

The <> is called the diamond operator, Java infers the item type from the variable declaration.

Generics provide compile-time type safety. If you try to push the wrong type onto a stack, the compiler catches the error:

Stack<Apple> stack = new Stack<>();
Apple apple = new Apple();
stack.push(apple);
Orange orange = new Orange();
stack.push(orange);    // compile-time error

Generic type arguments must be reference types, not primitive types. Each primitive type has an associated wrapper type:

Java automatically converts between primitives and their wrapper types:

• Autoboxing: automatic conversion from primitive type to wrapper type.
• Unboxing: automatic conversion from wrapper type to primitive type.

Stack<Integer> stack = new Stack<>();
stack.push(17);             // autoboxing (int -> Integer)
int x = stack.pop();        // unboxing (Integer -> int)

Generic array creation. Java prohibits the creation of arrays of generic types. The following code leads to a generic array creation compile-time error:

Item[] a = new Item[1];

Instead, use a cast:

Item[] a = (Item[]) new Object[1];

This will produce an unavoidable compiler warning about an "unchecked cast." This particular warning is expected and acceptable. However, you should not receive any other compiler warnings on this assignment.

Working with iterators

Iterators allow clients to iterate through the items in a collection without knowing its internal representation. Java's enhanced for loop (foreach) provides a convenient syntax for iteration:

Stack<String> stack = new Stack<>();
for (String s : stack)
    StdOut.println(s);

This foreach loop is equivalent to the following while loop:

Iterator<String> i = stack.iterator();
while (i.hasNext()) {
    String s = i.next();
    StdOut.println(s);
}

To support the foreach syntax, a class must implement the Iterable interface, which requires a single method that returns an Iterator:

public interface Iterable<Item> {
    Iterator<Item> iterator();
}

The Iterator interface requires two methods: hasNext() returns whether there are more items to iterate, and next() returns the next item:

public interface Iterator<Item> {
    boolean hasNext();
    Item next();
}

Implementing an iterator. To make a data structure iterable, you need to:

1. Add implements Iterable<Item> to the class declaration.
2. Implement the iterator() method that returns an Iterator<Item>.
3. Create a nested class that implements Iterator<Item>.

Here is a typical pattern for implementing an iterator in an array-based data structure:

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

public class Stack<Item> implements Iterable<Item> {
    private int n;    // number of items in the stack
    private Item[] a; // stack items
    ...
    public Iterator<Item> iterator() {
        return new ArrayIterator();
    }

    private class ArrayIterator implements Iterator<Item> {
        private int i = n - 1; // index of next item to return

        public boolean hasNext() { return i > 0; }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            return a[i--];
        }
    }
}

The nested class ArrayIterator can access the instance variables of the enclosing class (such as n and a[]). Each call to iterator() returns a new, independent iterator.

You can see two examples of complete data structures illustrating iterators here:

• ResizingArrayStack.java implements a stack using a resizing array.
• LinkedStack.java implements a stack using a singly linked list.

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 collection. Create a generic data type Deque that implements the following API:

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

    // construct an empty deque
    public Deque()

    // is the deque empty?
    public boolean isEmpty()

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

    // add the item to the front
    public void addFirst(Item item)

    // add the item to the back
    public void addLast(Item item)

    // remove and return the item from the front
    public Item removeFirst()

    // remove and return the item from the back
    public Item removeLast()

    // return an iterator over items in order from front to back
    public Iterator<Item> iterator()

    // unit testing
    public static void main(String[] args)

}

You may use arrays, linked lists, or your own data structure to implement the deque, provided you meet the specified performance and memory requirements.

Unit testing

You are not required to create unit tests for this class, and the autograder will not check them. However, writing tests in your main() method is a good way to verify your implementation works correctly.

Testing tips:

• Test intermixed sequences of operations, not just isolated methods.
• Make sure to test what happens when your data structure goes from non-empty to empty and back to non-empty—this is a common source of bugs.
• Avoid loitering: when you remove an item, make sure to set the corresponding array entry or linked-list reference to null so that the garbage collector can reclaim the memory.

Randomized Queue

A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random among items in the collection—meaning each of the $n$ items should be equally likely to be removed (with probability $1/n$). You can generate a pseudo-random integer between 0 and $n-1$ using StdRandom.uniformInt(n).

Create a generic data type RandomizedQueue that implements the following API:

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

    // construct an empty randomized queue
    public RandomizedQueue()

    // is the randomized queue empty?
    public boolean isEmpty()

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

    // add the item
    public void enqueue(Item item)

    // remove and return a random item
    public Item dequeue()

    // return a random item (but do not remove it)
    public Item sample()

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

    // unit testing
    public static void main(String[] args)

}

Note that sample() returns a random item without removing it, so repeated calls may return the same item more than once. This is known as "sampling with replacement."

You may use arrays, linked lists, or your own data structure to implement the randomized queue, provided you meet the specified performance and memory requirements.

Unit testing

You are not required to create unit tests for this class, and the autograder will not check them. However, writing tests in your main() method is a good way to verify your implementation works correctly.

Test that multiple iterators can be used simultaneously and operate independently of one another. For example, the following code uses two nested iterators:

int n = 5;
RandomizedQueue<Integer> queue = new RandomizedQueue<Integer>();
for (int i = 0; i < n; i++)
    queue.enqueue(i);
for (int a : queue) {
    for (int b : queue)
        StdOut.print(a + "-" + b + " ");
    StdOut.println();
}

It should produce a result like (your output might be different, since this is in random order):

0-2 0-1 0-3 0-0 0-4
1-2 1-1 1-4 1-0 1-3
2-1 2-4 2-0 2-3 2-2
4-2 4-3 4-4 4-1 4-0
3-2 3-3 3-1 3-0 3-4

Note that each row has a different random order, demonstrating that the iterators are independent.

Permutation

Write a client program Permutation.java that takes an integer $k$ as a command-line argument; reads 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.

~/Desktop/queues> more distinct.txt
A B C D E F G H I

~/Desktop/queues> java-algs4 Permutation 3 < distinct.txt
C
G
A

~/Desktop/queues> java-algs4 Permutation 3 < distinct.txt
E
F
G

~/Desktop/queues> more duplicates.txt
AA BB BB BB BB BB CC CC

~/Desktop/queues> java-algs4 Permutation 8 < duplicates.txt
BB
AA
BB
CC
BB
BB
CC
BB

Your program must implement the following API:

public class Permutation {
   public static void main(String[] args)
}

Deliverables

Project files

The file queues.zip contains sample data files. It also contains feedback.txt, which you should fill out, and acknowledgments.txt, which you should complete with citations and collaboration information.

Submission

Submit the programs RandomizedQueue.java, Deque.java, and Permutation.java.

Your submission may not call library functions except those in StdIn, StdOut, StdRandom, java.lang, java.util.Iterator, and java.util.NoSuchElementException. In particular, do not use either java.util.LinkedList or java.util.ArrayList. The goal of this assignment is to implement data types from first principles using resizing arrays and linked lists. Also, you must use StdIn (instead of java.util.Scanner) because our testing infrastructure intercepts calls to StdIn.

Finally, submit feedback.txt and acknowledgments.txt files and answer the questions.

Advice and Further Challenges

Suggested Approach

To help you work through the assignment, here is a suggested list of steps for how you might make progress. You don't have to follow this list to complete the assignment and in fact we recommend you don't look at it unless you get stuck.

Further Challenges