Stack, queue and linked list

Problem

"Undo" undoes the wrong thing

A text editor keeps the actions in a list. Ctrl+Z should undo the last one, but it undoes the first:

List<String> actions = new ArrayList<>();
actions.add("Typed text");
actions.add("Made the title bold");
actions.add("Inserted a photo");

// Ctrl+Z: undo the last action.
String undone = actions.remove(0);
System.out.println("Undone: " + undone);
System.out.println("Left: " + actions);

Output

Undone: Typed text
Left: [Made the title bold, Inserted a photo]

The fix is actions.remove(actions.size() - 1). But everyone who touches this code has to remember which end to remove from. And at the store checkout it is the other way around: the first one who came is served first. Is there a collection that knows the end by itself?

The idea

Stack: the last one on top

A stack is like a pile of plates. You put on top and you take from the top. The last thing put in comes out first. This is called LIFO: last in, first out.

The "Back" button in the browser is a stack:

Deque<String> history = new ArrayDeque<>();
history.push("Home");
history.push("Laptops");
history.push("14-inch laptop");
System.out.println("Now: " + history.peek());

history.pop();
System.out.println("Back: " + history.peek());
System.out.println(history);

Output

Now: 14-inch laptop
Back: Laptops
[Laptops, Home]

• push puts on top, pop removes and returns the top one, and peek only looks at the top one.
• Deque is the interface, and ArrayDeque is the class. Both are in java.util.
• println prints the stack from the top down.

More precisely, if you are curious

• pop on an empty stack stops the program with java.util.NoSuchElementException. peek on an empty stack returns null.
• Java also has an older Stack class. It works, but the Java documentation recommends ArrayDeque:

Stack<String> stack = new Stack<>();
stack.push("Google");
stack.push("Apple");
stack.push("Microsoft");
System.out.println("On top: " + stack.peek());
while (!stack.isEmpty()) {
    System.out.println("Popped: " + stack.pop());
}

Output

On top: Microsoft
Popped: Microsoft
Popped: Apple
Popped: Google

Try it

What is left to undo?

What will the program print?

Deque<String> undo = new ArrayDeque<>();
undo.push("font");
undo.push("color");
undo.push("size");
undo.pop();
undo.push("underline");
while (!undo.isEmpty()) {
    System.out.println(undo.pop());
}

Answer

font
color
underline

underline
size
color
font

font
color
size

underline
color
font

Check

The idea

Queue: first come, first served

A queue is like the line at the checkout. You join at the back, and the first one is served. This is called FIFO: first in, first out.

Print jobs wait in a queue:

Queue<String> printer = new ArrayDeque<>();
printer.offer("invoice.pdf");
printer.offer("contract.docx");
printer.offer("photo.jpg");
System.out.println("Next: " + printer.peek());

while (!printer.isEmpty()) {
    System.out.println("Printing " + printer.poll());
}
System.out.println("Queue: " + printer);

Output

Next: invoice.pdf
Printing invoice.pdf
Printing contract.docx
Printing photo.jpg
Queue: []

• offer puts at the back, poll removes and returns the first one, and peek looks at the first one.
• The type is the Queue interface, and the class is ArrayDeque again. It can do both: be a stack and be a queue. The name comes from double-ended queue, a queue with two ends.
• poll and peek on an empty queue return null.

More precisely, if you are curious

• There are also add, remove() and element(). They do the same, but on an empty queue they throw an exception instead of returning null.
• In older examples the queue is a LinkedList. That works too, because LinkedList also implements Queue:

Queue<String> clients = new LinkedList<>();
clients.offer("Customer 1");
clients.offer("Customer 2");
System.out.println("Served: " + clients.poll());
System.out.println("Waiting: " + clients);

Output

Served: Customer 1
Waiting: [Customer 2]

• ArrayDeque does not accept null as an element. Otherwise poll would have no way to say "it is empty".

Try it

Next at the checkout

The cashier calls the next customer. Which method takes them from the queue?

Queue<String> checkout = new ArrayDeque<>();
checkout.offer("Ivan");
checkout.offer("Maria");
String next = checkout.();
System.out.println("Your turn, " + next);

Check

See it

A linked list inside

ArrayList keeps the elements next to each other in an array. That is why inserting at the front moves all the others. There is another way: each element is in a separate object that holds the value and an arrow to the next one. An object like this is called a node:

class Node {
    String value;
    Node next;

    Node(String value, Node next) {
        this.value = value;
        this.next = next;
    }
}

A list of nodes is called a linked list. It is enough to keep the first node, head. You find each next one by following the next arrow. The last one points to null.

Node head = null;
head = new Node("Coffee", head);
head = new Node("Milk", head);
head = new Node("Bread", head);

for (Node n = head; n != null; n = n.next) {
    System.out.println(n.value);
}

Step by step, in words

1. The list is empty: head points to null.
2. A new node: next is the old head (null), and head moves to the node.
3. The second node points to the first. Nothing moves in memory: only the arrows change.
4. The third node also goes in at the front: the last one added is first.
5. n starts at head and prints each node.
6. n reaches null: the loop stops.

• Inserting at the front: a new node whose next points to the old first one, and head points to the new one. Two arrows, and you move nothing.
• Looping: you start at head and follow next until you reach null.
• The cost: nodes have no indexes. You reach the fifth element by going through the first four.

The idea

LinkedList, and which one when

Java has a ready-made linked list: LinkedList. It implements both List and Deque, so it has add, get and remove, but also addFirst, addLast and getFirst:

LinkedList<String> route = new LinkedList<>();
route.add("Plovdiv");
route.add("Stara Zagora");
route.addFirst("Sofia");
route.addLast("Burgas");
System.out.println(route);

route.remove("Stara Zagora");
System.out.println("After the change: " + route);
System.out.println("From " + route.getFirst() + " to " + route.getLast());

Output

[Sofia, Plovdiv, Stara Zagora, Burgas]
After the change: [Sofia, Plovdiv, Burgas]
From Sofia to Burgas

Which one when:

• A list by number: ArrayList. This is the usual choice.
• A stack or a queue: ArrayDeque.
• LinkedList: rarely. It works for both, but it is usually slower than they are.

More precisely, if you are curious

• Why does LinkedList lose, even at inserting? Each node is a separate object somewhere in memory, and the processor reads data fastest when it sits side by side. The array behind ArrayList and ArrayDeque is exactly that. In practice, LinkedList wins only if you often insert or remove in the middle through an iterator that has already got there.
• LinkedList keeps arrows in both directions, to the next one and to the previous one. That is why getLast and removeLast are fast too. The node from this card has only next. A list like that is called singly linked.

Try it

Find the bug

The method should count the nodes. For the list Bread → Milk → Coffee it returns 2 instead of 3. And for an empty list it stops with NullPointerException. Which line has the bug?

Pick the line with the bug.

1static int count(Node head) {2 int count = 0;3 Node n = head;4 while (n.next != null) {5 count++;6 n = n.next;7 }8 return count;9}

Check

Exercise

Stacks and queues at work

Solve the tasks in your editor. The collection is a private field of the class.

1. A toy train. A Train class with the methods addWagon(String wagon) and removeWagon(). The train is a stack: the last car coupled is the first one uncoupled. removeWagon() returns the uncoupled car, or null if there is none. Add count(). Couple three cars and uncouple two.

Output

Uncoupled: Car 3
Uncoupled: Car 2
Cars: 1

2. A bus route. A BusRoute class with a queue of stops and the methods addStop(String stop) and getNextStop(), which returns the next stop, or null if the route is over. Add "Central Station", "NDK" and "Studentski Grad", and go through the route.

Output

Next stop: Central Station
Next stop: NDK
Next stop: Studentski Grad
End of the route.

3. A stock ticker. A StockTicker class keeps the last N prices of one stock. The constructor gets the symbol and N. updatePrice(double price) adds a price, and if there are more than N prices, it removes the oldest one. Add getLastPrice() and average() for the stored prices. For SAP with N = 3, pass the prices 150, 152, 149 and 155. Hint: Deque has peekLast().

Output

SAP: last price €155.0
Average of the last 3: €152.0

4. Balanced brackets. A code editor checks whether the brackets (), [] and {} are closed in the right order. Write isBalanced(String text) with a stack: at an opening bracket you put it on the stack, and at a closing one you remove the top one and check that it is the same kind. At the end the stack must be empty. Read three lines.

Input

(1 + [2 * 3])
(1 + 2]
((5)

Output

(1 + [2 * 3]) -> yes
(1 + 2] -> no
((5) -> no

5. Your own linked list. A MyLinkedList class with the nodes from the lesson and the methods add(String value) (at the end), remove(String value), contains(String value), size() and toString(). In remove, find the node before the one you are looking for and redirect its next. Check the case where the first one is removed separately.

Output

[Invoice, Report, Meeting]
Contains Report: true
After removal: [Invoice, Meeting]
Size: 2

More tasks

• Undo and Redo. Keep two stacks: undo and redo. A new action goes into undo and clears redo. "Undo" moves the top one from undo to redo, and "Redo" moves it back.
• Words in reverse. Read a sentence and print it with the words in reverse order, going through a stack: "Today is Friday" becomes "Friday is Today".
• Two checkouts. Customers come one by one and go to the checkout with the shorter line. Print who was served at which checkout.
• Reverse the linked list. Add a reverse() method to MyLinkedList that turns the arrows around without making new nodes.

Test

Check yourself

1. You put A on a stack, then B, then C. Which comes out first at pop?

BCA

2. Which one is a job for a queue?

Undoing the last actionThe "Back" button in the browserPrint jobs that are printed in the order they arrive

3. What does poll() return on an empty ArrayDeque?

It throws NoSuchElementException0null

4. Why is inserting at the start of a linked list fast?

Because the list sorts itselfBecause the elements sit next to each other in memoryBecause you make a new node and move two arrows, without touching the other elements

5. What is slow in a linked list?

Adding at the startGetting an element by its number, for example the five hundredthRemoving the first element

Check

Start the lesson over