DataslopeQueues and Deques
Learn FIFO queues, std::queue, std::deque, producer-consumer patterns, priority queue teasers, and queue-based interview patterns
A queue is a first in, first out data structure. The oldest item waiting in line is served first. Queues model printers, web requests, breadth-first search frontiers, and producer-consumer pipelines.
The queue ADT
| Operation | Meaning |
|---|---|
enqueue / push | Add an item to the back |
dequeue / pop | Remove the front item |
front | Read the next item to leave |
empty | Check whether the queue has no items |
std::queue<T>
std::queue is an adapter. By default it uses std::deque, exposing only FIFO operations.
Producer-consumer style
One part of a program can produce work while another consumes it in the same order.
std::deque<T>
A deque is a double-ended queue. It supports O(1) push and pop at both the front and the back. It is the unsung hero of competitive C++ because it handles queue and stack-like workloads well.
Unlike std::vector, popping from the front of a deque does not shift every remaining element.
Queue and deque costs
std::queue backed by std::deque gives O(1) push, pop, front, and empty. std::deque also gives O(1) push/pop at both ends.
Vector front-pop versus deque front-pop
This example shows the operation shape: vector erases from the front by shifting, while deque simply removes its first element.
Priority queues teaser
std::priority_queue is not FIFO. It returns the highest-priority item first and is usually implemented with a heap. We will cover it later in the heaps section.
Breadth-first flavor
Queues also power breadth-first search: visit a node, enqueue its neighbors, then process nodes in discovery order.
Choose deque before list for queue ends
A linked list can push and pop at ends, but a deque usually has better locality and lower allocation overhead.
Practice: first non-repeating character in a stream
Given a stream of lowercase characters, after each character print the first character so far with frequency one, or # if none exists. Use a queue plus a frequency table.
Practice: reverse the first k elements
Given queue 1,2,3,4,5 and k=3, reverse the first three elements and keep the rest in order. Print the resulting queue in order.
Check your understanding
Which phrase describes a queue?
Last in, first out
First in, first out
Highest value, first out
Random element, first out
Why is std::deque often preferred over std::list for queue-like work?
It supports efficient end operations with better locality and fewer per-element allocations.
It makes every operation O(log n).
It automatically removes duplicates.
It cannot grow dynamically.
What is the complexity of removing the front element from a std::vector with erase(begin()) compared with std::deque::pop_front()?
Both are always O(1).
Vector front erase is O(n), while deque pop_front is O(1).
Vector front erase is O(log n), while deque pop_front is O(n).
Both are O(n^2).