Skip to main content

Queues

Premium

A queue is a linear data structure that stores elements in First-In, First-Out (FIFO) order. The first element inserted is the first one removed, similar to a line of people waiting for service.

Queues allow fast insertion at the rear and deletion from the front in O(1) time, but random access is not efficient. They are widely used in task scheduling, data buffering, producer-consumer systems, and BFS in graphs.

Queue

Types of queues

1. Linear queue

A simple queue is the most basic form, following the FIFO (First-In, First-Out) principle. Elements are inserted at the rear and removed from the front. Once the rear reaches the end, no new element can be added unless earlier elements are dequeued.

Used for:

  • Task scheduling
  • BFS traversal in graphs

2. Circular queue

A circular queue connects the end of the queue back to the front, forming a circle. It efficiently reuses empty space left by dequeued elements, preventing overflow in fixed-size implementations. Useful for implementing buffer systems and load balancers.

Used for:

  • CPU scheduling (Round Robin)
  • I/O buffers
  • Real-time streaming data

3. Priority queue

A priority queue removes elements based on priority, not arrival order. The element with the highest priority (or lowest value, depending on convention) is dequeued first. It’s commonly implemented using heaps.

Used for:

  • Dijkstra’s shortest path algorithm
  • Operating system process scheduling
  • Event-driven simulation systems

4. Double-ended queue (Deque)

A deque allows insertion and deletion of elements from both ends, front and rear. It can behave as both a queue (FIFO) and a stack (LIFO), depending on usage.

Used for:

  • Sliding window problems
  • Palindrome checking
  • Implementing monotonic queues

Common queue operations

1. Enqueue (add element to rear)

from collections import deque queue = deque() queue.append(10) queue.append(20)

2. Dequeue (remove element from front)

x = queue.popleft()

3. Peek / Front (view front element)

front = queue[0]

Queue TC

Calculating memory usage

The memory footprint of a queue depends on its underlying implementation, typically arrays are used to build fixed-size queues, whereas linked lists are used to build variable-sized queues.

Common edge cases & pitfalls

  1. Queue underflow: Removing from an empty queue

  2. Queue overflow: Adding to a full queue (for fixed-size implementations)

  3. Forgetting to handle circular wrapping in circular queues

  4. Incorrectly maintaining window size in monotonic queue problems

Quiz

  1. What is the time complexity of enqueue and dequeue? a) O(n)

b) O(1)

c) O(log n)

d) O(n²)

  1. Which algorithm uses a queue internally? a) DFS

b) BFS

c) Binary Search

d) Quick Sort

  1. What’s the main advantage of a circular queue over a simple queue? a) Faster access time

b) Prevents overflow and reuses space

c) Easier to implement

d) Uses more memory

Practice problems

Next Lesson