Stacks, Queues, and Deques

Introduction

Many programs must process data according to an order that is more specific than simply “first stored, first retrieved.” A browser may undo the most recent action, a printer may serve waiting jobs in arrival order, and a network application may temporarily hold messages until a consumer is ready. These situations are naturally modeled by stacks, queues, and deques.

A stack follows the last-in, first-out (LIFO) principle. A queue follows the first-in, first-out (FIFO) principle. A deque, or double-ended queue, permits insertion and removal at both ends. These structures are conceptually simple, but they support important applications in parsing, recursion, scheduling, buffering, graph traversal, and application development.

This chapter explains their abstract data types, implementations in Python and Java, performance characteristics, design choices, and practical uses.

Learning Objectives

By the end of this chapter, you should be able to:

1. Explain LIFO, FIFO, and double-ended access.
2. Distinguish abstract data types from their implementations.
3. Implement stacks, queues, and deques in Python and Java.
4. Analyze common operations using Big-O notation.
5. Apply stacks to parsing and undo operations.
6. Apply queues to scheduling, buffering, and breadth-first search.
7. Select an appropriate structure for a programming problem.
8. Identify implementation errors, limitations, and reliability concerns.

1. Abstract Data Types and Access Discipline

An abstract data type (ADT) specifies what operations are available and what those operations mean; it does not prescribe how the data is stored. A stack can be implemented with an array, dynamic array, linked list, or language library. The observable behavior should remain the same.

Stack ADT

A stack normally supports:

• push(x): place x on the top.
• pop(): remove and return the top item.
• peek() or top(): return the top item without removing it.
• is_empty(): test whether the stack contains no items.
• size(): return the number of items.

If the insertion sequence is A, B, C, then the first item removed is C, followed by B and A.

Queue ADT

A queue normally supports:

• enqueue(x): add x at the rear.
• dequeue(): remove and return the front item.
• front() or peek(): inspect the front item.
• is_empty() and size().

If A, B, and C arrive in that order, they leave in the order A, B, C.

Deque ADT

A deque supports operations at both ends:

• add_front(x) and add_rear(x)
• remove_front() and remove_rear()
• peek_front() and peek_rear()

A deque can behave as either a stack or a queue, depending on which operations a program uses.

2. Complexity and Correctness

For a well-designed implementation, stack insertion and removal occur at one end and take constant time:

Here, T(n) is the running time for an operation on a structure containing n items. The notation Θ(1) means that the operation takes bounded time independent of n, assuming that resizing or memory allocation is not being counted as a separate exceptional event.

For a queue, both enqueue and dequeue should also be Θ(1). A common error is to remove the first element of an array and shift every remaining element left. That operation takes Θ(n), so repeated removals can make a program unnecessarily slow. A circular array or a linked representation avoids this shifting.

A dynamic array may occasionally resize. If its capacity is doubled when full, an individual append can take Θ(n) during resizing, but over a long sequence the amortized cost per append is Θ(1). Amortized analysis averages the cost over a sequence while retaining the guarantee that the total cost is linear under the stated resizing policy.

The space requirement for n stored elements is generally Θ(n), excluding fixed object overhead.

3. Implementing Stacks

Python implementation

Python lists provide efficient append and removal at the right-hand end, making them suitable for stacks.

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at empty stack")
        return self._items[-1]

    def is_empty(self):
        return len(self._items) == 0

    def __len__(self):
        return len(self._items)

The choice of the right end is important. append and pop() operate at the end, whereas pop(0) removes from the beginning and generally requires shifting elements.

Python also supplies collections.deque, which supports efficient operations at both ends:

from collections import deque

stack = deque()
stack.append("A")
stack.append("B")
print(stack.pop())       # B

Java implementation

Java’s Deque<E> interface is commonly used as a stack. ArrayDeque<E> is usually preferable to the older Stack<E> class for ordinary single-threaded use.

import java.util.ArrayDeque;
import java.util.Deque;

Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
String item = stack.pop();       // B
String next = stack.peek();

ArrayDeque does not allow null elements. A program should use isEmpty() before pop() or peek() when empty access is possible. For concurrent programs, a thread-safe collection or an explicit synchronization strategy is required.

4. Implementing Queues

Python queues

The deque class is appropriate for a normal FIFO queue:

from collections import deque

queue = deque()
queue.append("job-1")
queue.append("job-2")
print(queue.popleft())    # job-1

Using a Python list and repeatedly calling pop(0) is usually a poor choice because elements must be shifted. For producer-consumer systems requiring synchronization, Python’s queue.Queue provides blocking and thread-safe operations.

Java queues

Java provides the Queue<E> interface and several implementations:

import java.util.ArrayDeque;
import java.util.Queue;

Queue<String> queue = new ArrayDeque<>();
queue.offer("job-1");
queue.offer("job-2");
String job = queue.poll();       // job-1

offer and poll are often convenient because they report failure with a value (false or null) rather than throwing an exception in bounded or empty situations. add and remove use exception-based failure behavior. A program must distinguish a legitimate null element from an empty result; ArrayDeque avoids this issue by rejecting null.

Circular queues

A fixed-size circular queue stores elements in an array and treats the end as connected to the beginning. Let capacity be the array capacity and front be the index of the next element to remove. The next insertion position can be calculated as:

The variable index is an array position from 0 through capacity − 1. The modulo operation returns the remainder after division and ensures wraparound. Correct designs also track either the current size or a distinction between full and empty states, because identical front and rear indices can otherwise represent both conditions.

5. Deques

A deque is useful when both recent and older items may need priority. Python’s collections.deque provides:

from collections import deque

d = deque([2, 3])
d.appendleft(1)   # [1, 2, 3]
d.append(4)       # [1, 2, 3, 4]
d.pop()           # 4
d.popleft()        # 1

In Java:

Deque<Integer> d = new ArrayDeque<>();
d.addFirst(2);
d.addLast(3);
d.removeFirst();
d.removeLast();

Deques support algorithms such as sliding-window processing. For example, a program can retain candidate maximum values for a moving range while removing obsolete values from the front and dominated values from the rear. This can reduce some window-processing tasks from quadratic time to linear time, although the detailed algorithm depends on the problem definition.

6. Application: Parsing and Expression Processing

Stacks are central to syntax processing because nested structures must close in the reverse order in which they open. Consider:

{ [ ( ) ] }

The opening symbols are {, [, (. The first closing symbol must match (, the most recently opened symbol. This is exactly LIFO behavior.

Balanced-delimiter algorithm

1. Create an empty stack.
2. Scan the input from left to right.
3. When an opening delimiter appears, push it.
4. When a closing delimiter appears, reject the input if the stack is empty; otherwise pop and verify the matching type.
5. At the end, accept only if the stack is empty.

If the input contains n characters, each character is pushed or popped at most once. Therefore the running time is Θ(n), and the additional space is O(n) in the worst case.

def balanced(text):
    matching = {')': '(', ']': '[', '}': '{'}
    stack = []

    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in matching:
            if not stack or stack.pop() != matching[ch]:
                return False
    return not stack

The algorithm validates delimiter nesting, not complete programming-language syntax. A compiler or interpreter must also handle tokens, strings, comments, operators, types, and grammar rules.

Stacks also support postfix evaluation, operator-precedence parsing, function-call management, and depth-first search. In expression evaluation, operands are pushed and operators pop the required operands, compute a result, and push that result back.

7. Application: Undo and Backtracking

An editor can store each completed user action on an undo stack. When the user selects Undo, the most recent action is removed and reversed. A second stack is commonly used for Redo:

• Normal action: push onto the undo stack and clear or update the redo stack.
• Undo: pop from undo, reverse the action, and push it onto redo.
• Redo: pop from redo, reapply the action, and push it onto undo.

A robust design stores commands with enough information to reverse them. For example, a deletion command might record the deleted text and its position, rather than merely recording the word “delete.”

Undo systems raise application-level questions. Should saving a file clear the history? How much memory may history consume? Are actions grouped, such as typing an entire word rather than each keystroke? These are product and usability decisions, but the underlying history mechanism is stack-based.

The same principle supports backtracking in maze solving, configuration search, and recursive problem solving. A stack records the current path and permits the program to return to the latest decision point when a choice fails.

8. Application: Scheduling and Buffering

A queue is appropriate when fairness is based on arrival order. Examples include print jobs, customer-service requests, tasks waiting for a worker, and messages waiting for a consumer.

A basic FIFO scheduler repeatedly removes the front task, processes it, and admits new tasks at the rear. If tasks have different priorities, pure FIFO may not be sufficient. A priority queue selects according to priority rather than arrival order. A round-robin scheduler uses a queue but returns an unfinished task to the rear after a time slice. Thus, “queue” describes an access discipline, while the scheduling policy determines how items are admitted, selected, and reinserted.

Buffering

A buffer temporarily absorbs a difference between production and consumption rates. A bounded queue is especially important because unlimited buffering can exhaust memory. If producers generate data faster than consumers can process it, a bounded queue must apply one of several policies:

• block producers until space is available;
• reject or drop new items;
• discard older items;
• apply backpressure to slow the producer.

The correct policy depends on whether data is disposable, ordered, safety-critical, or legally required to be retained. Logging, video streaming, payment processing, and sensor systems do not have identical requirements.

In concurrent applications, the queue must also provide safe coordination. A thread-safe queue generally protects updates to internal state and may support waiting until an item or capacity becomes available. Thread safety does not automatically guarantee fairness, bounded latency, or correct shutdown behavior.

9. Application: Breadth-First Search

Breadth-first search (BFS) explores a graph level by level. It uses a queue so that vertices discovered earlier are processed before vertices discovered later at the same distance.

def bfs(graph, start):
    visited = {start}
    distance = {start: 0}
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                distance[neighbor] = distance[vertex] + 1
                queue.append(neighbor)
    return distance

For a graph represented by adjacency lists, BFS takes:

where V is the number of vertices and E is the number of edges. The bound assumes that adjacency-list iteration and set membership are expected constant-time operations. The queue and visited set require O(V) additional space. For an unweighted graph, the resulting distance is the minimum number of edges from the start vertex to each reachable vertex. This shortest-path claim does not generally apply to weighted graphs; weighted problems require other algorithms such as Dijkstra’s algorithm under its assumptions.

10. Detailed Applied Case: A Help-Desk Service

Background

An organization receives technical-support requests through a web application. Each request contains an identifier, customer information, arrival time, category, and status. The service must preserve requests, assign them to available agents, and prevent memory from growing without limit.

Problem

A first implementation used a Python list and removed requests with pop(0). During peak periods, response time increased because removing the front element shifted the remaining elements. The system also silently discarded requests when a worker crashed, making operational auditing difficult.

Analysis

The normal work list is FIFO, so a deque is a better representation. However, the system also needs special handling for urgent security incidents. A single FIFO queue would not express this policy adequately. The design therefore separates ordinary requests from urgent requests or uses a documented priority mechanism.

The queue is bounded. If it reaches capacity, the service records an explicit failure event and applies a policy agreed with operations management. It does not silently overwrite requests. Each request receives a durable identifier and status transitions such as received, assigned, in_progress, resolved, and failed.

Approach and Solution

A worker removes a request using an atomic queue operation. Before processing, it records assignment. After successful completion, it records resolution. If processing fails, the request is either returned to the queue with a retry count or moved to a dead-letter queue for investigation. A retry limit prevents one defective request from circulating forever.

Python-like pseudocode is:

while service_is_running:
    request = work_queue.get()       # waits when empty
    try:
        record_status(request.id, "assigned")
        process(request)
        record_status(request.id, "resolved")
    except Exception as error:
        if request.retries < MAX_RETRIES:
            request.retries += 1
            work_queue.put(request)
        else:
            dead_letter_queue.put(request)
            record_status(request.id, "failed")
    finally:
        work_queue.task_done()

In production, exception handling, shutdown signaling, transaction boundaries, authentication, and durable storage must be designed explicitly. The example illustrates the queue discipline, not a complete service framework.

Outcome

Replacing front-removal from a list with deque-based operations removes the repeated-shifting bottleneck. Bounded capacity makes overload visible, while retry and dead-letter policies prevent silent data loss. The design also improves observability because every request has a traceable status history.

Learning Points

1. Select a structure based on access discipline, not familiarity.
2. Analyze the cost of the operations actually used.
3. Separate FIFO behavior from priority policy.
4. Treat overflow, failure, retry, and shutdown as part of the design.
5. Use durable records when business or regulatory requirements demand auditability.

11. Common Errors and Best Practices

Errors

• Removing from the front of a dynamic array repeatedly.
• Calling pop or dequeue without defining empty behavior.
• Confusing peek with removal.
• Mixing front and rear conventions in a circular queue.
• Failing to distinguish a full circular queue from an empty one.
• Reusing mutable objects in a queue without understanding aliasing.
• Assuming a queue is thread-safe because its operations look simple.
• Using a stack where fairness is required.
• Allowing unlimited retries or unlimited buffering.

Best practices

• Define invariants, such as “front refers to the next removable item.”
• Encapsulate operations behind a clear class or interface.
• Document behavior for empty, full, and shutdown states.
• Prefer library implementations that are tested and well documented.
• Measure latency, throughput, queue length, rejection rate, and retry count.
• Use bounded queues where uncontrolled growth could harm reliability.
• Keep security-sensitive or legally significant records durable and auditable.
• Test ordering, empty access, capacity limits, wraparound, concurrent access, and failure recovery.

12. Contemporary Development Considerations

Modern applications often connect queues to web services, event brokers, and distributed workers. A local in-memory queue is fast but loses data when the process terminates unless data is persisted elsewhere. Distributed messaging systems add durability, replication, partitioning, acknowledgements, and delivery semantics. These features introduce new concerns such as duplicate delivery, ordering within partitions, idempotent consumers, and eventual consistency.

Artificial intelligence systems also use queues for task submission, model inference requests, document processing, and rate control. A queue does not by itself make an AI system fair or safe. Designers must consider sensitive data, access control, retention, workload prioritization, and whether urgent or vulnerable-user requests could be systematically delayed. Technical ordering rules should therefore be reviewed alongside operational and ethical requirements.

Chapter Summary

Stacks, queues, and deques are abstract data types defined by access discipline. Stacks provide LIFO behavior and are effective for nested syntax, expression processing, undo history, recursion, and backtracking. Queues provide FIFO behavior and support fair task handling, buffering, producer-consumer coordination, and breadth-first search. Deques provide efficient access at both ends and can implement either a stack or a queue.

Efficient implementations perform end operations in Θ(1), while careless array shifting can create Θ(n) operations. Circular arrays, linked structures, dynamic arrays, and standard library collections each offer different trade-offs. Correct programs define empty and full behavior, preserve invariants, consider concurrency, and plan for overload and failure. In professional systems, data-structure selection must be connected to scheduling policy, durability, observability, security, and ethical handling of data.

Key Terms

Abstract data type: A specification of data operations and behavior independent of implementation.

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

Backtracking: Returning to a previous decision point when a current path fails.

Breadth-first search: Graph traversal that explores vertices level by level using a queue.

Buffer: Temporary storage that absorbs differences between production and consumption rates.

Circular queue: A queue implemented with wraparound positions in a fixed array.

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

FIFO: First-in, first-out ordering.

Front: The queue end from which an item is normally removed.

LIFO: Last-in, first-out ordering.

Overflow: An attempt to add to a full bounded structure.

Peek: Inspecting an item without removing it.

Priority queue: A queue-like structure that removes items according to priority.

Producer-consumer system: A system in which producers create items and consumers process them.

Queue: A FIFO abstract data type.

Stack: A LIFO abstract data type.

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

Wraparound: Moving from the final array position back to position zero.

Review Questions

5 Short Answer Questions

1. What is the defining access rule of a stack?
2. Why is pop(0) usually inefficient for implementing a queue in Python?
3. What is the purpose of a queue’s front position?
4. State one application of a deque.
5. What is the difference between peek and pop?

5 Long Answer Questions

1. Explain how a circular queue works and why modulo arithmetic is useful.
2. Compare array-based and linked implementations of queues, including performance and memory considerations.
3. Describe how two stacks can implement undo and redo operations.
4. Explain the balanced-delimiter algorithm and analyze its time and space requirements.
5. Discuss why bounded queues and explicit overflow policies are important in production systems.

3 Analytical / Application Questions

1. A program processes jobs in arrival order, but urgent security jobs must be handled before ordinary jobs. Should it use a simple FIFO queue, a priority queue, or separate queues? Justify your design and explain how fairness could be preserved.
2. Design a BFS procedure for finding the minimum number of connections between two users in an unweighted social network. Identify the roles of the queue, visited set, and distance record.
3. A circular queue has capacity 5, with three elements stored and the front at index 3. Describe the next insertion positions as elements are added and explain which variables are needed to distinguish full from empty states.

Multiple Choice Questions with Answers

Question 1

Which access discipline does a stack follow?

A. First-in, first-out

B. Last-in, first-out

C. Random-in, first-out

D. Priority-in, first-out

Correct Answer: B. Last-in, first-out

Question 2

Which Python operation is appropriate for removing the oldest item from a deque named q?

A. q.pop()

B. q.remove_oldest()

C. q.popleft()

D. q.delete(0)

Correct Answer: C. q.popleft()

Question 3

What is the typical time complexity of enqueue and dequeue in a correctly implemented circular queue?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: A. Θ(1)

Question 4

Why are stacks useful for checking balanced parentheses?

A. They sort symbols alphabetically

B. They match each closing symbol with the most recent opening symbol

C. They remove symbols in arrival order

D. They prevent all syntax errors

Correct Answer: B. They match each closing symbol with the most recent opening symbol

Question 5

Which structure is most directly used by breadth-first search?

A. Queue

B. Stack

C. Heap only

D. Hash table only

Correct Answer: A. Queue

Question 6

If a queue receives A, then B, then C, in what order should a FIFO queue remove them?

A. C, B, A

B. A, C, B

C. B, A, C

D. A, B, C

Correct Answer: D. A, B, C

Question 7

What is the main danger of repeatedly using list.pop(0) as a queue operation in Python?

A. It reverses the queue

B. It usually shifts remaining elements

C. It automatically duplicates elements

D. It prevents insertion at the rear

Correct Answer: B. It usually shifts remaining elements

Question 8

Which operation inspects the top stack item without removing it?

A. push

B. enqueue

C. peek

D. dequeue

Correct Answer: C. peek

Question 9

For a graph represented with adjacency lists, what is the usual BFS time complexity in terms of vertices V and edges E?

A. O(V + E)

B. O(VE)

C. O(V²E)

D. O(log V)

Correct Answer: A. O(V + E)

Question 10

Which policy is especially relevant when a bounded queue becomes full?

A. Ignore capacity permanently

B. Choose whether to block, reject, or drop items

C. Convert every item into a stack

D. Guarantee zero waiting time

Correct Answer: B. Choose whether to block, reject, or drop items