Step 3 of 6

Stacks and queues on linked nodes

Many programs don't need a list's get(index) at all. They only add and remove at the ends, and two ways of doing that have names of their own.

A stack: last in, first out

A stack adds and removes at one end only, its top, like a pile of plates: the plate you put on last is the first you take off. Its operations are usually called push (put on top), pop (take the top one off and return it), peek (look at the top one without taking it) and isEmpty. The call stack (module 11, and module 55's recursion) is one: the newest call is on top, and it's the first to finish.

On linked nodes the top is the head: push is addFirst, and pop is removeFirst. Both take a few steps whatever the size. This stack of whole numbers gives back 1, 2, 3 and 4 in the opposite order:

Main.java

public class Main {
    public static void main(String[] args) {
        NumberStack stack = new NumberStack();
        for (int digit = 1; digit <= 4; digit++) {
            stack.push(digit);
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
        System.out.println();
    }
}

NumberStack.java

public class NumberStack {
    private NumberNode top;

    public void push(int value) {
        this.top = new NumberNode(value, this.top);
    }

    public int pop() {
        int value = this.top.value;
        this.top = this.top.next;
        return value;
    }

    public boolean isEmpty() {
        return this.top == null;
    }
}

NumberNode.java

public class NumberNode {
    int value;
    NumberNode next;

    public NumberNode(int value, NumberNode next) {
        this.value = value;
        this.next = next;
    }
}

Output

4 3 2 1

NumberStack has no constructor of its own, so Java gives it a default constructor that takes no parameters, and top starts as null, the default value of a reference variable. This pop crashes on an empty stack with a NullPointerException; a better one checks first and throws an exception with a clear message.

A queue: first in, first out

A queue adds at one end, its back, and removes at the other, its front, like a line at a counter: whoever came first is served first. Its operations are often called enqueue (join at the back) and dequeue (leave from the front).

On linked nodes, the front is the head and the back is the tail, with the links pointing from front to back:

head                                   tail
[report.pdf] --> [map.png] --> [menu.txt] --> null

enqueue is step 2's addLast: link the new node after tail, and move tail to it.
dequeue is removeFirst: take the head's value, and move head to head.next. When the queue becomes empty, set tail to null as well.

Why not the other way round, adding at the head and removing at the tail? To remove the last node, a list must set the next of the node before it to null, and the only way to find that node is to walk from the head. With the links pointing front to back, both operations take a few steps.

Checking brackets with a stack

Brackets in a formula must close in the opposite order to the one they opened in: ([]) is fine, ([)] isn't. A stack checks this. Go through the characters one by one:

an opening bracket, (, [ or {, is pushed;
a closing bracket must match the opening bracket on top of the stack, which is popped. If the stack is empty, or the top is the wrong kind, the brackets aren't balanced;
other characters are skipped.

At the end, the stack must be empty: anything left on it was never closed.

Your task

Challenge 1 of 3

An office keeps incoming letters in a tray, and the newest letter is always on top. In InTray.java, write a stack of Strings on linked nodes (the class LetterNode is ready), with:

push(String letter) puts a letter on top;
pop() takes the top letter off and returns it;
peek() returns the top letter without taking it off;
isEmpty() and size().

pop and peek on an empty tray throw an IllegalStateException with the message The tray is empty. The check runs:

InTray tray = new InTray();
tray.push("invoice");
tray.push("postcard");
tray.push("tax form");
System.out.println(tray.peek() + ", " + tray.size() + " letters");
System.out.println(tray.pop());
System.out.println(tray.pop());
System.out.println(tray.size() + " " + tray.isEmpty());

and expects:

tax form, 3 letters
tax form
postcard
1 false

Challenge 2

An office printer prints documents in the order they were sent. In PrintQueue.java, write a queue of document names on linked nodes (JobNode is ready). Keep references to both the first node and the last one (head and tail), so that neither method walks through the queue:

enqueue(String document) adds a document at the back;
dequeue() removes the document at the front and returns it. On an empty queue it throws an IllegalStateException with the message Nothing to print;
isEmpty() and size().

The check runs:

PrintQueue queue = new PrintQueue();
queue.enqueue("report.pdf");
queue.enqueue("map.png");
System.out.println("Printing " + queue.dequeue());
queue.enqueue("menu.txt");
while (!queue.isEmpty()) {
    System.out.println("Printing " + queue.dequeue() + ", " + queue.size() + " left");
}

and expects:

Printing report.pdf
Printing map.png, 1 left
Printing menu.txt, 0 left

Challenge 3

A spreadsheet checks the brackets in a formula before it calculates anything. Write the method balanced(String formula) in Main.java. It returns true when every bracket, (, [ and {, is closed by the matching ), ] or } in the right order, and false otherwise. Other characters don't matter. Use the stack of characters in CharStack.java (it has push, pop, peek and isEmpty; pop and peek throw an exception on an empty stack, so check isEmpty() first), the way the lesson describes. The check runs:

System.out.println(balanced("=SUM((A1+B2)*[C3])"));
System.out.println(balanced("=MAX(A1,{B2)}"));
System.out.println(balanced("=(A1+B2"));
System.out.println(balanced("=A1)"));

and expects:

true
false
false
false

Previous: A linked list class Next: ArrayDeque from the library