Algo VisualizedStart learning

Queue (FIFO) & Deque

Print jobs, web requests, messages between services: anything that must be handled in arrival order waits in a queue. It is also the engine of breadth-first search, so you will meet it again in every graph lesson.

beginner⏱ 8 min read

←Builds on

3Stack (LIFO) & Expression EvaluationA queue is the stack's twin that removes from the other end: FIFO instead of LIFO.3Linked ListsA queue can be a linked list with a head and a tail pointer.3Monotonic StackA monotonic deque gives the sliding window maximum: the same idea, popping at both ends.

Leads to→

5Binary Heap & Priority QueueA priority queue is a queue where the smallest leaves first instead of the oldest.6Breadth-First Search (BFS)BFS is a queue put to work: the FIFO order is what makes the wave.
1Learn2Play3Check4Practice
01

Learn

The idea, the mechanics and the cost.

01First in, first out

A queue is a line at a shop counter. New elements join at the back; elements leave from the front. The one that waited longest is served first: "First In, First Out" (FIFO).

In C++: #include <queue> and queue<int> q;. The functions mirror the stack:

  • push(x): add x at the back;
  • pop(): remove the front element (returns nothing);
  • front() / back(): read the oldest / newest element;
  • size(), empty().

All of them are O(1). As with the stack, front() or pop() on an empty queue is undefined behaviour.

FIFO: First In, First Out372229pop() / front()push(16)frontback

02Same commands, opposite answer

Run the stack lecture program on a queue: push 37, 22, 29, then pop(). A stack would remove 29, the newest. A queue removes 37, the oldest, and front() now shows 22.

That single difference decides which structure an algorithm needs:

  • a stack goes deep first: the newest task is handled first (depth-first search, undo, recursion);
  • a queue goes wide first: tasks are handled in the order they appeared (breadth-first search, scheduling, buffering).

In BFS the queue holds the vertices discovered but not yet processed. Because they leave in arrival order, vertices are processed level by level, which is exactly why BFS finds shortest paths in unweighted graphs.

push 37, 22, 29stack: pop() takes the newest37222929queue: pop() takes the oldest37222937

03The deque: both ends at once

A deque (double-ended queue, #include <deque>) allows push_front, push_back, pop_front and pop_back, all in O(1), plus indexing d[i]. It can act as a stack, a queue, or both at once.

Two classic uses:

  • sliding window minimum: keep a deque of indices with increasing values; drop the front when it leaves the window and drop the back while it is larger than the new element. That is a monotonic stack with an exit at the other end.
  • 0-1 BFS: on graphs with edge weights 0 and 1, push a vertex to the front for a 0-edge and to the back for a 1-edge.

Under the hood, std::queue and std::stack are thin wrappers around a deque by default.

deque: add and remove at both ends in O(1)5381push_frontpop_frontpush_backpop_backused for: sliding window minimum, 0-1 BFS

Cost at a glance

push / pop / front / backO(1)
Deque at either endO(1)
Search insideO(n)

Remember

  1. A queue adds at the back and removes from the front, so elements leave in the order they arrived.
  2. A stack processes the newest element first (depth), a queue the oldest (breadth); that is the difference between DFS and BFS.
  3. A deque supports O(1) insertion and removal at both ends and powers sliding window and 0-1 BFS tricks.
02

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Compare with the stack lesson: the same commands, but pop now removes 37, the oldest element. Try your own commands, including back.

Interactive visualizerfocus here, then space ← →
✎ Your inputUp to 14 commands: push N (or just N), pop, front, back, size, empty.

Queue q (FIFO: First In, First Out)

(empty)
Console output (cout)
A queue is First In, First Out: you add at the back and remove from the front. The mirror image of a stack.

Pseudocode

 1 queue<int> q; 2 q.push(x);    // join at the BACK 3 q.pop();      // leave from the FRONT 4 q.front();    // read the oldest element 5 q.back();     // read the newest element 6 q.size();     // how many are waiting 7 q.empty();    // true / false
1 / 1
03

Check

Three questions. Pick an answer to see why.

Q1

Empty queue: push 4, push 7, push 1, pop, push 9. What is front()?

Q2

BFS explores a graph level by level. Which property of the queue makes that happen?

Q3

You need to add tasks at both ends and take them from both ends in O(1). What do you use?

04

Practice

Real problems to lock it in, easiest first.

LeetCodeNumber of Recent Calls beginner↗LeetCodeImplement Queue using Stacks beginner↗CSESJosephus Problem I intermediate↗LeetCodeSliding Window Maximum advanced↗