Exercise 1.3.19 from Algorithms by Sedgewick and Wayne

UndoableQueue.java

/*
 * From Algorithms 4th ed. by Sedgewick and Wayne, pg 164.
 * 
 * Exercise 1.3.19 Give a code fragment that removes the last node in a linked list whose
 * first node is first.
 * 
 * Links to source:
 * https://github.com/kevin-wayne/algs4
 * https://algs4.cs.princeton.edu/home/
 * 
 * Explanation:
 * Use a queue data structure and offer a public "undo" method to undo the last
 * item enqueued.
 * 
 * Sample client code:
 * import edu.princeton.cs.algs4.StdOut;
 * public class Ex1319 {
 *     public static void main(String[] args) {
 *         UndoableQueue<String> linkedList = new UndoableQueue<>();
 *         for (String s : args) linkedList.enqueue(s);
 *         StdOut.printf("%s\n", linkedList.undo());
 *         for (String s : linkedList) StdOut.printf("%s\n", s);
 *     }
 * }
 * 
 * Run configuration:
 * $ java Ex1319 this is a test
 * 
 */
 
import java.util.Iterator;

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

    Node first;
    Node last;
    int count;

    private class Node {
        Node next;
        Item item;
    }

    private boolean isEmpty() {
        return count <= 0;
    }

    public int count() {
        return count;
    }

    public void enqueue(Item item) {
        Node current = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()) first = last;
        else current.next = last;
        count++;
    }

    public Item dequeue() {
        Item item = first.item;
        first = first.next;
        count--;
        if (isEmpty()) last = null;
        return item;
    }

    public Item undo() {
        // Remove the last item added
        Iter iter = new Iter();
        Node secondToLast;
        Item item;
        while (iter.hasNext()) {
            iter.next();
            if (iter.reverseCount() == 2) {
                secondToLast = iter.current;
                item = last.item;
                last = secondToLast;
                last.next = null;
                return item;
            }
        }
        return null;
    }

    public Iterator<Item> iterator() {
        return new Iter();
    }

    private class Iter implements Iterator<Item> {
        Node current = first;
        int reverseCount = count;

        public boolean hasNext() {
            return current != null;
        }

        public Item next() {
            Item item = current.item;
            current = current.next;
            reverseCount--;
            return item;
        }

        private int reverseCount() {
            // Used only to undo the last item added
            return reverseCount;
        }
    }
}