What a stack is
A stack is a collection where the last item added is the first one removed. This rule is called LIFO, for last in, first out. A pile of plates is the usual picture: you put a plate on top, and you take a plate from the top. You never pull one from the middle.
A stack supports a few operations, all at one end called the top:
- push adds an item on top;
- pop removes the top item and gives it back;
- peek looks at the top item without removing it;
- is empty tells whether there is anything left.
Each of these takes O(1) time, because they only touch the top.
A stack in TypeScript
TypeScript has no separate stack type. An ordinary array works, because the array methods push and pop both work at the end. The last element of the array is the top of the stack.
const stack: number[] = [];
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack); // [ 10, 20, 30 ]
console.log(stack[stack.length - 1]); // 30 (peek)
console.log(stack.pop()); // 30
console.log(stack.pop(), stack.pop()); // 20 10
console.log(stack.length === 0); // true
The annotation number[] on the first line matters. Without it, TypeScript can't tell what an empty array literal will hold. The annotation is only for the compiler: it is erased when the code becomes JavaScript, and it doesn't stop a wrong value from getting in at run time.
The four operations map to array code like this:
| Stack operation | TypeScript |
|---|---|
| push | stack.push(x) |
| pop | stack.pop() |
| peek | stack[stack.length - 1] |
| is empty | stack.length === 0 |
Push and pop are the cheap, end-of-array operations. Avoid shift and unshift for a stack, which work at the front: they shift every other element, so they are slower on large arrays, and they don't match the push and pop end.
Gotchas in TypeScript
Popping an empty stack
Calling pop() on an empty array doesn't throw. It returns undefined. Reading the top by index does the same:
const empty: number[] = [];
console.log(empty.pop()); // undefined
console.log(empty[empty.length - 1]); // undefined
Because of this, check stack.length before you use a popped value. With strict null checking turned on, TypeScript types pop() as number | undefined, and using the result as a plain number is a compiler error. When you have already checked that the stack isn't empty, the non-null assertion stack.pop()! tells the compiler the value is there. It is a promise to the compiler only. It checks nothing and converts nothing at run time, so use it only after a real check.
Peeking is not popping
Reading stack[stack.length - 1] leaves the stack unchanged. A common bug is to call pop() when you only meant to look, which loses the item.
Push can take several values
stack.push(1, 2) pushes both values in order, so 2 ends up on top. push also returns the new length, not the stack, so don't chain it.
The stack is shared by reference
If you pass a stack array to a function, the function can push and pop on the very same array. Changes are visible to the caller. That is useful for helper functions, and a surprise if you forgot about it.
Where stacks are used
Stacks fit any problem where the most recent unfinished thing must be handled first. In this chapter you will meet three typical patterns:
- Matching pairs. Opening brackets wait on a stack until their closing bracket arrives, and the most recent opening bracket is always the one that must be closed first.
- Waiting for an answer. Items that don't have an answer yet stay on the stack. When a later item provides the answer, the items it resolves are popped. Finding the next greater element for each number works this way.
- Undoing and reversing. Reading characters into a stack and popping them out gives them back in reverse order:
const letters: string[] = [];
for (const ch of "abc") {
letters.push(ch);
}
let reversed = "";
while (letters.length > 0) {
reversed += letters.pop();
}
console.log(reversed); // cba
Function calls follow the same rule. Each call waits on the program's call stack until the call it made returns. That is why a recursion with no stopping point eventually fails with a "Maximum call stack size exceeded" error, which is the stack running out of room.
Key takeaways
- A stack is last in, first out: you only add and remove at the top.
- In TypeScript, use an array:
pushto add,popto remove,stack[stack.length - 1]to peek andstack.length === 0to test for empty. - Annotate an empty stack, as in
const stack: number[] = [];, so TypeScript knows its element type. pop()on an empty array returnsundefined, so check the length first.- Every stack operation is
O(1), which is why stack-based solutions often run in linear time overall.