Data Structures
Queue & Deque
Difficulty: Beginner
BFS visits a graph one frontier at a time, and the trick that makes that work is a queue: nodes are added in the order they are discovered and pulled out in the same order, level by level. Queue & Deque captures that First In, First Out...
Queue & Deque
BFS visits a graph one frontier at a time, and the trick that makes that work is a queue: nodes are added in the order they are discovered and pulled out in the same order, level by level. Queue & Deque captures that First In, First Out discipline as a reusable abstraction, then extends it to a double-ended variant that pops up surprisingly often in sliding-window problems.
In this lesson, you will implement enqueue, dequeue, front, and isEmpty using both a linked list and an array, then see why a naive array queue wastes space and how a circular queue with two index pointers fixes that with O(1) operations. You will also build a deque that supports inserts and removes at both ends, the structure underneath the monotonic-deque pattern that solves sliding-window-maximum in linear time.
In Stack (LIFO), you implemented push and pop from the same end and saw how the choice of array versus linked list affected the worst-case bound. A queue uses the same two storage options but pulls from the opposite end, which is what forces the circular buffer trick when you back it with an array.
With a queue in your toolkit, Hash Map (Dictionary) Basics introduces the most-used data structure in real-world code: a key-value store that answers lookups in expected O(1).
Prerequisites:
Stack (LIFO)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain FIFO with a concrete real-world example and contrast it with LIFO.
Implement enqueue/dequeue/front/isEmpty safely using both array-based and linked-list-based approaches.
Explain why a naive array queue wastes space and how a circular queue solves this with O(1) operations.
Implement a Deque with addFront, addRear, removeFront, and removeRear operations.
Identify queue applications: BFS, task scheduling, print queues, and sliding window.
State time and space complexity for queue and deque operations.
Why This Matters
01
Queues model first-come-first-served behavior -- from print queues and task schedulers to message brokers in distributed systems.
02
BFS (Breadth-First Search) is built on queues, making them essential for shortest-path problems on unweighted graphs, level-order tree traversal, and more.
03
Deques combine stack and queue powers in one structure; they enable the sliding-window-maximum pattern (monotonic deque), which appears frequently in interviews.
Key Terms
7 terms you'll encounter in this lesson
FIFO
First In, First Out -- the element that has been waiting the longest is the first one removed, like a line at a store.
Enqueue
Adding an element to the rear (back) of the queue. Also called 'offer' or 'add' in some languages.
Dequeue
Removing and returning the element at the front of the queue. Also called 'poll' or 'remove' in some languages.
Front / Peek
Reading the element at the front of the queue without removing it -- a non-destructive observation.
Circular Queue
A fixed-size queue implementation where the array wraps around using modular arithmetic, avoiding the O(n) cost of shifting elements.
Deque (Double-Ended Queue)
A generalized queue that supports insertion and removal at both the front and rear ends in O(1) time.
Underflow
Attempting to dequeue or peek from an empty queue -- an error condition that must be handled explicitly.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Dequeue removes from the back"
Dequeue removes from the front (FIFO). The element that was added first (the one waiting longest) is the one that gets removed. The back/rear is where new elements are added.
"Using array.shift() is fine for a queue"
In JavaScript, Array.shift() removes the first element but shifts ALL remaining elements left -- that's O(n). For a proper O(1) queue, use a circular buffer, a linked list, or a two-pointer approach. Python's collections.deque has O(1) popleft().
"A deque is just two stacks glued together"
While you CAN implement a queue using two stacks, a deque is a distinct data structure that natively supports O(1) operations at both ends. Two-stack queues have amortized O(1) dequeue but O(n) worst-case per dequeue.
"Circular queues waste space because they have a fixed size"
Circular queues use their fixed space efficiently -- they reuse slots that were freed by dequeue operations. A naive linear array queue is what wastes space: dequeued slots at the front are never reused.