Stacks, Queues, Deques, and Priority Queues

Introduction

Many programs must manage data according to an ordering rule rather than by arbitrary position. A browser’s Back command revisits the most recently viewed page; a printer serves waiting jobs; a network buffer temporarily stores arriving packets; and a hospital triage system serves urgent cases before routine cases. These behaviours are naturally modelled by restricted linear data structures.

A stack follows last-in, first-out (LIFO) order. A queue follows first-in, first-out (FIFO) order. A deque permits insertion and removal at both ends. A priority queue removes the item with the highest priority rather than necessarily the oldest item. Each structure can be implemented in Java and Python, and each is useful in parsing, scheduling, buffering, undo systems, simulations, and service systems.

This chapter develops their abstract data types, array- and linked-list implementations, complexity, practical uses, limitations, and professional design considerations.

Learning Objectives

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

• explain LIFO, FIFO, double-ended, and priority-based ordering;
• implement stacks, queues, circular queues, deques, and binary-heap priority queues;
• select an appropriate structure for parsing, scheduling, buffering, and simulation;
• analyse time and space complexity;
• identify overflow, underflow, resizing, and stability issues;
• use Java and Python library implementations safely and effectively.

1. Abstract Data Types and Ordering Policies

An abstract data type (ADT) specifies what operations mean, not how they are represented. A stack commonly provides push, pop, peek or top, isEmpty, and size. A queue provides enqueue, dequeue, front, isEmpty, and size. Implementations may use arrays, linked nodes, or library classes while preserving the same externally visible behaviour.

The choice of structure is an algorithmic decision. A queue is not merely an array with two indices, and a priority queue is not simply a sorted list: each has a specific ordering contract.

2. Stacks

2.1 Concept and operations

A stack has one logically accessible end called the top. If items A, B, and C are pushed in that order, C is removed first, followed by B, then A.

The principal operations are:

• push(x): place x on the top;
• pop(): remove and return the top item;
• peek(): return the top item without removing it;
• isEmpty(): test whether no item is present.

For a correctly implemented stack, push and pop normally take Θ(1) time. A dynamically resizing array can occasionally take Θ(n) for one operation, but its amortized cost is Θ(1), meaning the average cost over a long sequence is constant per operation.

2.2 Array-based stack

An array implementation stores elements from index 0 through top - 1. The variable top is the number of stored elements, so the next insertion occurs at index top.

If the capacity is C, overflow occurs when an insertion is attempted with top = C in a fixed-capacity stack. Underflow occurs when pop or peek is requested while top = 0.

A dynamically growing stack commonly doubles its capacity when full. If the capacities are 1, 2, 4, 8, and so on, then a sequence of n pushes performs fewer than 2n total element copies across all resizing events. Thus the total copying cost is O(n), and the amortized cost per push is O(1), although an individual resizing push is O(n).

2.3 Java implementation

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

public class StackExample {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("A");
        stack.push("B");
        System.out.println(stack.peek()); // B
        System.out.println(stack.pop());  // B
    }
}

Java’s ArrayDeque is generally preferable to the legacy Stack class for ordinary stack operations. It does not permit null elements, and it is not synchronized; concurrent access requires an appropriate concurrent design.

2.4 Python implementation

stack = []
stack.append("A")       # push
stack.append("B")
print(stack[-1])         # peek: B
print(stack.pop())       # pop: B

Appending to and removing from the end of a Python list are amortized O(1). Removing from index 0 is O(n), so a list should not normally be used as a queue by repeatedly calling pop(0).

2.5 Applications of stacks

Undo operations. Each completed action can be pushed onto a history stack. Undo pops the latest action and applies its inverse. A second stack can support redo: undo moves an action from the undo stack to the redo stack, while a new action usually clears the redo history.

Delimiter matching. In source code, an opening delimiter such as (, [, or { is pushed. A closing delimiter must match the top opening delimiter. A mismatch or a non-empty stack at the end indicates invalid nesting.

Expression conversion and evaluation. Stacks support conversion between infix, postfix, and prefix notation and evaluate postfix expressions by pushing operands and applying an operator to the required number of top operands.

Depth-first search. A graph traversal can use an explicit stack, avoiding the call-stack limitations of recursive depth-first search.

2.6 Worked example: delimiter matching

Consider {[()]}. Scan from left to right:

The expression is balanced because every closing delimiter matches the most recent unmatched opening delimiter and the final stack is empty. The algorithm is O(n) time and O(n) auxiliary space in the worst case, where n is the number of characters examined.

3. Queues

3.1 FIFO behaviour

A queue has a front from which items are removed and a rear at which items are inserted. If A, B, and C are enqueued in that order, they are dequeued as A, B, and C.

A queue’s operations are:

• enqueue(x): insert x at the rear;
• dequeue(): remove and return the front item;
• front(): inspect the front item;
• isEmpty() and size().

A queue models fairness when service order is based on arrival order. However, real systems may use priorities, ageing, batching, or separate queues, so FIFO should not be assumed without examining requirements.

3.2 Linked queue

A linked queue maintains references to both front and rear. Enqueue creates a node after the rear; dequeue removes the front node. Both operations are Θ(1), including when the queue contains one item, provided the empty-state transitions update both references correctly.

3.3 Circular array queue

A fixed array can implement a queue without shifting elements. The front and rear positions wrap around using modular arithmetic:

Here, i is an array index and C is the array capacity. The result is always an index from 0 through C − 1.

A robust design stores front and size. The rear insertion index is:

The queue is empty when size = 0 and full when size = C. On enqueue, store at rear, then increase size. On dequeue, read at front, advance front using next(front), and decrease size. Both operations are O(1).

Using only front and rear indices is also possible, but then the implementation must distinguish an empty queue from a full queue, often by reserving one slot or maintaining an additional Boolean or count.

3.4 Java queue example

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

Queue<String> customers = new ArrayDeque<>();
customers.offer("A");
customers.offer("B");
System.out.println(customers.peek()); // A
System.out.println(customers.poll()); // A

offer and poll are often preferred when failure should be represented by a return value rather than an exception. add and remove may throw exceptions for capacity or emptiness in bounded implementations.

3.5 Python queue example

from collections import deque

customers = deque()
customers.append("A")
customers.append("B")
print(customers[0])       # front: A
print(customers.popleft())  # A

collections.deque supports O(1) append and removal at both ends. Indexing near the middle is not its intended strength.

4. Deques

A deque (double-ended queue) permits insertion and removal at both the front and rear. Typical operations are addFirst, addLast, removeFirst, removeLast, peekFirst, and peekLast.

A deque can act as a stack by using one end only, or as a queue by inserting at one end and removing at the other. Its flexibility makes it useful for:

• sliding-window algorithms;
• palindrome testing;
• task scheduling with work stealing;
• breadth-first search variants;
• maintaining candidates for monotonic queues.

Java’s ArrayDeque and Python’s collections.deque provide efficient end operations. A deque is not automatically thread-safe, and concurrent producer-consumer systems should use suitable blocking or concurrent queues.

Example: palindrome testing

To test whether a string is a palindrome, place its characters in a deque. Repeatedly compare and remove the first and last characters. A mismatch proves the string is not a palindrome. If all pairs match, it is a palindrome. For a string of length n, the time is O(n) and auxiliary space is O(n), unless a different in-place strategy is available.

5. Priority Queues and Binary Heaps

5.1 Priority ordering

A priority queue stores entries with priorities. Removal returns the entry with the smallest priority in a min-priority queue or the largest priority in a max-priority queue. If two entries have equal priority, their relative order is not automatically guaranteed; stable behaviour requires an explicit tie-breaking rule.

Priority queues support:

• insert(x, p);
• peekBest();
• removeBest();
• sometimes changePriority or remove.

A common implementation is a binary heap. A min-heap satisfies the heap-order property: every parent’s key is less than or equal to the keys of its children. The complete-tree shape is stored compactly in an array.

For zero-based indexing, the relationships are:

Here, i is an array index. These relationships depend on zero-based storage; one-based implementations use different expressions.

5.2 Heap operations

Insertion. Append the new item at the next available leaf and repeatedly swap it with its parent while it has a smaller key. This is called sift-up or bubble-up. The height of a complete binary tree with n nodes is Θ(log n), so insertion is O(log n).

Removal of the minimum. Save the root, move the final element to the root, reduce the logical size, and repeatedly swap it with its smaller child while the heap property is violated. This is sift-down and costs O(log n).

Peek. The minimum is at the root and is available in O(1).

Build-heap. Starting from the last internal node and sifting down each node constructs a heap in O(n), not O(n log n). The lower levels contain many nodes but require little movement; the total height-weighted work is linear.

5.3 Java priority queue

import java.util.PriorityQueue;

PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.offer(7);
numbers.offer(2);
numbers.offer(5);
System.out.println(numbers.poll()); // 2

Java’s default PriorityQueue is a min-priority queue. A comparator can reverse the order or implement a domain-specific policy. The class is not a stable priority queue, and iteration does not produce sorted order; repeated removal does.

For a record with urgency and arrival sequence, an explicit comparator can use urgency first and sequence number second. This makes tie-breaking deterministic and can support fairness.

5.4 Python heap implementation

Python’s heapq implements a min-heap over a list.

import heapq

jobs = []
heapq.heappush(jobs, (2, "routine"))
heapq.heappush(jobs, (1, "urgent"))
print(heapq.heappop(jobs))  # (1, 'urgent')

Tuple comparison uses subsequent fields when priorities are equal. If payload objects are not mutually comparable, include a unique sequence number:

import heapq
from itertools import count

counter = count()
jobs = []
heapq.heappush(jobs, (1, next(counter), "urgent"))

The sequence number gives deterministic first-in order among equal priorities, provided all entries use the same counter.

6. Complexity Comparison

The table gives asymptotic bounds for standard implementations. Constants, memory locality, resizing policy, and workload distribution can affect practical performance. A heap is efficient for repeatedly obtaining the best item, but it is not a fully sorted collection and does not support efficient arbitrary search by default.

7. Applied Case: A Multi-Level Service Centre

Background

Consider an illustrative university IT service centre. Students submit requests through a portal. Critical outages should be handled before routine password-reset requests, while requests of equal urgency should generally be served in arrival order.

Problem

A simple FIFO queue delays urgent incidents behind many routine requests. A single priority queue improves urgency handling but may create starvation if new urgent jobs continually arrive.

Analysis

Each request can contain:

• a priority level, where a smaller number means greater urgency;
• an arrival sequence number;
• a timestamp and estimated service duration;
• privacy-sensitive student information.

The scheduling key can be represented conceptually as (priority, sequence). A min-heap then removes the lowest-priority-number request, breaking ties by earliest sequence. To reduce starvation, the system can apply ageing, periodically improving the effective priority of waiting jobs. Ageing must be documented because it changes the service policy.

Approach and solution

The portal places requests into a priority queue. Worker processes repeatedly remove the best request, mark it as in progress, and record completion. A separate deque may hold recently failed requests for controlled retry, while a bounded queue buffers incoming events during short processing bursts.

The service must not rely solely on an in-memory data structure. Requests should be durably stored, authenticated, access-controlled, and recoverable after failure. Queue entries should have unique identifiers so that retries do not accidentally create duplicate service actions.

Outcome

Urgent incidents are handled quickly, equal-priority requests are treated predictably, and bounded buffering prevents unlimited memory growth. Monitoring can measure queue length, waiting time, service time, abandonment, and the proportion of requests exceeding service-level targets.

Learning points

The data structure expresses policy, but policy also requires governance. Priority values, tie-breaking, ageing, failure recovery, privacy, and auditability are system requirements rather than implementation details.

8. Buffering, Scheduling, and Simulation

Buffers and back-pressure

A queue often separates a producer from a consumer operating at different rates. If arrivals temporarily exceed service capacity, the queue grows. A bounded queue provides a capacity limit and forces a policy when full: reject, block the producer, overwrite old data, or apply back-pressure. The correct choice depends on whether data is disposable, loss-sensitive, or safety-critical.

Event simulation

Discrete-event simulations use a priority queue ordered by event time. The earliest event is removed, its effects are applied, and newly generated events are inserted. If two events have equal times, a sequence number or domain rule must define deterministic order. A simulation must distinguish simulated time from wall-clock time; the priority queue orders events by the former.

Scheduling

A FIFO queue represents simple first-come service. A priority queue represents urgency or shortest-job policies. A deque can support work-stealing systems in which a worker takes tasks from one end of its local deque while another worker steals from the opposite end. These policies have different fairness and throughput properties.

9. Correctness, Errors, and Defensive Design

Underflow and overflow

Underflow is an attempt to remove from an empty structure. APIs should define whether this returns a sentinel, returns null or None, or raises an exception. Ambiguous sentinel values are dangerous when the stored domain can contain the same value.

Overflow may mean a fixed array is full or a bounded queue has reached capacity. Dynamic structures reduce capacity failures but do not eliminate memory limits. Production systems should define limits and failure handling rather than allowing uncontrolled growth.

Invariants

Useful invariants include:

• a stack’s top equals its element count;
• a queue’s size remains between 0 and capacity;
• an empty linked queue has both front and rear set to null;
• a heap has complete-tree shape and satisfies parent-order relationships;
• every deque operation preserves the order of untouched elements.

Assertions and unit tests should check these invariants after normal, boundary, and failure operations.

Concurrency

Ordinary array deques are not automatically safe for multiple producers and consumers. A check-then-act sequence such as “if not empty, then remove” may fail when another thread changes the structure between the two actions. Use synchronized, blocking, lock-free, or actor-based structures appropriate to the environment. Do not add locks casually without considering contention, deadlock, visibility, and interruption.

Security and privacy

Queues may contain credentials, personal records, or confidential messages. Limit access, avoid logging sensitive payloads, erase or overwrite data where required by the environment, and define retention policies. Priority fields can encode discriminatory decisions; their policy should be explainable, reviewable, and monitored for unintended effects.

10. Best Practices

1. Select the structure from the required ordering policy, not from familiarity.
2. Prefer standard, tested library implementations unless learning or special constraints justify a custom one.
3. Document empty, full, tie-breaking, and failure behaviour.
4. Use deque for efficient two-ended operations rather than repeatedly shifting a list.
5. Use a heap when repeated best-item removal matters; do not assume heap iteration is sorted.
6. Add stable sequence numbers when equal-priority order matters.
7. Bound buffers in production systems and define back-pressure or loss policies.
8. Test empty, singleton, full, wraparound, duplicate-priority, and large-input cases.
9. Measure waiting time and memory usage, not only nominal Big-O complexity.
10. Treat concurrency, recovery, privacy, and auditability as part of the design.

Chapter Summary

Stacks enforce LIFO ordering and are central to undo systems, delimiter matching, expression processing, and depth-first search. Queues enforce FIFO ordering and model fair service, buffering, and breadth-first search. Circular arrays provide O(1) queue operations without shifting elements, while linked queues provide flexible growth. Deques support efficient insertion and removal at both ends and can act as either stacks or queues. Priority queues remove entries according to a priority policy; binary heaps provide O(1) peek and O(log n) insertion and removal, with O(n) heap construction.

Correct implementations depend on clearly defined invariants, empty and full behaviour, tie-breaking rules, and capacity policies. Professional systems also require concurrency control, back-pressure, fault recovery, monitoring, privacy protection, and fair scheduling. The data structure is therefore both a computational mechanism and an expression of system policy.

Key Terms

Stack: A linear ADT that removes the most recently inserted item first.

LIFO: Last-in, first-out ordering.

Queue: A linear ADT that removes the earliest inserted item first.

FIFO: First-in, first-out ordering.

Deque: A double-ended queue supporting operations at both ends.

Priority queue: An ADT that removes the item with the best priority.

Top: The accessible end of a stack.

Front: The removal end of a queue.

Rear: The insertion end of a queue.

Underflow: An attempted removal from an empty structure.

Overflow: An attempted insertion into a full fixed-capacity structure.

Circular queue: An array queue whose indices wrap around the array boundary.

Heap: A complete-tree structure satisfying a parent-child ordering property.

Min-heap: A heap whose root contains the smallest key.

Sift-up: Restoring heap order by moving an item toward the root.

Sift-down: Restoring heap order by moving an item toward the leaves.

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

Back-pressure: A mechanism that slows or limits producers when consumers cannot keep up.

Ageing: Gradually improving a waiting item’s effective priority to reduce starvation.

Review Questions

Short Answer Questions

1. What ordering rule does a stack implement?
2. Why is removing index 0 repeatedly from a Python list inefficient for a queue?
3. State the zero-based array indices of the left and right children of heap index i.
4. What is the purpose of a sequence number in a priority queue?
5. Distinguish underflow from overflow.

Long Answer Questions

1. Explain how a circular array queue works and why its enqueue and dequeue operations are O(1).
2. Compare linked-list and array-based implementations of stacks and queues.
3. Describe insertion and minimum removal in a binary min-heap.
4. Explain how stacks support delimiter matching and postfix expression evaluation.
5. Discuss the role of bounded queues and back-pressure in production systems.

Analytical / Application Questions

1. Design a scheduling policy for a help desk that balances urgency and fairness. Specify the queue structure, priority key, tie-breaking rule, and starvation mitigation.
2. A producer generates messages faster than a consumer for short periods but not indefinitely. Recommend a buffering strategy and explain what should happen when the buffer is full.
3. Design a browser history system supporting visit, Back, Forward, and a new visit after going Back. Identify the required structures and explain the state transitions.

Multiple Choice Questions with Answers

Question 1

Which operation removes the most recently inserted item from a stack?

A. enqueue

B. dequeue

C. pop

D. insertBest

Correct Answer: C. pop

Question 2

For a zero-based binary heap, what is the index of the left child of index i?

A. 2i

B. 2i + 1

C. i + 1

D. floor((i − 1) / 2)

Correct Answer: B. 2i + 1

Question 3

Which Python structure is designed for efficient insertion and removal at both ends?

A. list with pop(0)

B. set

C. collections.deque

D. tuple

Correct Answer: C. collections.deque

Question 4

What is the usual time complexity of removing the minimum item from a binary min-heap containing n items?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: B. O(log n)

Question 5

In a circular queue of capacity C using a front index and size, which expression gives the rear insertion index?

A. (front + size) mod C

B. front − size

C. size mod (C − 1)

D. front × size

Correct Answer: A. (front + size) mod C

Question 6

Which data structure is most directly appropriate for matching nested parentheses?

A. Stack

B. FIFO queue

C. Min-heap

D. Hash set

Correct Answer: A. Stack

Question 7

What does a min-priority queue remove first?

A. The most recently inserted item

B. The item with the smallest priority key

C. The item with the largest priority key

D. A random item

Correct Answer: B. The item with the smallest priority key

Question 8

Why can a sequence number be added to priority-queue entries?

A. To make heap construction impossible

B. To guarantee all priorities are unique by changing their meaning

C. To provide deterministic tie-breaking among equal priorities

D. To convert a queue into a stack

Correct Answer: C. To provide deterministic tie-breaking among equal priorities

Question 9

What is the amortized complexity of appending to a dynamically resizing array-based stack?

A. O(1)

B. O(log n)

C. O(n) for every append

D. O(n²)

Correct Answer: A. O(1)

Question 10

Which policy helps reduce starvation in a priority-based service system?

A. Ignoring waiting time

B. Ageing waiting requests

C. Deleting low-priority requests immediately

D. Always serving the newest request

Correct Answer: B. Ageing waiting requests