ReviseAlgo Logo

Stacks & Queues

Queue & Deque

Master Queue and Double-ended Queue (Deque) operations, circular queue array wrapping, and BFS queue architectures.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What are Queues and Deques?

  • A Queue is a linear data structure that operates on a FIFO (First In First Out) basis: insert at the rear, remove from the front.
  • A Deque (Double-ended Queue, pronounced "deck") is a generalization that permits insertion and deletion at both the front and rear ends in constant time.

    • Why study them?

    Deques are the Swiss Army knife of queue-based problems. They allow you to maintain window boundaries (for sliding window algorithms) and traverse trees/graphs layer-by-layer (Breadth-First Search).

    Where is it Used?

  • Breadth-First Search (BFS): Tracking frontier nodes layer-by-layer.
  • Task Scheduling Pools: Thread execution work-stealing pools where idle threads steal tasks from the back of other threads' deques.

    • 2. Mental Model: The Double-Ended Conveyor

    Think of a Deque as a conveyor belt with access points at both ends:

  • You can place a box onto the belt from either the left end or the right end.
  • You can lift a box off the belt from either the left end or the right end.
  • If you restrict inputs to the right end and outputs to the left end, the belt behaves as a standard FIFO queue.

    • 3. Core Algorithms & Implementations

    1. Circular Queue Implementation

    To implement a queue with a fixed-size array without shifting elements on dequeues:
  • Maintain indices front and rear initialized to -1 or 0.
  • Enqueue: Increment rear circularly: rear = (rear + 1) % capacity.
  • Dequeue: Increment front circularly: front = (front + 1) % capacity.
  • Full Condition: (rear + 1) % capacity == front.
  • Empty Condition: front == -1 or front == rear.

    • 2. Standard Deque Usage Across Languages

    Deques are used to solve sliding window lookups and BFS traversals.

    4. Visual Trace: Circular Index Modulo Updates

    Queue size = 3. data = [0, 0, 0]. Head = 0, Tail = 0, Size = 0.

    5. Real-World Applications

  • Work Stealing Pools: Concurrent executors use Deques so worker threads push/pop tasks from their own Front, while idle threads steal tasks from the Rear to balance workloads.
  • BFS Crawlers: Web search crawlers use queues to scan outbound links layer-by-layer.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test circular boundaries and tree navigations:
  • "Design a Circular Deque." (LeetCode 641 -> similar to circular queue, but with circular decrement updates: head = (head - 1 + capacity) % capacity).
  • "Given a binary tree, return its level order traversal." -> Standard BFS using a queue.

    • Common Mistakes

    Warning: 1. Circular Decrement Underflow: Decrementing indices in circular structures can go negative (e.g. head - 1). To avoid out of bounds, always add capacity before modulo: (head - 1 + capacity) % capacity.
    > 2. Queue Resizing Pitfalls: In python, using a list ([]) as a queue. list.pop(0) is O(N) because all other elements must slide forward. Always use collections.deque for O(1) operations.

    7. Summary

  • Deques: Support O(1) front and back updates.
  • Index Wrapping: (index + 1) % capacity wraps pointers cleanly.
  • Graphing: FIFO Queues are the core structure for layer-by-layer BFS traversals.

    • 8. Quiz

    Question 1: Why is Python's list.pop(0) slow for queue implementations? Answer: A Python list is backed by a contiguous array. Removing the element at index 0 requires copying and shifting all remaining N-1 elements forward by 1 index, taking O(N) time.
    Question 2: What is the full condition for a circular queue if we track indices without a size variable? Answer: (rear + 1) % capacity == front. This means the slot immediately succeeding the rear index is currently occupied by the front element.
    Question 3: How does the Work-Stealing scheduler use Deques to avoid lock contention? Answer: The primary thread pushes and pops tasks from the front of its Deque. Stealer threads steal tasks from the back of the Deque. Since updates happen at opposite ends, they rarely collide, minimizing lock sync operations.
    Question 4: True or False: std::deque in C++ guarantees that elements are stored contiguously in memory. Answer: False. Unlike vectors, C++ std::deque is implemented as a map of fixed-size chunks, offering O(1) insertion at ends but sacrificing strict contiguous layout memory.
    Question 5: What is the output of Front() in a Circular Queue of size 3 after enQueue(1), enQueue(2), deQueue(), enQueue(3)? Answer: 2. The first element 1 was dequeued, leaving 2 at the front of the queue.