Queues

November 19, 2025
#queue #data-structures #fifo #algorithms #interviewing

Table of Contents

Introduction

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Think of it like a line at a coffee shop: the first person to join the line is the first person to be served. This fair ordering makes queues perfect for managing tasks, requests, and data that needs to be processed in the order it arrives.

Queues are everywhere in computing—from managing print jobs and handling network requests to implementing breadth-first search algorithms. By the end of this tutorial, you’ll understand how queues work, when to use them, and how to implement them efficiently.

If you’re new to time and space complexity, start with our guide to Big-O Notation. You may also want to review Arrays, Linked Lists, and Stacks to understand related data structures.

What is a queue?

A queue is a collection of elements with two principal operations:

  1. Enqueue: Add an element to the back (rear) of the queue
  2. Dequeue: Remove and return the element from the front of the queue

Additionally, most queue implementations include: 3. Peek (or Front): View the front element without removing it 4. IsEmpty: Check if the queue is empty 5. Size: Get the number of elements in the queue

The key constraint: elements are added at one end (rear) and removed from the other end (front), maintaining FIFO order.

Why use a queue?

Choose a queue when:

  1. You need FIFO (First-In-First-Out) processing
  2. You’re managing tasks or requests that should be handled in order
  3. You’re implementing breadth-first search (BFS) algorithms
  4. You need a buffer between producers and consumers (producer-consumer pattern)
  5. You’re scheduling processes or managing resources fairly

Avoid a queue when:

  • You need LIFO (Last-In-First-Out) access (use a stack instead)
  • You need random access to elements (use an array)
  • You need priority-based ordering (use a priority queue with a heap)

Real-world applications

Queues are used in many practical scenarios:

  • Task scheduling: Operating systems use queues to manage processes and threads
  • Print queue: Managing print jobs in the order they’re submitted
  • Web servers: Handling incoming HTTP requests in order
  • Call centers: Managing customer service calls on hold
  • Breadth-first search: Graph and tree traversal algorithms
  • Message queues: RabbitMQ, Kafka for distributed systems
  • Keyboard buffer: Storing keystrokes in the order they’re typed
  • Asynchronous processing: Background job processing

Queue vs Stack

Understanding the difference between queues and stacks is crucial:

Feature Queue Stack
Order FIFO (First-In-First-Out) LIFO (Last-In-First-Out)
Add operation Enqueue (at rear) Push (at top)
Remove operation Dequeue (from front) Pop (from top)
Use cases Task scheduling, BFS Function calls, DFS, undo/redo
Analogy Line at a store Stack of plates

Core operations and complexity

All primary queue operations are extremely efficient:

  • Enqueue: O(1) — add element to rear
  • Dequeue: O(1) — remove and return front element
  • Peek/Front: O(1) — view front element without removing
  • IsEmpty: O(1) — check if queue is empty
  • Size: O(1) — get number of elements
  • Space: O(n) — where n is the number of elements in the queue

Queue implementation

Queues can be implemented using arrays or linked lists. Array-based implementations are simpler but may require resizing. Linked list implementations are more flexible and never need resizing.

Array-based queue (dynamic)

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.shift();
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }

  toArray() {
    return [...this.items];
  }
}

// Example usage
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.peek());     // 10
console.log(queue.dequeue());  // 10
console.log(queue.dequeue());  // 20
console.log(queue.size());     // 1
console.log(queue.isEmpty());  // false

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, element):
        self.items.append(element)

    def dequeue(self):
        if self.is_empty():
            return None
        return self.items.pop(0)

    def peek(self):
        if self.is_empty():
            return None
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

    def clear(self):
        self.items = []

    def to_list(self):
        return self.items.copy()

# Example usage
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print(queue.peek())       # 10
print(queue.dequeue())    # 10
print(queue.dequeue())    # 20
print(queue.size())       # 1
print(queue.is_empty())   # False

import java.util.ArrayList;

public class Queue {
    private ArrayList<Integer> items;

    public Queue() {
        items = new ArrayList<>();
    }

    public void enqueue(int element) {
        items.add(element);
    }

    public Integer dequeue() {
        if (isEmpty()) {
            return null;
        }
        return items.remove(0);
    }

    public Integer peek() {
        if (isEmpty()) {
            return null;
        }
        return items.get(0);
    }

    public boolean isEmpty() {
        return items.isEmpty();
    }

    public int size() {
        return items.size();
    }

    public void clear() {
        items.clear();
    }

    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        System.out.println(queue.peek());     // 10
        System.out.println(queue.dequeue());  // 10
        System.out.println(queue.dequeue());  // 20
        System.out.println(queue.size());     // 1
        System.out.println(queue.isEmpty());  // false
    }
}

Linked list-based queue

For optimal performance, implement queues using linked lists with both head and tail pointers:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedQueue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.length = 0;
  }

  enqueue(element) {
    const node = new Node(element);
    if (this.isEmpty()) {
      this.front = this.rear = node;
    } else {
      this.rear.next = node;
      this.rear = node;
    }
    this.length++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.front.value;
    this.front = this.front.next;
    if (this.front === null) {
      this.rear = null; // Queue is now empty
    }
    this.length--;
    return value;
  }

  peek() {
    return this.isEmpty() ? undefined : this.front.value;
  }

  isEmpty() {
    return this.length === 0;
  }

  size() {
    return this.length;
  }

  toArray() {
    const result = [];
    let current = this.front;
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    return result;
  }
}

// Example usage
const queue = new LinkedQueue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.peek());     // 10
console.log(queue.dequeue());  // 10
console.log(queue.toArray());  // [20, 30]

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedQueue:
    def __init__(self):
        self.front = None
        self.rear = None
        self.length = 0

    def enqueue(self, element):
        node = Node(element)
        if self.is_empty():
            self.front = self.rear = node
        else:
            self.rear.next = node
            self.rear = node
        self.length += 1

    def dequeue(self):
        if self.is_empty():
            return None
        value = self.front.value
        self.front = self.front.next
        if self.front is None:
            self.rear = None  # Queue is now empty
        self.length -= 1
        return value

    def peek(self):
        return None if self.is_empty() else self.front.value

    def is_empty(self):
        return self.length == 0

    def size(self):
        return self.length

    def to_list(self):
        result = []
        current = self.front
        while current:
            result.append(current.value)
            current = current.next
        return result

# Example usage
queue = LinkedQueue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print(queue.peek())      # 10
print(queue.dequeue())   # 10
print(queue.to_list())   # [20, 30]

class Node {
    int value;
    Node next;

    Node(int value) {
        this.value = value;
        this.next = null;
    }
}

public class LinkedQueue {
    private Node front;
    private Node rear;
    private int length;

    public LinkedQueue() {
        this.front = null;
        this.rear = null;
        this.length = 0;
    }

    public void enqueue(int element) {
        Node node = new Node(element);
        if (isEmpty()) {
            front = rear = node;
        } else {
            rear.next = node;
            rear = node;
        }
        length++;
    }

    public Integer dequeue() {
        if (isEmpty()) {
            return null;
        }
        int value = front.value;
        front = front.next;
        if (front == null) {
            rear = null; // Queue is now empty
        }
        length--;
        return value;
    }

    public Integer peek() {
        return isEmpty() ? null : front.value;
    }

    public boolean isEmpty() {
        return length == 0;
    }

    public int size() {
        return length;
    }

    public static void main(String[] args) {
        LinkedQueue queue = new LinkedQueue();
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        System.out.println(queue.peek());     // 10
        System.out.println(queue.dequeue());  // 10
        System.out.println(queue.size());     // 2
    }
}

Common queue problems

1. Breadth-First Search (BFS)

Use a queue to traverse a binary tree level by level:

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function bfsTraversal(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.value);

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return result;
}

// Example usage
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log(bfsTraversal(root)); // [1, 2, 3, 4, 5]

from collections import deque

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def bfs_traversal(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()
        result.append(node.value)

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    return result

# Example usage
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(bfs_traversal(root))  # [1, 2, 3, 4, 5]

import java.util.*;

class TreeNode {
    int value;
    TreeNode left, right;
    TreeNode(int value) { this.value = value; }
}

public class BFS {
    public static List<Integer> bfsTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            result.add(node.value);

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.println(bfsTraversal(root)); // [1, 2, 3, 4, 5]
    }
}

2. Generate binary numbers from 1 to N

Use a queue to generate binary representations efficiently:

function generateBinaryNumbers(n) {
  const result = [];
  const queue = ['1'];

  for (let i = 0; i < n; i++) {
    const binary = queue.shift();
    result.push(binary);

    // Generate next binary numbers by appending 0 and 1
    queue.push(binary + '0');
    queue.push(binary + '1');
  }

  return result;
}

console.log(generateBinaryNumbers(5)); // ['1', '10', '11', '100', '101']

from collections import deque

def generate_binary_numbers(n):
    result = []
    queue = deque(['1'])

    for i in range(n):
        binary = queue.popleft()
        result.append(binary)

        # Generate next binary numbers by appending 0 and 1
        queue.append(binary + '0')
        queue.append(binary + '1')

    return result

print(generate_binary_numbers(5))  # ['1', '10', '11', '100', '101']

import java.util.*;

public class BinaryNumbers {
    public static List<String> generateBinaryNumbers(int n) {
        List<String> result = new ArrayList<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer("1");

        for (int i = 0; i < n; i++) {
            String binary = queue.poll();
            result.add(binary);

            // Generate next binary numbers by appending 0 and 1
            queue.offer(binary + "0");
            queue.offer(binary + "1");
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(generateBinaryNumbers(5));
        // [1, 10, 11, 100, 101]
    }
}

3. Implement a stack using two queues

Challenge: Implement stack operations using only queue operations:

class StackUsingQueues {
  constructor() {
    this.q1 = [];
    this.q2 = [];
  }

  push(x) {
    // Add to q2
    this.q2.push(x);

    // Move all elements from q1 to q2
    while (this.q1.length > 0) {
      this.q2.push(this.q1.shift());
    }

    // Swap q1 and q2
    [this.q1, this.q2] = [this.q2, this.q1];
  }

  pop() {
    if (this.q1.length === 0) {
      return undefined;
    }
    return this.q1.shift();
  }

  top() {
    if (this.q1.length === 0) {
      return undefined;
    }
    return this.q1[0];
  }

  empty() {
    return this.q1.length === 0;
  }
}

// Example usage
const stack = new StackUsingQueues();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.top());  // 3
console.log(stack.pop());  // 3
console.log(stack.pop());  // 2

from collections import deque

class StackUsingQueues:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x):
        # Add to q2
        self.q2.append(x)

        # Move all elements from q1 to q2
        while self.q1:
            self.q2.append(self.q1.popleft())

        # Swap q1 and q2
        self.q1, self.q2 = self.q2, self.q1

    def pop(self):
        if not self.q1:
            return None
        return self.q1.popleft()

    def top(self):
        if not self.q1:
            return None
        return self.q1[0]

    def empty(self):
        return len(self.q1) == 0

# Example usage
stack = StackUsingQueues()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.top())  # 3
print(stack.pop())  # 3
print(stack.pop())  # 2

import java.util.*;

public class StackUsingQueues {
    private Queue<Integer> q1;
    private Queue<Integer> q2;

    public StackUsingQueues() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        // Add to q2
        q2.offer(x);

        // Move all elements from q1 to q2
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }

        // Swap q1 and q2
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }

    public Integer pop() {
        if (q1.isEmpty()) {
            return null;
        }
        return q1.poll();
    }

    public Integer top() {
        if (q1.isEmpty()) {
            return null;
        }
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }

    public static void main(String[] args) {
        StackUsingQueues stack = new StackUsingQueues();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.top());  // 3
        System.out.println(stack.pop());  // 3
        System.out.println(stack.pop());  // 2
    }
}

Queue variations

  • Circular Queue: Uses a fixed-size array with wraparound to avoid wasting space
  • Deque (Double-ended queue): Allows insertion and deletion at both ends
  • Priority Queue: Elements are dequeued based on priority rather than arrival order (uses heaps)
  • Blocking Queue: Thread-safe queue that blocks when empty or full (used in concurrent programming)

Common pitfalls

  • Array dequeue is O(n): Using array shift() or pop(0) requires shifting elements. Use linked lists for true O(1) dequeue.
  • Forgetting to update rear: In linked list implementations, ensure the rear pointer is updated correctly
  • Queue underflow: Always check if the queue is empty before dequeuing
  • Memory leaks: In manual-memory languages, ensure dequeued nodes are properly freed
  • Not handling empty queue in peek: Verify the queue has elements before accessing the front

When to prefer other data structures

  • Need LIFO access → Use a stack
  • Need random access → Use an array
  • Need priority ordering → Use a priority queue (heap)
  • Need search operations → Use a hash table
  • Need sorted data → Use a binary search tree or sorted array

Practice problems

  1. Implement a circular queue with fixed capacity using an array
  2. Reverse the first K elements of a queue
  3. Implement a queue using a single stack
  4. Generate all perfect squares from 1 to N using a queue
  5. Use a queue to check if a binary tree is a complete binary tree
  6. Implement a recent counter that counts requests in the last 3000ms using a queue
  7. Design a system to handle requests with rate limiting using a queue
  8. Solve the “Hot Potato” problem (Josephus problem) using a queue
  9. Level order traversal of a tree with null markers between levels
  10. Find the first non-repeating character in a stream of characters using a queue

Complexity summary

All core queue operations are constant time:

  • Time complexity:
    • Enqueue: O(1)
    • Dequeue: O(1) (linked list) or O(n) (naive array)
    • Peek: O(1)
    • IsEmpty: O(1)
    • Size: O(1)
  • Space complexity: O(n) where n is the number of elements

This constant-time performance for enqueue and dequeue (with proper implementation) makes queues ideal for managing ordered data efficiently.

Thanks for visiting
We are actively updating content to this site. Thanks for visiting! Please bookmark this page and visit again soon.
Sponsor