Stacks, Queues, and Deques
Three restricted-access structures — last-in-first-out, first-in-first-out, and both ends at once — and the real problems each one solves cleanly.
What you'll learn
- Implement a stack and a queue using an array, with correct O(1) operations
- Choose stack vs. queue vs. deque based on the access pattern a problem requires
- Use a stack to solve a classic matching/nesting problem (balanced parentheses)
Prerequisites
Explanation
A stack is a LIFO structure — last in, first out — supporting exactly two core operations: push (add to the top) and pop (remove from the top), both O(1) when backed by a dynamic array's end (never its front, which would be O(n) per the arrays lesson). The mental model is a physical stack of plates: you can only add or remove from the top. Stacks are the natural fit whenever "undo the most recent thing" or "match the most recently opened thing" is the actual requirement — function call stacks, undo history, and balanced-parentheses checking (this lesson's independent exercise) all reduce to exactly that pattern.
A queue is FIFO — first in, first out — supporting enqueue (add to the back) and dequeue (remove from the front). This is the natural fit for "process things in the order they arrived" — a print queue, a task queue, or breadth-first search (covered in a later module) all need this ordering specifically. A naive queue backed by a plain array is a trap: Array.prototype.shift() (remove from the front) is O(n), because removing the first element requires shifting every remaining element left by one — exactly the array-insertion cost from two lessons ago, mirrored for removal. A queue with genuinely O(1) operations needs either a linked list (front removal is O(1), as covered last lesson) or a circular buffer (an array with wrap-around head/tail indices, avoiding any shifting).
A deque (double-ended queue) generalizes both: it supports O(1) insertion and removal at both ends. It subsumes a stack (use only one end) and a queue (add at one end, remove at the other) as special cases, which is why a deque is often the practical default when you're not sure yet whether you'll need stack-like or queue-like access — implemented well (a doubly linked list, or a circular buffer with growth), it gives you both without commitment.
Example
A stack (LIFO, via array push/pop) and a naive queue (FIFO, via array push/shift) -- with a note on the queue's real cost.
// Stack: push/pop on the END of an array -- both O(1).
const stack = [];
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3 -- last in, first out
// Queue: push on the end, shift from the FRONT.
const queue = [];
queue.push("a");
queue.push("b");
queue.push("c");
console.log(queue.shift()); // "a" -- first in, first out
// BUT: shift() is O(n) on a plain array -- every remaining element shifts left by one.
// A genuinely O(1) queue needs a linked list or circular buffer, not a plain array's front.Try it yourself
Use the stack to reverse the order of ['a','b','c'] by pushing all three then popping them one at a time.
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Guided exercise
Guided exercise
Write reverseWithStack(items) that reverses an array using ONLY push/pop (model a real stack -- no Array.prototype.reverse()).
Checks: reverses a multi-element array correctly · handles an empty array · handles a single-element array
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Independent exercise
Independent exercise
Write isBalanced(expression) using a stack to check whether every (), [], and {} in the string is properly matched and nested (e.g. '([{}])' is balanced, '([)]' is NOT -- brackets close in the wrong order). Ignore all other characters. An empty string is balanced.
Checks: correctly identifies a properly nested, balanced expression · correctly rejects out-of-order closing brackets · an empty string is balanced · rejects an unclosed opening bracket · rejects a closing bracket with no matching opener · ignores non-bracket characters entirely
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Common mistakes
- Implementing a queue with Array.prototype.shift() for dequeue and assuming it's O(1) -- it's O(n), since every remaining element must shift left; a real O(1) queue needs a linked list or circular buffer.
- Forgetting to check whether the stack is empty before popping when validating balanced brackets -- popping an empty stack (an unexpected closer) must be treated as invalid input, not ignored or crashed on.
- Forgetting the final 'stack must be empty' check in a balanced-brackets solution -- without it, an unclosed opener like '(' incorrectly reports as balanced, since nothing ever failed during the scan.
Knowledge check
Takeaway
A stack's push/pop on one end and a queue's add-one-end/remove-other-end are both O(1) when implemented correctly (a queue needs a linked list or circular buffer, not a plain array's front) — pick the structure whose access order actually matches the problem, rather than defaulting to whichever is more familiar.
Summary
Stacks are LIFO (push/pop, O(1) on an array's end). Queues are FIFO (O(1) only with a linked list or circular buffer, since array shift() is O(n)). Deques support O(1) at both ends and subsume both. A stack is the standard tool for matching/nesting problems like balanced brackets.
References
Your notes
Notes save automatically.
Finished this lesson?
Mark it complete to track your progress and schedule a future review.
AI tutor
The optional AI tutor isn't enabled in this deployment. All lessons, exercises, quizzes, and search work fully without it.