Skip to content
wannacode

Stack, queue and linked list

Problem

"Undo" undoes the wrong thing

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

const actions = [];
actions.push("Typed text");
actions.push("Made the title bold");
actions.push("Inserted a photo");


// Ctrl+Z: undo the last action.
const undone = actions.shift();
console.log(`Undone: ${undone}`);
console.log("Left:", actions);
Output
Undone: Typed text
Left: [ 'Made the title bold', 'Inserted a photo' ]

The fix is actions.pop(). 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:

const history = [];
history.push("Home");
history.push("Laptops");
history.push("14-inch laptop");
console.log(`Now: ${history.at(-1)}`);


history.pop();
console.log(`Back: ${history.at(-1)}`);
console.log(history);
Output
Now: 14-inch laptop
Back: Laptops
[ 'Home', 'Laptops' ]

JavaScript has no separate class for a stack: an array is a stack if you put and take only at the end.

  • push puts on top, pop() removes and returns the top one, and at(-1) only looks at the top one.
  • The top is the end of the array. Both operations are fast, because nothing moves at the end.
  • console.log prints the stack from the bottom up: the top one is last.
More precisely, if you are curious
  • pop() and at(-1) on an empty array do not stop the program. They give undefined:
const history = [];
console.log(history.pop());
console.log(history.at(-1));
Output
undefined
undefined

So check history.length before you take.

Try it

What is left to undo?

What will the program print?

const undo = [];
undo.push("font");
undo.push("color");
undo.push("size");
undo.pop();
undo.push("underline");
while (undo.length > 0) {
  console.log(undo.pop());
}
Answer

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:

const printer = [];
printer.push("invoice.pdf");
printer.push("contract.docx");
printer.push("photo.jpg");
console.log(`Next: ${printer[0]}`);


while (printer.length > 0) {
  console.log(`Printing ${printer.shift()}`);
}
console.log("Queue:", printer);
Output
Next: invoice.pdf
Printing invoice.pdf
Printing contract.docx
Printing photo.jpg
Queue: []

JavaScript has no separate class for a queue. An array becomes a queue if you put at the back and take from the front:

  • push puts at the back, shift removes and returns the first one, and printer[0] looks at the first one.
  • shift on an empty array gives undefined. It does not stop the program.

But shift has a cost. It moves all the others one place forward, like inserting at the front in the lesson on arrays. With a few print jobs you do not notice it. With a queue of tens of thousands of elements, it is many times slower than just reading in order. That is when you use the linked list from the next card, which keeps both the first and the last node.

More precisely, if you are curious
  • shift on an empty queue:
const clients = ["Customer 1"];
console.log(`Served: ${clients.shift()}`);
console.log(clients.shift());
Output
Served: Customer 1
undefined
  • The V8 engine sometimes makes shift fast by moving the start of the array instead of moving the elements. With big arrays this does not happen. Do not rely on it.

Try it

Next at the checkout

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

const checkout = [];
checkout.push("Ivan");
checkout.push("Maria");
const client = checkout.();
console.log(`Your turn, ${client}`);

See it

A linked list inside

An array 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 {
  constructor(value, 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.

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


for (let n = head; n !== null; n = n.next) {
  console.log(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

The array, and which one when

JavaScript has no ready-made linked list. An array can add and remove at both ends: push and pop at the back, unshift and shift at the front:

const route = [];
route.push("Plovdiv");
route.push("Stara Zagora");
route.unshift("Sofia");
route.push("Burgas");
console.log(route);


route.splice(route.indexOf("Stara Zagora"), 1);
console.log("After the change:", route);
console.log(`From ${route[0]} to ${route.at(-1)}`);
Output
[ 'Sofia', 'Plovdiv', 'Stara Zagora', 'Burgas' ]
After the change: [ 'Sofia', 'Plovdiv', 'Burgas' ]
From Sofia to Burgas

Which one when:

  • A list by number: an array. This is the usual choice.
  • A stack: an array with push and pop.
  • A queue: an array with push and shift, while it is small. A big queue with thousands of elements: a linked list like the one from the previous card, which also keeps the last node.
More precisely, if you are curious
  • unshift is like shift: it moves all the elements by one place, so it is slow at the front of a big array.
  • Why is an array usually faster than a linked list, even at inserting? Each node is a separate object somewhere in memory, and the processor reads data fastest when it sits side by side. An array is exactly that.
  • The node from this card has only next. A list like that is called singly linked.

Try it

Find the bug

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

Pick the line with the bug.

Exercise

Stacks and queues at work

Solve the tasks in your editor. The collection is a private field of the class, with a # in front.

1. A toy train. A Train class with the methods addWagon(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(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(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: at(-1) is the last price. Print the prices with two digits after the decimal point, with toFixed(2).

Output
SAP: last price €155.00
Average of the last 3: €152.00

4. Balanced brackets. A code editor checks whether the brackets (), [] and {} are closed in the right order. Write isBalanced(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(value) (at the end), remove(value), contains(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.
  • A fast queue. Add a field for the last node to MyLinkedList, so that add at the end is fast too. Now it is a queue without shift: add at the back, removing the first one at the front.

Test

Check yourself

1. You put A on a stack, then B, then C. Which comes out first at pop?
2. Which one is a job for a queue?
3. What does shift() return on an empty array?
4. Why is inserting at the start of a linked list fast?
5. What is slow in a linked list?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·