Stacks and Queues Explained
How stacks (last in, first out) and queues (first in, first out) work, what their operations cost, and how to build both correctly in JavaScript.
· Updated · 8 min read
Stacks and queues are lists with a restriction on where items enter and leave. The restriction is the point: it makes the order of processing predictable, and many algorithms depend on that order.
Stack: last in, first out
A stack works like a pile of plates. You add to the top and remove from the top, so the most recently added item is the first to come off. This is called LIFO: last in, first out.
| Operation | Meaning | Cost |
|---|---|---|
| push | Add an item to the top | O(1) |
| pop | Remove and return the top item | O(1) |
| peek | Read the top item without removing it | O(1) |
A JavaScript array already behaves as a stack, because push and pop both work at the end in constant time.
const stack = [];
stack.push("a");
stack.push("b");
stack.push("c");
stack[stack.length - 1]; // "c" (peek)
stack.pop(); // "c"
stack.pop(); // "b"A stack, step by step
| Operation | Returns | Stack afterwards (top on the right) |
|---|---|---|
| push a | a | |
| push b | a, b | |
| push c | a, b, c | |
| peek | c | a, b, c |
| pop | c | a, b |
| push d | a, b, d | |
| pop | d | a, b |
| pop | b | a |
Items come off in the reverse of the order they went on. That reversal is what a stack is for.
Where stacks are used
- Function calls. The call stack records which function to return to. A function that calls itself forever causes a stack overflow.
- Undo. Each action is pushed; undo pops the most recent one.
- Matching pairs. Checking that brackets are balanced is the classic example:
function isBalanced(text) {
const closingFor = { "(": ")", "[": "]", "{": "}" };
const stack = [];
for (const ch of text) {
if (ch in closingFor) {
stack.push(closingFor[ch]);
} else if (ch === ")" || ch === "]" || ch === "}") {
if (stack.pop() !== ch) return false;
}
}
return stack.length === 0;
}
isBalanced("{[()]}"); // true
isBalanced("([)]"); // falseEach opening bracket pushes the closing bracket it expects. Each closing bracket must match the most recent expectation, which is exactly what pop returns.
The same idea, with more explanation and a Python version, is the Valid Parentheses problem.
Undo and redo with two stacks
Undo is one stack. Adding redo takes a second: whatever is undone moves across to it, and redo moves it back.
class UndoHistory {
constructor() {
this.done = [];
this.undone = [];
}
record(action) {
this.done.push(action);
this.undone = []; // a new action clears redo
}
undo() {
const action = this.done.pop();
if (action !== undefined) this.undone.push(action);
return action;
}
redo() {
const action = this.undone.pop();
if (action !== undefined) this.done.push(action);
return action;
}
}After typing A, B and C, then pressing undo twice, done holds A and undone holds C and B, with B on top. Redo brings back B first, the most recently undone action, which is the behaviour people expect. Recording a new action empties undone, because the old future no longer applies.
Queue: first in, first out
A queue works like a line at a counter. Items join at the back and leave from the front, so the oldest item is processed first. This is FIFO: first in, first out.
| Operation | Meaning | Cost |
|---|---|---|
| enqueue | Add an item at the back | O(1) |
| dequeue | Remove and return the front item | O(1) |
| peek | Read the front item without removing it | O(1) |
A queue, step by step
| Operation | Returns | Queue afterwards (front on the left) |
|---|---|---|
| enqueue a | a | |
| enqueue b | a, b | |
| enqueue c | a, b, c | |
| peek | a | a, b, c |
| dequeue | a | b, c |
| enqueue d | b, c, d | |
| dequeue | b | c, d |
| dequeue | c | d |
Items leave in the order they arrived. Compare this with the stack table: the same operations in the same order give a different sequence of results.
The JavaScript trap
Using push to enqueue and shift to dequeue works, but shift is O(n): it moves every remaining item down by one position. For a few hundred items nobody will notice. For a large queue inside a loop, it turns an O(n) algorithm into O(n²).
A simple fix is to keep an index for the front instead of removing items:
class Queue {
constructor() {
this.items = [];
this.head = 0;
}
enqueue(value) {
this.items.push(value);
}
dequeue() {
if (this.head === this.items.length) return undefined;
const value = this.items[this.head];
this.head += 1;
return value;
}
get size() {
return this.items.length - this.head;
}
}Both operations are now O(1). The trade-off is that dequeued items stay in memory until the queue itself is discarded, which is fine for a queue that lives for the length of one algorithm. A long-lived queue is better built on a linked list.
Where queues are used
- Breadth-first search. Exploring a tree or graph level by level relies on a queue.
- Task scheduling. Jobs, print requests and messages are handled in arrival order.
- Buffering. Data that arrives faster than it can be processed waits in a queue.
What to build them on
| Built on | Add | Remove | Good for |
|---|---|---|---|
Stack on an array (push, pop) |
O(1) | O(1) | Almost every stack |
Queue on an array (push, shift) |
O(1) | O(n) | Small queues only |
| Queue on an array with a front index | O(1) | O(1) | A queue used for one algorithm |
| Queue on a linked list | O(1) | O(1) | A queue that lives a long time |
The last row is built in full in Linked Lists Explained.
The same search with a stack and with a queue
The clearest way to see the difference is to run one piece of code both ways. This function visits every node of a tree. The only thing that changes is which waiting node it takes next.
function visitOrder(root, useQueue) {
const waiting = [root];
const visited = [];
while (waiting.length > 0) {
// A queue takes the oldest waiting node; a stack takes the newest.
const node = useQueue ? waiting.shift() : waiting.pop();
visited.push(node.value);
// For the stack, add children in reverse so the leftmost is taken first.
const children = useQueue ? node.children : [...node.children].reverse();
waiting.push(...children);
}
return visited;
}On this tree:
A
/ | \
B C D
/ \ \
E F G| Structure | Order visited | Name |
|---|---|---|
| Queue | A, B, C, D, E, F, G | Breadth-first: level by level |
| Stack | A, B, E, F, C, D, G | Depth-first: all the way down one branch, then the next |
A queue finishes everything near the start before going further, so it finds the shortest route to something. A stack goes deep first, which suits exploring every possibility or working through nested structures. (shift is used here to keep the example short. It is fine for a tree of seven nodes.)
Relatives worth knowing
| Structure | Rule | Where it appears |
|---|---|---|
| Deque (double-ended queue) | Add and remove at both ends | Sliding Window Maximum |
| Priority queue | The most important item leaves first, whatever order they arrived in | Scheduling, shortest paths. Usually built on a heap |
| Circular buffer | A fixed-size queue that reuses its space | Keyboard input, audio and video streaming |
| Monotonic stack | A stack kept in sorted order | Daily Temperatures |
Choosing between them
Ask which item should be handled next:
- the most recent one: use a stack;
- the oldest one: use a queue.
Common mistakes
- Popping from an empty stack. In JavaScript
popreturnsundefinedrather than failing, which can hide a bug. Check the length when emptiness is possible. - Using
shifton large arrays. See the trap above. - Mixing up the ends. Decide once which end is the top or the front, and use the same end everywhere.
- Checking the stack only at the end. When matching pairs, a closing item with nothing open is an error at that moment, not something to discover later.
- Forgetting what is left over. Items still on a stack or in a queue when the input ends usually mean something: unclosed brackets, unprocessed jobs.
Practise
The stack pattern explains how to recognise these problems. Then:
- Valid Parentheses: the matching-pairs stack.
- Daily Temperatures: a stack of items waiting for an answer.
- Largest Rectangle in Histogram: the same stack, pushed further.
- Sliding Window Maximum: a queue that removes from both ends.
Summary
- A stack removes the newest item first (LIFO). A queue removes the oldest first (FIFO).
- Both add and remove in O(1) when built correctly.
- A JavaScript array is a ready-made stack. It is a slow queue, because
shiftis O(n). - For a queue, keep a front index or use a linked list.
- Stacks suit nesting, undo and going deep. Queues suit fairness, arrival order and going level by level.
- Decide which end is which once, and check for empty before removing.