A stack on an array

Picture a stack of plates in a kitchen. A clean plate goes on top, and plates are taken from the top too. The plate put down last is the first to go, and the bottom one waits until all the others are gone.

The Undo button in an editor works the same way. It first undoes the last action, then the one before it. Here a program needs the reverse of the order in which things were saved: what was saved later comes out earlier.

An ordinary array gives this order if elements are added and taken only at its end. Let's look at an editor's action history:

const history = [];
history.push("type");
history.push("bold");
history.push("delete");

console.log(history.pop()); // delete
console.log(history.pop()); // bold
console.log(history.join(" ")); // type

Let's go through the program line by line:

1. const history = [] creates an empty history.
2. Three push calls append actions to the end of the array: "type", "bold", "delete".
3. The first pop takes off the last action and prints delete.
4. The second pop takes off bold.
5. history.join(" ") prints what is left: type.

The top of a stack

A stack is a collection of values that are added and taken at one end only. That end is called the top. The value put on last is taken off first: "last in, first out".

In an array, the top is its end. A value is put on the stack with the push method and taken off with the pop method: it removes the last element and returns it. Neither method touches the other elements.

This is where the plate analogy ends. A real stack of plates will not let you take the bottom one, but an array will: history[0] reads the first element. What makes an array a stack is your rule of touching only its end.

Looking at the top

Sometimes you only need to look at the top without taking it off. The at method returns the element at an index and accepts negative indexes, which count from the end. So stack.at(-1) is the last element. It is the same as stack[stack.length - 1], only shorter.

const stack = [1, 2];
stack.push(3);
console.log(stack.at(-1), stack.length); // 3 3
console.log(stack.pop(), stack.at(-1)); // 3 2
console.log([].at(-1), [].pop()); // undefined undefined

Let's go through the output:

1. After push(3) the top is 3, and the stack holds three elements: the line prints 3 3.
2. pop() takes off and returns 3, and 2 becomes the top: it prints 3 2.
3. An empty array has no top: at(-1) and pop() return undefined, and there is no error.

Reading at(-1) leaves the stack as it is, the way looking at the top plate does not take it off. But pop shortens the stack by one element.

Matching brackets

A stack suits tasks where whatever opened last must close first. Brackets in an expression work this way: in "([])" the square bracket opened after the round one and closes before it. Interviewers often give the bracket check as a stack task.

The check goes through the string from left to right:

1. An opening bracket is put on the stack.
2. A closing bracket must pair with the top, and then the top is taken off.
3. When the string has ended, the stack must be empty.

For the string "([)]" the steps are these:

A closing bracket with no pair on top, including on an empty stack, means an error. If the string has ended and the stack is not empty, some bracket was left unclosed. For "([])" the check reaches the end with an empty stack: every bracket is closed.

Common mistake

People try to read the top with a negative index in square brackets:

const stack = ["(", "["];
console.log(stack[-1]); // ✗

There is no error, but the program prints undefined. Square brackets do not count from the end: to them, -1 is the name of a property the array lacks. The at method understands a negative index, and stack.at(-1) returns "[".

Key points

• A stack gives back first the value put on last; in an array, its top is the end.
• push puts a value on the top, and pop takes it off and returns it.
• at(-1) reads the top without taking it off; on an empty stack both it and pop return undefined.
• A negative index does not work in square brackets: stack[-1] gives undefined.