208: Stacks, Queues, Deques, Circular Buffers, and Expression Processing

Learning outcomes

By the end of this lesson, you can:

explain and apply stack in a realistic implementation;
explain and apply queue in a realistic implementation;
explain and apply deque in a realistic implementation;
explain and apply circular buffer in a realistic implementation;
explain and apply expression stacks in a realistic implementation.

These outcomes are about selecting and using the right processing order, not simply reciting five definitions. You should be able to describe the invariant that makes an implementation correct, identify the boundary cases that can break it, and explain the runtime and storage trade-offs to another developer.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where the same kind of constraint appeared. Perhaps work had to be undone in reverse order, items had to be processed in arrival order, or a fixed amount of memory had to be reused. The example does not need to use the formal data-structure name.

The purpose of that retrieval is to connect the vocabulary to a design decision. In an interview-sized problem and in a production data-processing problem, the useful question is not “Which template have I memorized?” It is “What must happen first, what must remain true, and what happens when the input or dependency is not well behaved?”

Terminology

Stack: A stack supports push/pop/peek in LIFO order: the last item added is the first item removed. That ordering models nested structure, undo histories, depth-first search (DFS), parsing, monotonic patterns, and call-stack-like behavior.
Queue: A queue processes items in FIFO order: the first item added is the first item removed. Queues are a natural fit for breadth-first search (BFS), scheduling, and buffering.
Deque: A deque, or double-ended queue, supports adding and removing at both ends in O(1). It is useful for sliding-window maxima, 0-1 BFS, and algorithms that maintain candidates at the front and back.
Circular buffer: A fixed-capacity queue can reuse an array by moving its head and tail with indexes taken modulo the capacity. It does not need to shift the remaining elements after a removal.
Expression stacks: Parentheses matching, postfix evaluation, and infix parsing exploit LIFO order. An expression is processed according to grammar rules, while a stack holds the operators or partial results that still need to be resolved.
Min/max stacks: A stack can store auxiliary extrema or paired metadata so that the current minimum or maximum remains available in O(1). Duplicate extrema require deliberate handling; removing one copy must not discard another equal value.

Mental model

Treat Stacks, Queues, Deques, Circular Buffers, and Expression Processing as a design problem with observable inputs, outputs, invariants, and failure modes. These structures control processing order: LIFO, FIFO, or access from both ends. The order is the contract. The implementation is only correct if every operation preserves that contract, including operations on an empty structure and operations at capacity.

In JavaScript, a quick implementation can accidentally destroy the intended complexity. Repeatedly calling shift() on a large array, for example, may require the remaining elements to be moved, so an operation that looks like queue removal is not necessarily O(1). A circular buffer or a queue with a moving read index makes the cost model explicit. The same principle applies to expression processing: if precedence and associativity are left to scattered conditions, the code may appear to work until a nested or mixed-operator expression exposes the missing rule.

A strong implementation makes assumptions visible, narrows uncertainty at boundaries, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to prove why the design is safe. Empty input, malformed expressions, duplicate values, full buffers, and dependency failures are not afterthoughts; they are where the contract becomes observable.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call. First state what must remain true. Then choose the mechanism that enforces it. If the requirement is FIFO processing, name the oldest available item as the next item to remove. If the requirement is a fixed-capacity buffer, decide what “full” means before writing enqueue. That small step prevents many off-by-one and accidental-complexity bugs.

Deep dive

1. Stack

When the newest unfinished item must be handled before older unfinished items, a stack gives that behavior directly. It supports push, pop, and peek in LIFO order and models nested structure, undo, DFS, parsing, monotonic patterns, and call-stack-like behavior. The top element is the only element a normal stack exposes for removal, which is precisely what makes nested work easy to represent.

For example, opening delimiters can be pushed as they are encountered and checked against the next closing delimiter. An undo history can push each completed action and pop the most recent action when the user requests an undo. A DFS can push the next nodes to visit. In each case, the useful property is the same: the most recently deferred work is resolved first.

There is a practical distinction between a stack's abstract behavior and its implementation. An array can implement a stack efficiently when the top is at the end, because push and pop do not require shifting the other values. The implementation still needs a defined result for pop or peek on an empty stack, and callers need to understand whether that result is a sentinel, undefined, or an error.

Decision rule: Use a stack deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

2. Queue

When items must be handled in arrival order, use a queue. A queue processes FIFO order and powers BFS, scheduling, and buffering. The first item accepted is the next item eligible for removal, provided it has not already been removed. That rule is often more important than the particular class or array used underneath.

In JavaScript, avoid repeated shift() for large queues; use an index or deque implementation. A moving index can leave removed values in the backing array until compaction, so the time complexity and memory-retention behavior should both be considered. A deque implementation may provide cleaner front removal, while a simple index is often enough for a bounded traversal. The right choice depends on expected size and lifetime rather than on syntax alone.

For BFS, the queue invariant is that the next node to process is at the front, and newly discovered nodes are appended at the back. For a scheduler, the queue may also need a policy for cancellation, retries, priority, or concurrency. Those additional policies should not be smuggled into an allegedly plain FIFO abstraction.

Decision rule: Use a queue deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

3. Deque

A deque supports both ends in O(1) and underpins sliding-window maxima, 0-1 BFS, and algorithms that need front/back candidates. The two-ended contract matters because some algorithms discard stale or inferior candidates from one end while adding new candidates at the other. A one-ended queue would force unnecessary work or obscure the algorithm's invariant.

In a sliding-window maximum, for instance, the deque can keep candidate indexes in decreasing value order. Before adding a new candidate, values that can no longer become the maximum are removed from the back; before reading the answer, indexes outside the current window are removed from the front. The deque is not merely storing every value in arrival order. It is maintaining a smaller set of candidates whose ordering makes the next maximum available at the front.

The implementation must define what both ends mean and how empty operations behave. If the structure is used with indexes, the caller must also keep the window bounds consistent with those indexes. That is where a correct-looking deque can still produce an incorrect algorithm.

Decision rule: Use a deque deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

4. Circular buffer

When a queue has a known capacity and items can be stored in reusable slots, a circular buffer avoids growing and shifting a linear array. Fixed-capacity queues can reuse an array with head/tail modulo capacity. After either index reaches the end of the physical array, modulo arithmetic wraps it to the beginning.

Full and empty state needs an explicit convention such as a stored size or one unused slot. Without that convention, head === tail could mean either “nothing is stored” or “every slot is occupied.” A size field uses all available slots and makes those states distinguishable. The one-unused-slot convention avoids a size field but reduces usable capacity by one. Either is valid if enqueue, dequeue, and capacity checks use the same rule.

The key invariant is that the head identifies the next item to remove, the tail identifies the next slot to write, and the chosen state convention accurately describes how many items are present. A full buffer also requires a policy: reject the new item, overwrite the oldest item, or block until space is available. That policy is part of the API contract, not an implementation detail.

Decision rule: Use a circular buffer deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

5. Expression stacks

Expressions become difficult when tokens arrive in one order but must be evaluated in another. Parentheses matching, postfix evaluation, and infix parsing exploit LIFO order. Opening delimiters wait for their matching closing delimiters; partial results wait until an operator can consume them; operators wait until precedence permits them to be applied.

Operator precedence and associativity belong to the grammar contract, not to ad-hoc conditions. Multiplication must not be treated like addition merely because both are binary operators, and right-associative operators cannot always be reduced using the same comparison as left-associative operators. A parser or evaluator should make these rules explicit and should reject malformed input rather than quietly inventing a result.

Decision rule: Use expression stacks deliberately when they make the contract or invariant easier to prove. If they only reduce typing while hiding an assumption, prefer the more explicit design.

6. Min/max stacks

A normal stack gives constant-time access to the top but not necessarily to the smallest or largest item. A min-stack or max-stack stores auxiliary extrema or paired metadata so the current min/max remains O(1). The auxiliary value is updated on push and restored on pop, so a query does not need to scan the entire stack.

There is one subtle detail worth making explicit: duplicate handling. If two equal values are the minimum, popping one must leave the other equal value available. Store an extremum for each stack entry, or store the extremum with a count, rather than keeping only one unqualified “current minimum.” The same reasoning applies to maximums.

Decision rule: Use min/max stacks deliberately when they make the contract or invariant easier to prove. If they only reduce typing while hiding an assumption, prefer the more explicit design.

Worked example

Consider an interview-sized problem and a production data-processing problem. In both cases, the learner must reason from constraints rather than memorize a template. Start by writing the requirement in one sentence, list the input and output contracts, and identify which of the concepts above owns each failure mode.

The important move is separation. Parsing or validation belongs at the boundary; domain rules belong in the domain/service layer; persistence rules belong in the database or repository; presentation rules belong in the client. A stack, queue, or buffer can help implement one of those responsibilities, but the data structure does not decide which layer owns the business rule. Mixing these concerns makes a happy-path demo look shorter and makes edge cases much harder to reason about.

Here is a deliberately small example. Its purpose is to show where an invariant should be stated, not to pretend that a maximum scan is one of the structures covered by this lesson:

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

The code has a contract that needs discussion. It returns 0 for an empty array, and that may or may not be a valid domain result. It also behaves differently from a true maximum for an all-negative input because answer starts at 0. The example therefore demonstrates a useful review habit: inspect the initial state and test it against the stated input domain before choosing an implementation. If empty input is invalid, reject it at the boundary. If negative numbers are valid, initialize from the first value or define the result as optional.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For each case, state which layer detects the problem and what the caller observes. With a queue, this might mean checking an empty dequeue and a retry that could enqueue duplicate work. With an expression evaluator, it might mean an unmatched parenthesis or an invalid token. With a production service, a dependency failure should produce a defined error or retry behavior rather than silently changing the data-structure invariant. This is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. A queue may preserve FIFO order within one process while still duplicating work after a retry. A circular buffer may be correct at its configured capacity while dropping data if its overflow policy was never made explicit. A parser may work for valid examples while accepting malformed input in a way that creates unsafe downstream behavior.

Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence. For a queue, measure backlog, wait time, throughput, and failure counts. For an expression processor, record rejected input without logging sensitive content. For a buffer, make capacity and overflow visible in configuration and metrics. The data structure is part of a system; its local complexity guarantee does not by itself guarantee system-level reliability.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted.

Guided lab

Build an O(1) queue without shift, a circular buffer, and a valid-parentheses evaluator. Then implement a min-stack and test duplicate minima plus empty operations. For each implementation, write down what an empty operation returns or throws, whether capacity is bounded, and which operation is expected to remain O(1). Those choices turn an informal exercise into a testable contract.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

For the queue, compare the moving-index approach with repeated shift() and inspect both runtime and retained memory. For the circular buffer, test the transition from empty to full, wraparound, and full-to-empty after removals. For parentheses, test nesting, mismatched types, premature closing delimiters, and an unclosed opener. For the min-stack, push the same minimum twice and pop it one time before checking the result again.

Edge cases and failure modes

Stack: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Queue: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Deque: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Circular buffer: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Expression stacks: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.

“Absence” may mean an empty operation, missing input, or no available candidate, depending on the API. “Ordering” means checking that the promised LIFO, FIFO, or two-ended behavior survives every transition. For a circular buffer, the smallest credible size includes capacity zero or one if the API permits it; for expression stacks, malformed tokens and mismatched delimiters must not be confused with a valid expression that happens to evaluate to zero.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.

For debugging, reproduce the smallest failing case, inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. In a stack, log or inspect the top and the operation sequence. In a queue or deque, inspect head, tail, size, and the next item to be removed. In a circular buffer, check the modulo calculation and the full/empty convention. In expression processing, inspect the token stream and the operator or value stack at the first unexpected token.

If the observed runtime is worse than expected, do not infer the cause from the data-structure name. Check whether array shifting, compaction, unbounded growth, duplicate retries, or logging is dominating the work. The debugging target is the first point where the stated invariant or resource assumption becomes false.

Interview questions

What problem does Stack solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Queue solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Deque solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Circular buffer solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Expression stacks solve, and what trade-off or failure mode would make you choose a different approach?

Answer each question with more than a definition. Name the processing-order invariant, give one concrete use, state the expected operation cost, and mention one boundary or failure policy. That answer demonstrates design judgment rather than vocabulary recall.

Checkpoint

Without notes, explain Stacks, Queues, Deques, Circular Buffers, and Expression Processing to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code.

Before you finish, check that you can explain why a queue implemented with repeated shift() may not meet an O(1) requirement, how a circular buffer distinguishes full from empty, why expression operators need precedence and associativity rules, and how a min-stack preserves duplicate minima. If any answer is vague, return to the relevant invariant and write a test that would expose the gap.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.