Queues

Introduction

Queue: First-In-First-Out (FIFO) abstract data type. Insert: rear (enqueue), remove: front (dequeue). Fair: processes in arrival order. Fundamental: scheduling, simulation, buffering. Analogy: line at store.

"Queues model waiting lines naturally: fair, predictable, orderly. Used everywhere: job scheduling, network packets, breadth-first search. Fairness through FIFO discipline." -- Fundamental data structures

Queue Definition

FIFO Principle

First element in: first element out. Enqueue 1, 2, 3: queue is [1, 2, 3]. Dequeue: returns 1 (first added). Enqueue 4: queue is [2, 3, 4].

Operations

Enqueue (insert at rear). Dequeue (remove from front). Peek (view front). isEmpty. Size. All O(1).

Example

Enqueue A: [A]Enqueue B: [A, B]Enqueue C: [A, B, C]Dequeue: [B, C] (returned A)Peek: returns BEnqueue D: [B, C, D]

Basic Operations

Enqueue

Add element to rearTime: O(1)Implementation: rear pointer increment

Dequeue

Remove from front, returnTime: O(1)Error: if empty (underflow)

Peek

View front elementTime: O(1)No removal

isEmpty

Test if emptyTime: O(1)

Size

Count elementsTime: O(1) or O(n)

Implementation

Array-Based (Simple)

class SimpleQueue: data = array[0..max-1] front = 0, rear = -1 enqueue(x): if rear == max-1: error (overflow) rear++ data[rear] = x dequeue(): if front > rear: error (underflow) result = data[front] front++ return result Problem: wasted space (front advances)

Circular Queue

Wraparound: rear position modulo sizeEfficient: reuses spaceComplexity: more logic, but O(1) space

Linked List-Based

class LinkedQueue: head = null, tail = null enqueue(x): new_node = Node(x) if head == null: head = tail = new_node else: tail.next = new_node tail = new_node dequeue(): if head == null: error result = head.data head = head.next if head == null: tail = null return result

Circular Queue

Concept

Wraparound: rear position wraps to beginning. Reuses space: abandoned slots filled. Size fixed: efficient for bounded queues.

Empty/Full Detection

Empty: front == rearFull: (rear + 1) % size == frontAlternative: track count (count == 0 is empty, count == size is full)

Implementation

enqueue(x): if (rear + 1) % size == front: overflow rear = (rear + 1) % size data[rear] = xdequeue(): if front == rear: underflow front = (front + 1) % size return data[front]

Advantages

Space efficient: no waste. Fixed memory: predictable. Fast: O(1) operations. Simple: easy to implement.

Disadvantages

Fixed size: cannot grow. Complexity: modulo operations. Overflow: immediate (no dynamic resize).

Double-Ended Queue (Deque)

Operations

Insert/remove: both ends. Generalizes: stack and queue. Push/pop front and rear.

Operations

Push front/rear, pop front/rear. Peek front/rear. All O(1). Doubly linked list or circular array.

Use Cases

Sliding window: maintain sub-problem results. A-Steal scheduling: workers steal work from both ends. Undo/redo: deque tracks history.

Priority Queue

Definition

Dequeue highest priority first (not FIFO). Priority: associated with each element. Common: min-heap (smallest first) or max-heap (largest first).

Operations

Insert (enqueue with priority). Extract max/min. Peek max/min. Time: O(log n) insertion, O(1) peek, O(log n) extraction.

Implementation

Heap-based: balanced tree. Binary heap: array-based. Efficient for queue operations.

Applications

Dijkstra's algorithm: shortest path. Huffman coding: optimal encoding. Task scheduling: priority-based. Simulations: event processing.

Time Complexity

Standard Queue

Priority Queue

Insertion: O(log n). Extraction: O(log n). Peek: O(1). Construction: O(n) heapify.

Applications

Breadth-First Search (BFS)

Graph traversal: queue of nodes. Level-by-level exploration. Shortest path (unweighted).

Job Scheduling

Fair allocation: round-robin. OS: process scheduling. Load balancing: distribute work.

Network Buffers

Packets: queue before processing. Flow control: buffer management. Congestion: queue growth indicates overload.

Simulation

Event-driven: process events in order. Bank queue: simulate customer arrivals. Traffic: simulate vehicle flow.

Printer Queue

Fair: first request printed first. Multiple jobs: ordered. FIFO discipline.

Breadth-First Search

Algorithm

queue = Queue()queue.enqueue(start)visited = set()visited.add(start)while !queue.isEmpty(): node = queue.dequeue() process(node) for each neighbor: if !visited.contains(neighbor): visited.add(neighbor) queue.enqueue(neighbor)

Time Complexity

V vertices, E edges: O(V + E). Each vertex/edge processed once.

Applications

Shortest path (unweighted). Connected components. Social network (distance from person). Maze solving.

Job Scheduling

Round-Robin

Each job: time quantum. Completed: removed. Incomplete: re-enqueued (rear). Fair: equal opportunity.

Priority Scheduling

Use priority queue: high priority jobs first. Preemption: interrupt low for high. Starvation: risk (high volume may starve low).

Multi-Queue

Multiple queues: different priority levels. Scheduler: services high first. Fairness: each level fair internally.

Practical Examples

Print Queue

Jobs: enqueued by users. Printer: dequeues in order. FIFO: fair allocation.

Call Center

Calls: entered queue. Agents: process in order. Performance: queue length indicates wait time.

HTTP Request Queue

Server: queues requests. Thread pool: dequeues and processes. Concurrency: bounded.

Cache Eviction

FIFO cache: oldest removed. Simple policy. Less effective than LRU (but queue works).

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. "Introduction to Algorithms." MIT Press, 3rd edition, 2009.
• Knuth, D. E. "The Art of Computer Programming: Fundamental Algorithms." Vol. 1, Addison-Wesley, 3rd edition, 1997.
• Sedgewick, R., and Wayne, K. "Algorithms." Addison-Wesley, 4th edition, 2011.
• Weiss, M. A. "Data Structures and Problem Solving Using Java." Addison-Wesley, 4th edition, 2010.
• Goodrich, M. T., Tamassia, R., and Goldwasser, M. H. "Data Structures and Algorithms in Java." Wiley, 6th edition, 2014.