Stacks

Checking that the brackets in {[()()]} pair up correctly takes one stack and 8 pushes and pops, one for each bracket.

Last in, first out

Think of a pile of plates. You put a clean plate on top, and when you need one you take it from the top. The plate you added last is the first one out. A stack is a data structure with exactly that rule, called last in, first out (LIFO). It offers two main operations: push puts a value on top, and pop removes the value on top and gives it back. Many stacks also offer peek, which looks at the top without removing it.

In MIT's 6.006 notes the stack is a special case of the sequence interface: insert last(x) and delete last(). That already tells you how to build one. Put the values in a dynamic array and treat the end of the array as the top. In the last unit the end was the cheap end, so push and pop each cost 1 step (amortized, because of the occasional copy). The size of the stack makes no difference. Popping from a stack of 3 values or of 3 million values is the same single step.

const stack = [];
stack.push(4);
stack.push(8);
stack.push(5);
console.log(stack.pop());           // 5, the last one pushed
console.log(stack[stack.length - 1]); // peek: 8
console.log(stack.length);          // 2

Checking brackets

A classic use for a stack is checking that brackets are balanced, which every code editor and compiler does. Read the text from left to right. Each opening bracket, (, [ or {, is pushed. Each closing bracket must match the opener on top of the stack: if it does, pop that opener; if the stack is empty or the top is a different kind, the string is not balanced. At the end the stack must be empty, or some opener was never closed.

Try the strings in the lab. {[()()]} needs 4 pushes and 4 pops, 8 steps, and ends with an empty stack. ([)] fails at the third character: the ) arrives while [ is on top. (() reads to the end with one ( left over. Why does a stack fit this job? Brackets nest, and the most recently opened one must be the first to close. That is last in, first out.

Where else stacks appear

• The call stack. When function a calls b and b calls c, the computer pushes a record for each call. When c returns, its record is popped and b continues where it stopped. Infinite recursion fills this stack, which is the "stack overflow" error.
• Undo. An editor pushes each change. Undo pops the most recent change and reverses it.
• Back button. A browser pushes each page you leave; Back pops the last one.
• Depth-first search. The algorithms course used a stack to go as deep as possible in a maze before backing up.