Stacks, Queues, Deques, and Recursion

Introduction

Many computational processes require data to be accessed in an order determined by its history. A browser’s Back button, an operating-system scheduler, a printer queue, an expression evaluator, and a recursive function all depend on disciplined ways of inserting and removing items. Stacks, queues, and deques are linear abstract data types (ADTs) designed for these patterns.

A stack is governed by last-in, first-out (LIFO) access. A queue is governed by first-in, first-out (FIFO) access. A deque, or double-ended queue, permits insertion and deletion at both ends. Recursion is a problem-solving technique in which a function invokes itself; its execution is supported by a run-time call stack. These structures are simple, but they support parsing, algorithm design, buffering, scheduling, search, memory management, and software-system control flow.

Learning Objectives

After completing this chapter, you should be able to:

• define and compare stacks, queues, and deques as ADTs;
• implement these structures using arrays and linked nodes;
• analyze their time and space complexity;
• use stacks for expression conversion, evaluation, parsing, and backtracking;
• use queues for scheduling, breadth-first search, and buffering;
• explain circular queues and priority queues;
• distinguish recursion from iteration and trace recursive calls;
• identify base cases, recurrence structure, and stack-overflow risks;
• select an appropriate linear ADT for a practical application.

1. Abstract Data Types and Linear Access Policies

An ADT specifies values and permitted operations without prescribing a representation. A stack may be implemented with an array or linked list, but the user of the ADT should rely only on operations such as push and pop.

A structure is empty when it contains no elements. Removing from an empty structure is an underflow error. A bounded array implementation may also experience overflow when an insertion is attempted while all allocated positions are occupied. Robust software either reports these conditions, resizes the structure, or defines an explicit recovery policy.

2. Stacks

A stack has one accessible end, called the top. Its essential operations are:

• push(x): place x on the top;
• pop(): remove and return the top element;
• peek() or top(): return the top element without removing it;
• isEmpty(): test whether the stack has no elements.

If the sequence push(A), push(B), push(C) is followed by two pops, the returned values are C and then B. The element A remains in the stack.

2.1 Array-based implementation

An array stack stores elements in consecutive positions. A variable top can represent the index of the last occupied position. If the stack is empty, top = -1; otherwise, the number of elements is top + 1.

push(x):
    if top = capacity - 1:
        report overflow or resize
    top ← top + 1
    A[top] ← x

pop():
    if top = -1:
        report underflow
    x ← A[top]
    top ← top - 1
    return x

Both operations take Θ(1) time when resizing is not required. If a dynamic array doubles its capacity when full, an individual resizing insertion can take Θ(n), but a sequence of n insertions has amortized Θ(1) time per insertion. The additional array space is Θ(n).

2.2 Linked implementation

A linked stack stores a pointer to the top node. Each node contains an element and a link to the next node. Insertion and deletion occur at the head, so both are Θ(1) time and no contiguous memory is required. The trade-off is an additional pointer per element and possible allocation overhead.

2.3 Applications of stacks

Stacks are appropriate whenever the most recent unfinished item must be processed first:

• undo and redo histories;
• browser navigation histories;
• balancing delimiters in source code;
• depth-first search and backtracking;
• conversion and evaluation of expressions;
• management of nested procedure calls.

3. Expression Processing and Parsing

Expressions contain operands, operators, and delimiters. Common notations are:

• infix: A + B, where the operator is between operands;
• prefix: + A B, where the operator precedes operands;
• postfix: A B +, where the operator follows operands.

Postfix notation is convenient for stack evaluation because it does not require parentheses or precedence decisions during evaluation.

3.1 Operator precedence and associativity

A typical precedence hierarchy is multiplication and division above addition and subtraction. Exponentiation is often above multiplication and is commonly right-associative. The exact rules depend on the programming language; an implementation must document them.

For example, A + B × C means A + (B × C), whereas (A + B) × C gives the addition priority through parentheses. Associativity determines how operators of equal precedence group. Subtraction is normally left-associative: A − B − C means (A − B) − C.

3.2 Infix-to-postfix conversion

The shunting-yard method scans tokens from left to right. Operands are emitted immediately. Operators are placed on a stack, but operators of higher precedence—or equal precedence when the incoming operator is left-associative—are first removed from the stack and emitted. An opening parenthesis is pushed; a closing parenthesis causes operators to be emitted until the matching opening parenthesis is removed.

for each token t:
    if t is an operand:
        output t
    else if t is '(':
        push t
    else if t is ')':
        while top ≠ '(':
            output pop()
        pop '('
    else if t is an operator:
        while stack is not empty and top is an operator and
              (precedence(top) > precedence(t) or
              precedence(top) = precedence(t) and t is left-associative):
            output pop()
        push t
while stack is not empty:
    if pop() is a parenthesis:
        report mismatched parentheses
    else output the operator

For A + B × C, the postfix result is A B C × +. For (A + B) × C, it is A B + C ×. With n tokens, conversion is Θ(n) time because each token is pushed and popped at most a constant number of times, and auxiliary space is O(n).

3.3 Postfix evaluation

To evaluate postfix notation, scan from left to right. Push operands. When an operator appears, pop the right operand first, then the left operand, compute the operation, and push the result.

Consider 8 3 2 × +. The steps are:

1. Push 8: [8].
2. Push 3: [8, 3].
3. Push 2: [8, 3, 2].
4. Apply ×: pop 2 and 3; push 6, giving [8, 6].
5. Apply +: pop 6 and 8; push 14.

The result is 14. Operand order is essential for non-commutative operations: for subtraction, if right = pop() and left = pop(), the result is left − right.

A reliable evaluator validates that enough operands exist for every operator and that exactly one value remains at the end. Division by zero, malformed tokens, integer overflow, and unsupported operators must also be handled.

3.4 Delimiter matching

A parser can use a stack to check delimiters such as parentheses, brackets, and braces. Opening delimiters are pushed. A closing delimiter must match the most recent opening delimiter. Any unmatched delimiter or nonempty stack at the end indicates a syntax error. This method runs in Θ(n) time and uses O(n) auxiliary space in the worst case.

4. Queues

A queue has two distinguished ends: insertion occurs at the rear, and removal occurs at the front. Its central rule is FIFO. If jobs enter in the order J1, J2, J3, they leave in that order.

Operations include:

• enqueue(x): add x at the rear;
• dequeue(): remove and return the front item;
• front(): inspect the front item;
• isEmpty(): test whether the queue is empty.

A linked queue maintains pointers to both the front and rear. Enqueue attaches a node at the rear; dequeue removes the node at the front. With both pointers, each operation is Θ(1).

4.1 The circular array queue

A simple array queue can waste space after repeated dequeues if the front moves only to the right. A circular queue treats the array as wrapping around. Let front identify the first element, size be the number of stored elements, and capacity be the array length. The next physical position is calculated as:

Here, i is a valid array index and mod returns the remainder. The rear position, when the queue is nonempty, is:

The formulas assume capacity > 0, indices begin at zero, and 0 ≤ size ≤ capacity. Enqueue places the item at (front + size) mod capacity and increments size; dequeue returns A[front], advances front to (front + 1) mod capacity, and decrements size. Both operations are Θ(1).

4.2 Priority queues

A priority queue removes the item with the best priority rather than the oldest item. “Best” may mean smallest numerical key, largest key, earliest deadline, or another defined ordering. A binary heap commonly supports insertion and removal of the minimum or maximum in O(log n), with inspection in O(1). Priority queues are not ordinary FIFO queues and should not be substituted for them without a clear policy.

4.3 Queue applications

Queues model situations in which arrival order matters:

• print spooling and job scheduling;
• network packets and input buffers;
• breadth-first search (BFS);
• customer-service systems;
• producer–consumer pipelines;
• event simulation.

In BFS, the start vertex is enqueued, then the algorithm repeatedly dequeues a vertex and enqueues each undiscovered neighbor. Because vertices are processed by increasing distance from the start, BFS finds shortest paths in an unweighted graph. With adjacency lists, BFS takes Θ(V + E) time, where V is the number of vertices and E is the number of edges, and uses O(V) auxiliary space.

5. Deques

A deque supports insertion and deletion at both the front and rear. Typical operations are addFront, addRear, removeFront, removeRear, and corresponding inspection operations. A doubly linked list is a natural implementation: each node has prev and next links, and front and rear pointers permit all end operations in Θ(1) time.

A circular array can also implement a deque. The front index moves backward using (front − 1 + capacity) mod capacity, while the rear index moves forward using modular arithmetic. Boundary conditions must distinguish full and empty states, commonly by storing size explicitly.

Deques are useful for:

• sliding-window maximum and minimum algorithms;
• palindrome testing;
• work-stealing schedulers;
• algorithms requiring controlled access to both ends.

A deque can behave as a stack by using one end only, or as a queue by inserting at one end and removing at the other.

6. Recursion and the Call Stack

A recursive algorithm solves a problem by reducing it to one or more smaller instances of the same problem. A correct recursive design requires:

1. a base case, which can be solved directly;
2. a recursive case, which makes progress toward the base case;
3. correct combination of the smaller result with the current result.

For factorial, the mathematical definition for nonnegative integer n is:

The recursive implementation is:

factorial(n):
    if n = 0:
        return 1
    return n × factorial(n − 1)

The definition assumes n is a nonnegative integer. For factorial(4), calls are nested as factorial(4), factorial(3), factorial(2), factorial(1), and factorial(0). The returns then occur in reverse order. The call stack stores each suspended invocation, including parameters, local variables, and a return location.

6.1 Recursion analysis

If a recursive function makes one call on input of size n − 1 and performs constant additional work, its running time satisfies:

where c is a constant and T(0) is constant. Therefore T(n) is Θ(n), and the maximum call-stack depth is Θ(n).

A naive recursive Fibonacci function illustrates a different pattern:

fib(n):
    if n ≤ 1: return n
    return fib(n − 1) + fib(n − 2)

Its recurrence is approximately:

which grows exponentially in n. The recursion depth is only Θ(n), but the number of calls is much larger. Memoization stores previously computed results and reduces the time to Θ(n), with Θ(n) additional storage. An iterative solution can achieve Θ(n) time and O(1) additional space when only the preceding two values are needed.

6.2 Recursion and iteration

Recursion often expresses tree traversal, divide-and-conquer, backtracking, and grammars clearly. Iteration may use less memory and avoid call-stack overflow. Any recursion can in principle be simulated with an explicit stack, but the programmer must store the state that the language normally places in activation records.

Tail recursion occurs when the recursive call is the final operation. Some languages optimize tail calls, but this is language-dependent; programmers must not assume that tail recursion always uses constant stack space.

7. Backtracking

Backtracking explores a sequence of decisions and reverses the most recent decision when it leads to failure. A stack can store decision states. Examples include maze solving, permutation generation, constraint satisfaction, and depth-first search.

A generic pattern is:

search(state):
    if state is a complete solution:
        report state
    else:
        for each legal choice c:
            apply c
            search(new state)
            undo c

The undo operation restores the state before the choice. This is not merely a programming detail: failing to restore state can cause later branches to inherit invalid decisions. Backtracking may have exponential worst-case time because it can explore many combinations, although pruning rules can substantially improve practical performance.

8. Applied Case: A Web-Service Request Pipeline

Background

Consider an illustrative online bookstore. Customers submit requests to search the catalogue, reserve stock, and pay for orders. The service must preserve request order for ordinary work, prioritize urgent operational tasks, and parse user-entered search expressions safely.

Problem

A single shared list was used for all requests. Workers sometimes removed the newest request instead of the oldest, urgent maintenance work waited behind normal requests, and malformed search expressions caused inconsistent errors.

Analysis

The ordinary request stream requires FIFO behavior, so a queue is appropriate. Urgent maintenance tasks require a priority queue with a documented priority policy. Search expressions require tokenization, delimiter validation, precedence handling, and possibly postfix evaluation. A stack is appropriate for these parsing stages.

Approach and solution

1. A thread-safe FIFO queue receives ordinary requests.
2. A bounded circular buffer limits memory consumption for incoming messages. When full, the system applies an explicit policy: reject, block the producer, or apply controlled back-pressure.
3. A priority queue handles operational tasks. Priority must not be based on an unvalidated user field; otherwise, users could promote routine requests.
4. The parser pushes opening delimiters and operators onto separate logical stacks or a unified parser stack, validates matching delimiters, and produces a structured expression.
5. Worker tasks use bounded recursion or iterative traversal when processing potentially user-controlled data, preventing denial of service through excessive nesting.

Outcome

The design makes ordering guarantees explicit. Queue length, waiting time, rejection count, and parser-error rate can be monitored. The system can also distinguish a full buffer from an empty buffer and report both conditions correctly.

Learning points

The correct structure follows the access policy, not the other way around. FIFO fairness does not guarantee low latency when requests are long-running; priority improves urgency but can starve low-priority work. Bounded buffers protect memory but require a visible overload policy. Parsing must validate input rather than assuming that delimiters and operators are well formed.

9. Correctness, Performance, and Engineering Practice

When implementing these ADTs, define invariants. For a queue with size, front, and capacity, a useful invariant is 0 ≤ size ≤ capacity; when size = 0, no element is logically present, regardless of stale array values. For a stack, −1 ≤ top < capacity in a fixed array implementation. In a linked structure, an empty structure should have both end pointers set to null.

Use encapsulation so clients cannot change internal indices or links directly. Test empty, one-element, full, wraparound, repeated insertion/removal, and error cases. For expression processing, test nested parentheses, operator associativity, missing operands, extra operands, mismatched delimiters, and division by zero.

In concurrent systems, an ordinary stack or queue is not automatically thread-safe. Synchronization, lock-free algorithms, or concurrent-library implementations may be required. Blocking queues additionally define what happens when producers or consumers must wait. Such behavior is part of the ADT’s operational contract.

Security is relevant whenever input controls depth or volume. Deeply nested expressions can exhaust a call stack; unlimited queues can exhaust memory; priority manipulation can undermine fairness. Systems should use limits, validation, authentication where appropriate, monitoring, and predictable failure behavior.

Contemporary Relevance

Stacks and queues remain fundamental beneath modern language runtimes, operating systems, web servers, databases, compilers, and distributed systems. Event loops commonly maintain queues of pending work. Message brokers use queues with acknowledgements, retries, visibility timeouts, and dead-letter handling. AI and data-processing pipelines use queues to decouple producers from consumers and smooth bursts of work. These advanced systems add persistence, concurrency, and delivery semantics, but their basic ordering models still derive from the linear ADTs studied here.

Chapter Summary

Stacks, queues, and deques are linear ADTs distinguished primarily by their access policies. Stacks provide LIFO access and support parsing, expression evaluation, undo operations, backtracking, and call-stack management. Queues provide FIFO access and support scheduling, buffering, event handling, and BFS. Circular arrays avoid wasted queue space through modular indexing. Deques provide access at both ends and can simulate either a stack or a queue.

Expression conversion and evaluation demonstrate how stacks enforce precedence and reverse nested dependencies. Recursion uses the run-time call stack and requires a base case, progress toward that case, and correct result construction. Its time and space costs must be analyzed rather than assumed to be efficient. Backtracking combines recursion or an explicit stack with state restoration.

Good implementations specify invariants, complexity, capacity behavior, error handling, concurrency guarantees, and security limits. The best ADT is selected from the required access policy and application constraints.

Key Terms

Stack: A LIFO abstract data type with insertion and removal at one end.

Queue: A FIFO abstract data type with insertion at the rear and removal at the front.

Deque: A double-ended queue supporting insertion and deletion at both ends.

LIFO: Last-in, first-out access order.

FIFO: First-in, first-out access order.

Top: The accessible end of a stack.

Underflow: An attempt to remove an item from an empty structure.

Overflow: An insertion attempt into a full bounded structure.

Circular queue: An array queue whose indices wrap around to reuse positions.

Priority queue: A queue that removes items according to priority rather than arrival time.

Infix notation: Expression notation with operators between operands.

Postfix notation: Expression notation with operators after operands.

Precedence: The rule determining which operators are processed first.

Associativity: The rule determining grouping of operators with equal precedence.

Parsing: Analyzing tokens according to a syntactic structure or grammar.

Recursion: A method in which a function solves a problem through smaller calls to itself.

Base case: A recursive condition solved without another recursive call.

Call stack: Run-time storage for active function invocations.

Backtracking: Exploring choices and undoing the latest choice when it fails.

Amortized analysis: Analysis of average cost over a sequence of operations.

Review Questions

Short Answer Questions

1. What access rule distinguishes a stack from a queue?
2. Why does a circular queue use modular arithmetic?
3. What two conditions are necessary for a correct recursive function?
4. Why must postfix evaluation pop the right operand before the left operand?
5. State one advantage and one disadvantage of a linked stack.

Long Answer Questions

1. Explain array-based and linked implementations of stacks, including their time and space trade-offs.
2. Describe the shunting-yard method for converting infix expressions to postfix notation.
3. Explain how BFS uses a queue and why it finds shortest paths in an unweighted graph.
4. Compare recursion and iteration with respect to clarity, time, and memory.
5. Explain how a deque can implement both stack and queue behavior.

Analytical / Application Questions

1. Design a data structure for a printer system that supports ordinary jobs, urgent jobs, and cancellation. Justify each ADT and discuss fairness.
2. Trace the stack contents while converting (A + B) × (C − D) to postfix notation, and give the final postfix expression.
3. A server receives messages faster than workers can process them. Analyze how a bounded circular queue, back-pressure, and a priority policy could be combined without allowing unlimited memory growth.

Multiple Choice Questions with Answers

Question 1

Which operation order demonstrates LIFO behavior?

A. Enqueue A, enqueue B, dequeue A

B. Push A, push B, pop B

C. Add A at the rear, remove A at the front

D. Insert A, insert B, remove the oldest item

Correct Answer: B. Push A, push B, pop B

Question 2

What is the postfix form of the infix expression A + B × C, using conventional precedence?

A. A B + C ×

B. A B C + ×

C. A B C × +

D. + A × B C

Correct Answer: C. A B C × +

Question 3

In postfix evaluation, why is the first popped operand usually called the right operand?

A. Stacks always store values in descending order

B. The most recently pushed operand appears on the right of the operator

C. The left operand is never stored on the stack

D. Postfix notation reverses every operand

Correct Answer: B. The most recently pushed operand appears on the right of the operator

Question 4

Which structure is most directly suited to breadth-first search?

A. Queue

B. Stack

C. Deque used only at the rear

D. Priority queue ordered by reverse insertion time

Correct Answer: A. Queue

Question 5

A circular array has capacity 8 and an index i = 7. What is next(i) = (i + 1) mod 8?

A. 0

B. 1

C. 7

D. 8

Correct Answer: A. 0

Question 6

Which condition is essential for a recursive algorithm to terminate, assuming finite input?

A. It must use a global variable

B. Every call must create two more calls

C. A base case must be reached through progress toward it

D. It must use an array rather than a linked list

Correct Answer: C. A base case must be reached through progress toward it

Question 7

What is the worst-case auxiliary space of delimiter matching for an input of n opening delimiters followed by n closing delimiters?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: C. Θ(n)

Question 8

Which deque operation pattern behaves as a FIFO queue?

A. Insert and remove at the same end

B. Insert at the rear and remove at the front

C. Insert at the front and remove at the front

D. Remove from both ends simultaneously

Correct Answer: B. Insert at the rear and remove at the front

Question 9

For a linked queue to perform enqueue in Θ(1) time, which pointers are normally maintained?

A. Only a pointer to the middle node

B. Only a pointer to the front node

C. Pointers to both the front and rear nodes

D. A pointer to every possible array index

Correct Answer: C. Pointers to both the front and rear nodes

Question 10

What is a principal risk of naive recursive Fibonacci computation?

A. It cannot have a base case

B. It performs exponentially many repeated calls

C. It always uses constant time

D. It requires FIFO removal

Correct Answer: B. It performs exponentially many repeated calls