Lessons · TypeScript · stacks and queues
Last in first out, and first in first out
An array is already a stack: push and pop work at the end. For a queue, shift() takes from the front but moves every remaining item, so a real queue keeps a head index instead.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
Undo, bracket matching and the call stack are stacks. Breadth-first search and any fair job order are queues. Naming which one the problem wants is most of the solution.
How to think about it
Ask what comes out NEXT. The most recent thing: push and pop. The oldest waiting thing: a queue, and on a big one keep an index rather than calling shift.
Worked example
const stack = [];An array is a stack.
stack.push('a'); stack.push('b');Push twice.console.log(stack.pop());b
const queue = ['a', 'b', 'c'];The items waiting.
let head = 0;Where the front is now.
const take = () => queue[head++];Read, then move the front on. Nothing shifts.
console.log(take(), take());a b
console.log(queue.length - head);1
Your turn
Take from the end of the array, stack style.
const stack = [1, 2, 3]; const top = stack.();
Solve one with the tests running
The trap
queue.shift() looks like a queue and reindexes the whole array each time, so a loop over n items quietly costs n squared. On a small queue it does not matter; on a big one it is the bug.