6. Stacks, Queues, Deques, and Priority Queues

Introduction and Context

Many algorithms do not require arbitrary access to every stored item. Instead, they process items according to a disciplined order. A compiler may evaluate the most recently opened construct first; a printer may serve requests in arrival order; a network router may prioritize urgent packets; and a simulation may repeatedly remove the event with the smallest timestamp. These requirements are captured by linear abstract data types (ADTs): stacks, queues, deques, and priority queues.

The central design issue is not merely how data is stored, but which operation is permitted next. A stack follows last-in, first-out (LIFO) discipline, whereas a queue follows first-in, first-out (FIFO) discipline. A deque permits insertion and deletion at both ends. A priority queue removes the item having the highest service priority rather than necessarily the item inserted earliest.

This chapter develops these ADTs from their abstract operations to array- and link-based implementations in C. It also examines circular queues, expression processing, backtracking, scheduling, buffering, heaps, complexity, implementation risks, and professional design choices. The material builds on arrays, pointers, structures, recursion, and dynamic memory management, and prepares the reader for graph algorithms, operating-system scheduling, parsing, and event-driven systems.

Learning Objectives

After completing this chapter, the learner should be able to:

1. Define and distinguish stacks, queues, deques, and priority queues.

2. Implement these ADTs using arrays, linked nodes, circular storage, and binary heaps in C.

3. Analyze time and space complexity and identify boundary conditions.

4. Apply stacks to expression conversion, expression evaluation, recursion, and backtracking.

5. Apply queues to scheduling, buffering, breadth-first search, and simulation.

6. Select an appropriate representation by considering capacity, locality, memory overhead, and workload.

7. Diagnose common implementation errors, including overflow, underflow, stale indices, and incorrect heap restoration.

Linear ADTs and Their Operational Disciplines

An ADT specifies behavior independently of representation. A stack, for example, is characterized by operations such as `push`, `pop`, `peek`, and `isEmpty`; whether it uses an array or linked list is an implementation decision. This separation allows an algorithm to depend on a reliable interface rather than on storage details.

The following concepts recur throughout the chapter:

• Overflow occurs when an insertion is attempted into a full bounded structure.
• Underflow occurs when deletion or inspection is attempted on an empty structure.
• Front identifies the removal end of a queue or deque.
• Rear identifies the insertion end of a queue.
• Top identifies the active end of a stack.
• Stable service preserves arrival order among elements with equal priority.
• Capacity is the maximum number of elements that can be held by a bounded implementation.

A useful engineering principle is that each operation should preserve an invariant. For a stack, the top index must identify exactly the last valid element. For a queue, front, rear, and size must consistently describe the occupied positions. For a heap, every parent must satisfy the selected priority relation with its children.

Stacks: LIFO Processing

A stack permits insertion and deletion at one end called the top. If values 10, 20, and 30 are pushed in that order, 30 is removed first. The principal operations are:

• `push(x)`: insert `x` at the top.
• `pop()`: remove and return the top item.
• `peek()`: return the top item without removing it.
• `isEmpty()`: test whether the stack has no elements.
• `isFull()`: relevant to bounded array implementations.

Array implementation

An array stack is compact and cache-friendly. With an array `data[CAPACITY]`, the variable `top` may be initialized to `-1`. A push first checks `top == CAPACITY - 1`, then increments `top` and stores the item. A pop first checks `top == -1`, then returns `data[top--]`.

```c

typedef struct {

int data[100];

int top;

} Stack;

void initStack(Stack *s) { s->top = -1; }

int push(Stack *s, int x) {

if (s->top == 99) return 0;

s->data[++s->top] = x;

return 1;

}

int pop(Stack s, int out) {

if (s->top == -1) return 0;

*out = s->data[s->top--];

return 1;

}

```

Both insertion and deletion take constant time, O(1). The principal limitation is fixed capacity. A dynamically resized array can overcome this limitation, but resizing occasionally costs O(n), although the amortized cost of repeated pushes remains O(1) under standard geometric growth policies.

Linked implementation

A linked stack stores the top node at the head of a singly linked list. Pushing creates a node and makes it the new head; popping removes the head. Both operations remain O(1), and capacity is limited primarily by available memory. Each item, however, requires pointer storage, and separate allocation may reduce locality and increase allocation overhead.

```c

typedef struct Node {

int value;

struct Node *next;

} Node;

int pushNode(Node **top, int x) {

Node *p = malloc(sizeof(Node));

if (!p) return 0;

p->value = x;

p->next = *top;

*top = p;

return 1;

}

```

A robust implementation must free a popped node and must release all remaining nodes when the stack is destroyed. Failure to do so produces memory leaks.

Stack applications

Stacks model nested and reversible behavior. Function calls use an implicit call stack containing return addresses, parameters, and local variables. Compilers use stacks for delimiter matching and expression parsing. Undo facilities store previous states or operations on a stack. Depth-first search and maze solving use a stack to defer alternatives. Backtracking pushes a decision, explores it, and pops the decision when that branch fails.

#### Expression processing

For an infix expression such as `A + B C`, precedence determines that multiplication occurs before addition. A stack-based infix-to-postfix conversion scans tokens from left to right. Operands go directly to the output; operators are temporarily held while operators of higher or equal precedence are removed according to associativity. Parentheses delimit this process. The postfix result is `A B C +`.

Postfix evaluation uses an operand stack. Each operand is pushed. When an operator appears, the required operands are popped, the operation is performed, and the result is pushed. For subtraction and division, order matters: if `b` is popped first and `a` second, the operation is `a - b` or `a / b`, not the reverse. Invalid expressions can be detected when an operator lacks sufficient operands or when more than one result remains at the end.

Queues and Circular Storage

A queue inserts at the rear and removes from the front. Its FIFO discipline is appropriate when fairness and arrival order matter. Operations include `enqueue`, `dequeue`, `front`, `isEmpty`, and, in bounded designs, `isFull`.

A naïve array queue may increment both indices. After several deletions, unused cells appear at the beginning even though the rear has reached the end. Shifting all elements after every deletion avoids this but makes deletion O(n). A circular queue treats the array as if its end were connected to its beginning. Indices advance using modular arithmetic:

`next = (index + 1) % capacity`.

The cleanest implementation maintains `front`, `rear`, and `size`. Initially, `front = rear = 0` and `size = 0`. Enqueue stores at `rear`, advances rear, and increments size. Dequeue reads at front, advances front, and decrements size. The queue is empty when `size == 0` and full when `size == capacity`.

```c

typedef struct {

int data[64];

int front, rear, size;

} Queue;

void initQueue(Queue *q) {

q->front = q->rear = q->size = 0;

}

int enqueue(Queue *q, int x) {

if (q->size == 64) return 0;

q->data[q->rear] = x;

q->rear = (q->rear + 1) % 64;

q->size++;

return 1;

}

int dequeue(Queue q, int out) {

if (q->size == 0) return 0;

*out = q->data[q->front];

q->front = (q->front + 1) % 64;

q->size--;

return 1;

}

```

Maintaining `size` eliminates the ambiguity that arises when `front == rear`: that condition can represent either an empty queue or a full queue in a design that reserves no explicit slot. An alternative is to reserve one array position and declare the queue full when the next rear position equals front.

Linked queues

A linked queue normally maintains both `front` and `rear` pointers. Enqueue appends a node at the rear; dequeue removes the node at the front. Each operation is O(1). When the final node is removed, both pointers must be set to `NULL`. Forgetting to reset rear creates a dangling pointer and may cause later insertion to access freed memory.

Queues are used in printer spooling, operating-system ready queues, producer-consumer buffers, breadth-first search, packet handling, and discrete-event simulations. In concurrent systems, a queue also requires synchronization. A correct sequential queue is not automatically safe when multiple threads modify it simultaneously.

Deques: Controlled Access at Both Ends

A deque, or double-ended queue, supports insertion and deletion at both front and rear. It can act as a stack, a queue, or a hybrid structure. Typical operations are `insertFront`, `insertRear`, `deleteFront`, `deleteRear`, and inspections at either end.

A circular array is an efficient deque representation. Each operation adjusts an index modulo capacity. A doubly linked list is also natural because deletion at either end is O(1), provided front and rear pointers are maintained. Each node has `prev` and `next` links, increasing memory use but simplifying reverse-end deletion.

Deques support sliding-window algorithms. For example, the maximum of every window of length `k` can be found in O(n) using a monotonic deque: indices whose values cannot become maximum are removed from the rear, while expired indices are removed from the front. Deques are also useful in work-stealing schedulers, where one end is used by an owning worker and the other by a scheduler or another worker. Such concurrent applications require carefully designed synchronization or lock-free algorithms.

Priority Queues and Binary Heaps

A priority queue associates each item with a priority. In a max-priority queue, the largest key is removed first; in a min-priority queue, the smallest key is removed first. Its abstract operations include insertion, inspection of the extreme-priority item, and deletion of that item. Some systems also require `changePriority` or `merge`.

An unsorted array gives O(1) insertion but O(n) deletion of the best item. A sorted array gives O(1) deletion at one end but O(n) insertion. A linked list has similar trade-offs. A binary heap provides a balanced compromise: insertion and deletion are O(log n), while inspection is O(1).

Heap representation

A binary heap is a complete binary tree satisfying a heap-order property. In a zero-based array, the relationships are:

• parent of node `i`: `(i - 1) / 2` for `i > 0`;
• left child: `2*i + 1`;
• right child: `2*i + 2`.

In a max-heap, every parent key is at least as large as either child. Insertion appends the new item at the next available leaf and repeatedly exchanges it with its parent while it has greater priority. This is called sift-up or up-heap.

Deletion of the root replaces it with the final array element, decreases the size, and repeatedly exchanges it with its higher-priority child until heap order is restored. This is sift-down. At each step, the larger child must be selected in a max-heap; selecting merely the left child can produce an invalid heap.

```c

void siftDown(int a[], int n, int i) {

while (2 * i + 1 < n) {

int child = 2 * i + 1;

if (child + 1 < n && a[child + 1] > a[child])

child++;

if (a[i] >= a[child]) break;

int t = a[i]; a[i] = a[child]; a[child] = t;

i = child;

}

}

```

A heap can be built by inserting items one at a time in O(n log n), or by bottom-up heap construction in O(n). The latter begins at the last internal node and applies sift-down toward the root. Although individual sift-down operations may be logarithmic, most nodes are near the leaves and move only a short distance, yielding linear total time.

A heap is not a fully sorted structure. It guarantees access to the extreme element, but arbitrary traversal does not produce sorted order. If priorities are equal, a basic heap does not guarantee arrival-order stability. Stability can be introduced by storing a sequence number and comparing `(priority, sequence)` pairs.

Choosing an Implementation

Representation should follow workload rather than habit. Arrays usually offer excellent locality, low per-element overhead, and predictable memory use. They are suitable for bounded buffers and high-throughput stacks. Linked structures grow flexibly and avoid contiguous allocation, but they consume link memory and may suffer from cache misses.

A circular array is often preferable to a shifting queue. A linked queue is preferable when capacity is highly variable or when nodes already exist elsewhere. A heap is appropriate when repeated access to the best-priority item dominates. If priorities have a small bounded integer range, bucket queues may outperform heaps by placing items into priority-specific queues. If the requirement is simply FIFO, adding a heap introduces unnecessary complexity.

Complexity alone is not sufficient. Designers should also consider maximum load, latency guarantees, memory fragmentation, cache behavior, cancellation requirements, fairness, and whether operations occur concurrently. An unbounded linked queue may avoid nominal overflow but still exhaust system memory; therefore production systems require explicit limits and back-pressure policies.

Applications in Algorithms and Systems

Scheduling

A basic ready queue implements round-robin scheduling: a process receives a time slice and, if unfinished, returns to the rear. Priority scheduling uses a priority queue, although starvation can occur when low-priority jobs are continually postponed. Aging gradually increases the effective priority of waiting jobs and improves fairness. A production scheduler may combine multiple queues, deadlines, processor affinity, and workload classes.

Buffering and streaming

A producer-consumer buffer decouples components operating at different speeds. A bounded circular queue prevents the producer from consuming unlimited memory. When full, the producer may block, reject data, overwrite the oldest item, or apply back-pressure. Each policy has semantic consequences. Overwriting may be acceptable for sensor readings but unacceptable for financial transactions.

Breadth-first and depth-first search

Breadth-first search uses a queue and explores vertices in nondecreasing distance from a source in an unweighted graph. Depth-first search uses a stack, explicitly or through recursion. Marking a vertex when it is discovered, rather than only when removed, prevents multiple unnecessary insertions in many implementations.

Simulation

In a discrete-event simulation, events are usually stored in a min-priority queue ordered by timestamp. The earliest event is removed, its effects are applied, and new future events are inserted. The event structure must define how simultaneous events are ordered, because nondeterministic tie handling can make experiments irreproducible.

Illustrative Case Study: A Network Packet Gateway

Background

Consider an illustrative gateway serving packets arriving from several network interfaces. Packets contain source information, payload length, arrival time, and service class. Voice packets are delay-sensitive, ordinary data packets are less urgent, and diagnostic packets have the lowest priority.

Situation and problem

A simple FIFO queue treats all packets equally. During a burst of large data transfers, voice packets wait too long. Replacing the queue with an unrestricted priority queue improves voice latency but may indefinitely delay diagnostic traffic. The gateway also has finite memory and must handle bursts without corrupting packet order.

Analysis

The gateway needs a bounded structure, explicit overflow behavior, and a policy for equal priorities. A binary heap can select the highest-priority packet efficiently, but it does not alone provide fairness. Each packet can therefore be assigned an effective key consisting of service priority and waiting time. Alternatively, separate FIFO queues can be maintained for each class, with weighted round-robin service.

Approach and solution

One illustrative design uses three FIFO queues in a circular-buffer implementation. A scheduler serves two voice packets, then one ordinary packet, then one diagnostic packet when those queues are nonempty. Within each class, arrival order is preserved. If a queue is full, the gateway records a drop counter and applies a documented policy: voice packets may be rejected only after a strict threshold, while diagnostic packets may be discarded first. Packet metadata includes a sequence number for monitoring and audit.

A different workload, in which packet deadlines vary continuously, may justify a min-heap keyed by deadline. In either design, enqueue and dequeue operations check capacity, and all drops are observable through metrics rather than silently ignored.

Outcome

The multi-queue design provides predictable service and avoids starvation under ordinary assumptions. It also exposes policy choices clearly: priority, fairness, capacity, and loss behavior are separated from the basic queue mechanism. Testing with burst traffic can measure latency percentiles, queue occupancy, drop rates, and service share.

Learning points

The case demonstrates that an ADT is only one part of a system design. The representation must be combined with a scheduling policy, capacity management, observability, and a definition of fairness. A technically correct priority queue can still implement an unacceptable service policy if starvation and overload are ignored.

Common Errors, Risks, and Professional Considerations

The most frequent stack error is confusing an empty top value with a valid data value. A separate top index or size field is safer. Queue implementations often fail because rear is advanced without modular wraparound, or because full and empty states are confused. Linked implementations commonly leak nodes, dereference `NULL`, or retain dangling front/rear pointers.

Heap implementations are vulnerable to incorrect child selection, off-by-one bounds, and comparing priorities in the wrong direction. A heap delete operation must not read children beyond the current size. Expressions require careful tokenization: unary minus, identifiers with multiple characters, function calls, and malformed parentheses cannot be handled correctly by a simplistic single-character algorithm.

At system level, priority mechanisms raise ethical and governance concerns. A policy that permanently deprioritizes a class of users may create unfair service. Logs should avoid exposing sensitive payloads while still recording sufficient operational evidence. Safety-critical or financial systems should define overflow, timeout, ordering, and recovery behavior explicitly. Memory allocation failures must be treated as normal possible outcomes, not ignored.

Concurrent queues and deques require atomicity and a memory-ordering model. Lock-based implementations may be easier to verify, while lock-free implementations can provide performance benefits but demand advanced reasoning about the C memory model, reclamation, and the ABA problem. Correctness, testability, and failure behavior should precede premature optimization.

Emerging Directions and Best Practices

Modern systems increasingly combine classical ADTs with telemetry, adaptive scheduling, and hardware-aware optimization. Priority queues may support deadlines, cancellation, or multiple service classes. High-throughput systems use pooled nodes, contiguous ring buffers, batch operations, and cache-conscious layouts. Distributed systems extend queue concepts through durable brokers, partitioning, acknowledgements, retry queues, and dead-letter queues; these introduce persistence and delivery semantics beyond the in-memory ADTs studied here.

Recommended practices include:

• Define the ADT contract, including behavior on overflow and underflow.
• Maintain explicit invariants and assert them during testing.
• Use `size` when it removes ambiguity in circular storage.
• Encapsulate representation so clients cannot corrupt indices or links.
• Test empty, single-element, full, wraparound, repeated, and failure cases.
• Measure latency, memory, throughput, and fairness under realistic workloads.
• Document whether priority ordering is stable and how ties are resolved.
• Make ownership and destruction responsibilities explicit in C.
• Use sanitizers, static analysis, and boundary-focused tests to detect memory errors.

Chapter Summary

Stacks, queues, deques, and priority queues are linear ADTs defined by disciplined access rules. Stacks provide LIFO behavior and are central to parsing, recursion, undo, and backtracking. Queues provide FIFO behavior and support scheduling, buffering, breadth-first search, and simulation. Circular arrays eliminate the wasted space and shifting cost of naïve array queues. Deques extend controlled access to both ends and support sliding-window algorithms.

Priority queues organize service by priority. Binary heaps provide O(1) access to the extreme item and O(log n) insertion and deletion, while bottom-up heap construction takes O(n). Array and linked representations offer different trade-offs in locality, flexibility, capacity, and memory overhead. In practical systems, data structure selection must be combined with fairness, overflow policy, concurrency control, observability, and ethical service decisions. Correct invariants, boundary testing, and explicit contracts are as important as asymptotic complexity.

Key Terms

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

Stack: A linear ADT that follows last-in, first-out order.

Queue: A linear ADT that follows first-in, first-out order.

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

Priority Queue: An ADT that removes the item with the most urgent priority.

Top: The active insertion and deletion position of a stack.

Front: The position from which a queue or deque normally removes an item.

Rear: The position at which a queue normally inserts an item.

Overflow: An attempted insertion into a full bounded structure.

Underflow: An attempted deletion or inspection from an empty structure.

Circular Queue: A queue that reuses array positions through modular index movement.

Heap: A complete tree satisfying a parent-child priority-order property.

Max-Heap: A heap whose root has the largest key.

Min-Heap: A heap whose root has the smallest key.

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

Sift-Down: Restoring heap order by moving a replacement item toward the leaves.

Backtracking: Exploring a choice and reversing it when the choice cannot lead to a solution.

Stable Priority Service: Preserving insertion order among items with equal priority.

Back-Pressure: A mechanism that slows or restricts producers when a consumer or buffer is overloaded.

Review Questions

Short Answer Questions

1. What invariant distinguishes an empty stack from a stack containing a valid sentinel-like value?

2. Why does a circular queue avoid the shifting problem of a naïve array queue?

3. State the zero-based array formulas for the parent and children of a heap node.

4. What is the difference between overflow and underflow?

5. Why does a basic binary heap not guarantee stable ordering among equal priorities?

Long Answer Questions

1. Compare array-based and linked implementations of stacks and queues with respect to complexity, memory, locality, and capacity.

2. Explain infix-to-postfix conversion and postfix evaluation using stacks, including operator precedence and operand order.

3. Describe the design and operation of a circular queue using front, rear, and size.

4. Explain insertion and deletion in a binary max-heap and justify their O(log n) complexity.

5. Discuss how fairness, starvation, overflow policy, and observability affect the design of a priority-based scheduler.

Analytical / Application Questions

1. Design an ADT and representation for a bounded producer-consumer buffer in which the oldest sensor reading may be discarded when capacity is reached. Justify each policy.

2. A priority scheduler continually serves urgent jobs while ordinary jobs wait indefinitely. Analyze the problem and propose two solutions, explaining their trade-offs.

3. Given a stream of integers and a fixed window size, explain how a monotonic deque can compute each window maximum in O(n), and identify the role of expired indices.

22. Multiple Choice Questions with Answers

Question 1

A stack initially contains 4 and 7, with 7 at the top. If 9 is pushed and one item is popped, what value is returned?

A. 4

B. 7

C. 9

D. The stack is empty

Correct Answer: C. 9

Question 2

In a circular queue of capacity 8, which condition indicates that the queue is full when an explicit size field is maintained?

A. front == rear

B. size == 0

C. size == capacity

D. rear == capacity - 1

Correct Answer: C. size == capacity

Question 3

What is the principal reason for maintaining a size field in a circular queue?

A. It sorts the queue automatically

B. It distinguishes full and empty states when indices coincide

C. It eliminates the need for modular arithmetic

D. It makes linked queues possible

Correct Answer: B. It distinguishes full and empty states when indices coincide

Question 4

During postfix evaluation, the expression `8 3 -` should produce which result?

A. 5

B. -5

C. 24

D. 11

Correct Answer: A. 5

Question 5

For a zero-based binary heap array, the left child of the node at index i is located at:

A. i / 2

B. 2i

C. 2i + 1

D. 2i + 2

Correct Answer: C. 2i + 1

Question 6

Which operation restores a max-heap after the root has been replaced by the final array element?

A. Linear search

B. Sift-down

C. Queue rotation

D. Delimiter matching

Correct Answer: B. Sift-down

Question 7

Which representation generally provides O(1) insertion and deletion at both ends for a deque, assuming valid end pointers?

A. Singly linked list with only a front pointer

B. Doubly linked list with front and rear pointers

C. Sorted singly linked list

D. Binary search tree

Correct Answer: B. Doubly linked list with front and rear pointers

Question 8

Why can a priority queue cause starvation?

A. The queue always removes the oldest item

B. Low-priority items may be continually postponed by higher-priority arrivals

C. A heap cannot store duplicate keys

D. Circular indexing deletes the rear item

Correct Answer: B. Low-priority items may be continually postponed by higher-priority arrivals

Question 9

What is the time complexity of building a binary heap using the bottom-up method?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: C. O(n)

Question 10

In a packet gateway requiring arrival order within each service class and bounded memory, which design best directly satisfies both requirements?

A. One unbounded stack

B. Separate bounded FIFO queues for service classes

C. An unsorted array with random deletion

D. A heap with no tie-breaking rule

Correct Answer: B. Separate bounded FIFO queues for service classes