Move it step by step
Instruction list (runs left to right)
- enqueue 3
- enqueue 7
- enqueue 5
- dequeue
- enqueue 9
- dequeue
- dequeue
- dequeue
- just pushed/enqueued
- value out
- empty slot
- error
- front is the head, rear is the last position
Step 1 of 9Instructions run: 0Values inside: 0
Running 8 instructions, one by one, on an empty queue. It holds up to 5 values.
The pseudocode line currently running
- 1enqueue(x)
- 2if full, error (overflow)
- 3place x at the back, and make that spot rear
- 4dequeue()
- 5if empty, error (nothing to return)
- 6return the value at front, then make the next value front
Change the example
Try predicting
You're on step 1.
What comes out on the next dequeue?
What you'll learn
- The flow where the first value in is the first one out
- When each of the two markers, front and rear, moves
Prerequisites
- Arrays and indices (numbering that starts at 0)
- A stack's push and pop
How a queue works
A queue is a container where you join values to the back of a line, and take them out from the front of the line. The value that went in first comes out first, so it's called first-in-first-out (FIFO).
Joining the line is called enqueue, and taking a value out is called dequeue. The position at the head is called front, and the position at the tail is called rear.
Steps, with an example
- 1For enqueue, check that it isn't full, then place the value behind rear
- 2For dequeue, check that it isn't empty, then return the value at front
- 3After returning it, make the next value the new front
- 4Treat a dequeue when empty, and an enqueue when full, as errors
| Instruction | Value out | Contents (front to back) |
|---|---|---|
| enqueue 3 | None | [3] |
| enqueue 7 | None | [3, 7] |
| enqueue 5 | None | [3, 7, 5] |
| dequeue | 3 | [7, 5] |
| enqueue 9 | None | [7, 5, 9] |
| dequeue | 7 | [5, 9] |
| dequeue | 5 | [9] |
| dequeue | 9 | [] |
Cost and complexity
| Operation | Cost | Complexity |
|---|---|---|
| enqueue | 1 step (just place it at the back) | O(1) |
| dequeue | 1 step (just move front forward by one) | O(1) |
| Removing the front of an array directly | n steps (shift the rest one spot to the left) | O(n) |
For clarity, the figure shifts the remaining values left after one comes out. A real queue doesn't shift anything; it just moves the front position forward by one, so dequeue only costs a single step.
When to use it
Good fit
- When you want to process things in the order they arrived (a print queue, taking orders)
- When you want to explore nearby things first (breadth-first search)
Not a good fit
- When you want to process the most recent item first (use a stack instead)
- Repeatedly calling pop(0) on a Python list (it's slow because it shifts everything each time; use deque instead)
Code
Pseudocode
- 1enqueue(x)
- 2if full, error (overflow)
- 3place x at the back, and make that spot rear
- 4dequeue()
- 5if empty, error (nothing to return)
- 6return the value at front, then make the next value front
Working code
▶ Press “Run” to see the result here
Edit the Python or JavaScript and press “Run” to see the result right away. Java is read-only here.
FAQ
- What's the difference between a stack and a queue?
- They're filled the same way; they differ in which end values come out from. A stack comes out from the last value in, a queue from the first.
- Why is list.pop(0) slow in Python?
- Because after removing the front item, everything else has to shift one spot to the left. collections.deque's popleft doesn't shift anything, so the cost stays the same no matter how many items there are.
