Deques & Priority Queue ADTs

Topics Covered:
33. Double-Ended Queue (Deque) ADT & Core Operations • Input-Restricted vs Output-Restricted Deques • Circular Array Deque Modulo Mathematics • The Sliding Window Maximum Monotonic Deque Pattern (Potential Method Proof) • 34. Priority Queue ADT Fundamentals & Underlying Data Structure Trade-offs • Production Implementations

Linear data structures culminate in two powerful generalized container models: Double-Ended Queues (Deques) and Priority Queues. While a Deque generalizes sequence boundaries by enabling constant-time insertions and removals at both the front and rear, a Priority Queue breaks away from chronological arrival ordering entirely, servicing elements based on an intrinsic priority key. This chapter formalizes bidirectional ring buffer mathematics, monotonic deque algorithms for optimal $O(n)$ sliding window queries, the Priority Queue abstract contract, and comparative trade-offs across contiguous, linked, and tree-backed implementations.

• Formalize the Double-Ended Queue (Deque) ADT contract and demonstrate how it subsumes both LIFO stacks and FIFO queues.
• Implement circular array deques using bidirectional modular arithmetic to step backward and forward in physical RAM without shifting.
• Formulate the decreasing monotonic deque invariant and prove how it solves the Sliding Window Maximum problem in optimal $\Theta (n)$ time using the Physicist's Potential Method.
• Define the Priority Queue ADT interface and compare the asymptotic bounds of arrays, linked lists, balanced binary search trees, and binary heaps.
• Trace real-world deployments in operating system scheduling (Linux CFS), network traffic QoS packet prioritization, and Huffman tree construction.

A Double-Ended Queue (Deque), pronounced "deck", is a generalized linear container that permits element insertion and deletion with equal efficiency at both ends: the Front and the Rear.

Because access is permitted at both boundaries, the Deque serves as a universal linear primitive:

• Restricting mutations to PushFront and PopFront forms a LIFO Stack.
• Restricting mutations to PushBack and PopFront forms a FIFO Queue.

To achieve $O(1)$ time across all four boundary operations without dynamic node allocations or memory shifting, an implementation wraps a contiguous array using modular arithmetic in both directions:

Advancing Forward (PushBack, PopFront):

Stepping Backward (PushFront, PopBack):

Adding Capacity before modulo ensures the intermediate value remains strictly non-negative in languages where % calculates truncated remainder rather than Euclidean modulo:

The Problem:

Given an array $A$ of $n$ numbers and a sliding window of size $k$, find the maximum value in every window as it slides from left to right.

• Brute Force: Inspecting all $k$ elements per window requires $O((n-k+1)\cdot k)=O(n\cdot k)$ time.
• Monotonic Deque Solution: Achieves optimal $\Theta (n)$ linear time by maintaining a strictly decreasing invariant!

Formal Amortized Analysis via the Physicist's Potential Method:

Define the potential function $\Phi$ at step $i$ as the number of elements currently stored in the deque:

• For each index $i\in [0,n-1]$:
  1. Let $d_i$ be the number of elements popped from the back (dominated elements) plus elements popped from the front (expired elements).
  2. The actual work performed is $c_i=1+d_i$ (one push plus $d_i$ pops).
  3. The change in potential is:
     $$\Delta {\Phi }_i={\Phi }_i-{\Phi }_{i-1}=1-d_i$$
  4. The amortized cost per element is:
     $${\hat{c}}_i=c_i+\Delta {\Phi }_i=(1+d_i)+(1-d_i)=2=\Theta (1)$$

Across the entire array of length $n$, total operations ${\sum }_{i=1}^n{c}_i\le 2n⟹$ Strictly $\Theta (n)$ linear time. $■$

A Priority Queue is an Abstract Data Type where element servicing is governed not by chronological arrival order, but by an associated Priority Key:

• Max-Priority Queue: The element with the highest key is extracted first (ExtractMax).
• Min-Priority Queue: The element with the lowest key is extracted first (ExtractMin).

[!CONCEPT] Hospital Triage Mental Model Incoming Patients:

• Patient A: Arrival 8:00 AM, Mild Flu $\to$ Priority 2
• Patient B: Arrival 8:15 AM, Acute Trauma $\to$ Priority 10

Next Serviced: Patient B (Priority 10), superseding Patient A regardless of arrival time!

A. C++20 Optimal Sliding Window Maximum Monotonic Deque

#include <vector>
#include <deque>
#include <span>

std::vector<int> maxSlidingWindow(std::span<const int> nums, int k) {
    if (nums.empty() || k <= 0) return {};

    std::deque<int> dq; // Stores indices of candidate maximums
    std::vector<int> result;
    result.reserve(nums.size() - k + 1);

    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        // 1. Evict expired index outside current window [i - k + 1, i]
        if (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // 2. Preserve strictly decreasing monotonic invariant
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }

        // 3. Insert current element's index
        dq.push_back(i);

        // 4. Record maximum once the first window is primed
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

B. Python 3 Monotonic Deque with Type Annotations

from collections import deque
from typing import List

def max_sliding_window(nums: List[int], k: int) -> List[int]:
    """Finds maximum in each sliding window of size k in O(n) linear time."""
    if not nums or k <= 0:
        return []

    dq: deque[int] = deque()  # Stores indices
    result: List[int] = []

    for i, num in enumerate(nums):
        # 1. Evict expired index
        if dq and dq[0] <= i - k:
            dq.popleft()

        # 2. Maintain decreasing monotonic invariant
        while dq and nums[dq[-1]] <= num:
            dq.pop()

        # 3. Add current index
        dq.append(i)

        # 4. First window completes at index k - 1
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

1. Deque Generalization: Deques support bidirectional $O(1)$ operations at both Front and Rear, seamlessly subsuming both stacks and queues.
2. Bidirectional Modulo: Stepping backward in a circular array deque requires (idx - 1 + capacity) % capacity to prevent negative dividend truncation.
3. Monotonic Deques: Enforcing a strictly decreasing invariant across stored indices eliminates dominated candidates, solving the Sliding Window Maximum problem in optimal $\Theta (n)$ time.
4. Priority Queue ADT: Governed by priority rankings rather than arrival time; the Binary Heap is the canonical backing implementation due to $O(\log n)$ extraction and zero pointer overhead.

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 6: Heapsort, Chapter 10: Elementary Data Structures. MIT Press.
2. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.), Section 2.2: Linear Lists. Addison-Wesley.
3. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 2.4: Priority Queues. Addison-Wesley.
4. Huffman, D. A. (1952). A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE, 40(9), 1098-1101.