Queues

Queues

A queue is a linear data structure that follows FIFO (First-In, First-Out) principle. Elements are added at the rear and removed from the front, ensuring sequential processing in insertion order.

Think of a coffee shop line: customers join at the back and are served from the front, maintaining fairness and order.

Queue Structure and Operations

graph LR
    A[Front] --> B[Element 1]
    B --> C[Element 2]
    C --> D[Element 3]
    D --> E[Rear]

    F[Enqueue] -.-> E
    G[Dequeue] -.-> A
    H[Peek] -.-> A

    style A fill:#ffcdd2
    style E fill:#c8e6c9
    style F fill:#e1f5fe
    style G fill:#fff3e0
    style H fill:#f3e5f5

This diagram shows the basic queue structure with front and rear access points, and the three core operations: enqueue (add to rear), dequeue (remove from front), and peek (view front element).

Queue Applications

graph TD
    A[Queue Applications] --> B[Task Scheduling]
    A --> C[Breadth-First Search]
    A --> D[Buffer Management]
    A --> E[Process Communication]

    B --> F[CPU Process Queue]
    C --> G[Level-order Tree Traversal]
    D --> H[I/O Buffering]
    E --> I[Message Passing]

    style A fill:#e3f2fd
    style B fill:#c8e6c9
    style C fill:#fff3e0
    style D fill:#f3e5f5
    style E fill:#e8f5e8

This diagram illustrates the main application areas where queues are essential: task scheduling, graph algorithms, data buffering, and inter-process communication.

Core Operations

Operation	Description	Time Complexity
enqueue(item)	Add element to rear	O(1)
dequeue()	Remove and return front element	O(1)
peek()	View front element without removing	O(1)
isEmpty()	Check if queue is empty	O(1)
size()	Get number of elements	O(1)

Key Properties:

• FIFO Ordering: First in, first out processing
• Dual Access Points: Insert at rear, remove from front
• Sequential Processing: Perfect for pipelines and streaming

Implementation

Most languages provide efficient queue implementations using either linked lists or dynamic arrays with optimized dequeue operations.

JavaKotlinTypeScriptDartSwiftPython

import java.util.Queue;
import java.util.LinkedList;

Queue<String> queue = new LinkedList<>();
queue.offer("first");            // O(1)
queue.offer("second");           // O(1)
String front = queue.peek();     // O(1)
String dequeued = queue.poll();  // O(1)
boolean empty = queue.isEmpty(); // O(1)

import java.util.LinkedList
import java.util.Queue

val queue: Queue<String> = LinkedList()
queue.offer("first")           // O(1)
queue.offer("second")          // O(1)
val front = queue.peek()       // O(1)
val dequeued = queue.poll()    // O(1)
val empty = queue.isEmpty()    // O(1)

// npm install @datastructures-js/queue
import { Queue } from '@datastructures-js/queue';

const queue = new Queue<string>();
queue.enqueue("first");           // O(1)
queue.enqueue("second");          // O(1)
const front = queue.front();      // O(1)
const dequeued = queue.dequeue(); // O(1)
const empty = queue.isEmpty();    // O(1)

import 'dart:collection';

Queue<String> queue = Queue<String>();
queue.add("first");                    // O(1)
queue.add("second");                   // O(1)
String front = queue.first;            // O(1)
String dequeued = queue.removeFirst(); // O(1)
bool empty = queue.isEmpty;            // O(1)

// Swift Collections: https://github.com/apple/swift-collections
import Collections

var queue = Deque<String>()
queue.append("first")              // O(1)
queue.append("second")             // O(1)
let front = queue.first            // O(1)
let dequeued = queue.removeFirst() // O(1)
let empty = queue.isEmpty          // O(1)

from collections import deque

queue = deque()
queue.append("first")          # O(1)
queue.append("second")         # O(1)
front = queue[0]               # O(1)
dequeued = queue.popleft()     # O(1)
empty = len(queue) == 0        # O(1)

Applications

Breadth-First Search (BFS): Queues are essential for level-order tree traversal, where you process all nodes at one level before moving to the next. This approach is perfect for finding shortest paths in unweighted graphs and trees.

How BFS Works with Queues:

Imagine traversing this tree:

graph TD
    A((1)) --> B((2))
    A --> C((3))
    B --> D((4))
    B --> E((5))
    C --> F((6))

    style A fill:#e1f5fe
    style B fill:#fff3e0
    style C fill:#fff3e0
    style D fill:#f3e5f5
    style E fill:#f3e5f5
    style F fill:#f3e5f5

Step-by-Step procedure:

Step 1: Initialize

• Queue: [1]
• Visited: []

Step 2: Process Node 1

• Dequeue 1 from front → Queue: []
• Visit 1 → Visited: [1]
• Enqueue children 2, 3 → Queue: [2, 3]

Step 3: Process Node 2

• Dequeue 2 from front → Queue: [3]
• Visit 2 → Visited: [1, 2]
• Enqueue children 4, 5 → Queue: [3, 4, 5]

Step 4: Process Node 3

• Dequeue 3 from front → Queue: [4, 5]
• Visit 3 → Visited: [1, 2, 3]
• Enqueue child 6 → Queue: [4, 5, 6]

Step 5: Process Node 4

• Dequeue 4 from front → Queue: [5, 6]
• Visit 4 → Visited: [1, 2, 3, 4]
• No children → Queue: [5, 6]

Step 6: Process Node 5

• Dequeue 5 from front → Queue: [6]
• Visit 5 → Visited: [1, 2, 3, 4, 5]
• No children → Queue: [6]

Step 7: Process Node 6

• Dequeue 6 from front → Queue: []
• Visit 6 → Visited: [1, 2, 3, 4, 5, 6]
• No children → Queue: []

Step 8: Complete

• Queue is empty → Traversal complete!
• Result: [1, 2, 3, 4, 5, 6] (level by level, left to right)

Why Queues? The FIFO property ensures nodes are visited level by level, from left to right, maintaining the breadth-first order.

Other Common Uses:

• Task Scheduling: Operating systems use queues to manage process execution
• Message Buffering: Communication systems queue messages for sequential processing