CHAPTER 05 · Queue & Deque

Queue and Deque

A queue serves in arrival order. New elements join at the back, and only the element at the front can leave, so the element removed is always the one that has waited longest. That rule is called FIFO, first in, first out. A deque loosens it and allows insertion and removal at both ends.

§01

Intuition: a queue at a shop, and what it guarantees

A stack serves the most recent first. A queue serves the earliest first.

The stack in the previous chapter always serves the most recent item first. Now imagine a print shop with one printer. If it always printed the newest file first, then as long as new jobs keep arriving, the oldest file would never be printed. Computer science calls that starvation. Print jobs, food orders, support tickets, and message systems do not want the most recent first. They want the earliest first.

The structure built for that order is the queue. Think of a queue at a shop: new customers join at the back (rear), and the clerk only serves the person at the front. Nobody can move past anyone else, so the person served is always the one who has waited longest. That is the whole contract, and it has a name: FIFO (First In, First Out). Three rules follow from it:

RULE 01

Two ends, two jobs

enqueue adds at the back. dequeue removes at the front. That single split is the difference from a stack, where both operations act on the same end.

RULE 02

⏱️ First in, first out

The order of arrival is the order of service. No element can be overtaken, so nothing waits forever.

RULE 03

No access in the middle

A queue offers no operation to read or change an element in the middle. As with the stack, a smaller set of abilities is what keeps every operation O(1).

Where queues appear

Task scheduling in an operating system, printer job queues, and message systems such as Kafka and RabbitMQ, where requests wait in a queue and the backend consumes them at its own rate. Queues also drive breadth-first search (BFS) on trees (chapter 7) and graphs (chapter 12): the queue is what makes BFS finish one level before starting the next, and that ordering is the reason BFS finds a path with the fewest edges in an unweighted graph. BFS itself comes later; here you only need the queue.

§02

In memory: from a wasteful array to a circular queue

Both ends of a queue must be O(1). A plain array cannot do that, and the modulo operator is what fixes it.

Storing a queue in a plain array causes a problem straight away. Adding at the back is what arrays are good at: append is O(1). Removing at the front is the operation the array chapter warned about: every remaining element moves one position left, so a dequeue costs O(n), and it costs more as the queue gets longer. You could refuse to move anything, but then the slots freed at the front are never used again. Three designs, side by side:

One array of 4 slots. The queue [2, 7, 9] removes 2, then adds 12. Three designs, three outcomes.

Design 1 · Shiftdequeue O(n)

frontrear

122

·3

When 2 leaves, every element after it moves one slot to the left, so the front stays at index 0. This is the front deletion from the array chapter. It is correct, but every dequeue moves the whole rest of the queue: O(n), and it gets worse as the queue gets longer.

Design 2 · Move frontdequeue O(1), wastes space

front

✕0

123

Nothing moves. front simply steps right, so dequeue becomes O(1). But slot 0 is now dead space that can never be used again, and after 12 is written into slot 3 the next write position is 4, which is past the end. A long-running service would keep growing the array while holding only three elements.

Design 3 · Wrap arounddequeue O(1), no waste

rearfront

120

·1

Design 2 plus one rule: every index is taken modulo the capacity. The picture is one step further along — 7 and 9 sit in slots 2 and 3, and 2 has just left slot 1. The next write position was 4, and 4 % 4 = 0, so 12 went into slot 0, reusing the space a dequeue had freed. The straight line behaves like a circle: no element moves and no slot is wasted. This is the circular queue.

Design 3 is the circular queue, also called a ring buffer in production code. The array is still a straight line in memory, but every index calculation ends with % capacity, which makes the line behave logically like a circle. front consumes from one side, rear wraps around and refills from the other, and as long as the queue is not full there is always a free slot. RingLab in §03 lets you turn the circle yourself.

ANOTHER ROUTE

A linked queue: out at the head, in at the tail

Keep two pointers, head and tail. Dequeue unlinks the head node (O(1)); enqueue links a new node after tail (O(1)). Why not the other way around? Removing the last node of a singly linked list means finding its predecessor, which is O(n), while removing at the head and inserting at the tail need no traversal. The same rule as always: use the end that costs nothing. A linked queue never resizes and never fills up. The price is one pointer per element and poor cache behavior.

THE GENERAL FORM

The deque: both ends open

A deque (double-ended queue, pronounced “deck”) removes one more restriction: you can insert and remove at both ends, and all four operations are O(1). Use one end only and it behaves as a stack; add at one end and remove at the other and it behaves as a queue. The monotonic deque in §06 needs both ends at the same time, which is why it must be a deque.

Ring buffers in production

Packet buffers in network drivers, sample buffers in audio devices, fixed-size log buffers, and the core of the LMAX Disruptor trading framework are all ring buffers. The reason is the same every time: a fixed-length array plus two wrapping indices means no allocation, no element ever moves, and the memory touched stays close together. A producer and a consumer each follow their own index.

§03

Core operations: all O(1), and how the indices wrap

A complexity table, RingLab, and the answer to: does front == rear mean full or empty?

Operation	Meaning	Cost	Why
enqueue(x)	Add x at the back	O(1)	Write into the slot rear points at (or link after tail), then move the index one step
dequeue()	Remove the front element	O(1)	A circular queue only moves front; a linked queue unlinks the head node. Nothing is copied
peek()	Read the front without removing	O(1)	Read the slot front points at, or the head node
isEmpty() / size()	Empty test and count	O(1)	Compare the two indices, or read the counter
Deque, both ends	Insert and remove at either end	O(1)	In a circular array both indices can move forward and backward; in a doubly linked list both ends have a handle
Read or search the middle	Not provided	O(n)	A queue does not offer it. Use an array when you need random access

Turn the ring a few times and watch three things. First, a dequeue moves no element at all. Second, what rear does when it reaches the last slot. Third, why full and empty end up looking identical, and the two ways to tell them apart:

RingLab — how the modulo makes an array behave like a circle

A circular array of 8 slots. front (green) is the position of the next element to leave. rear (yellow) is the position where the next element will be written. Right now front == rear, and the queue is empty.

queue []

Full or empty? The classic circular queue problem

Empty means front has caught up with rear. Full means rear has travelled a full circle and caught up with front. In both cases front == rear, so the indices alone cannot tell you which one it is. The design has to resolve this, and there are two standard answers. Scheme A keeps one slot permanently empty: allocate k + 1 slots and treat (rear + 1) % cap == front as full. It needs no extra variable and costs one slot. Scheme B keeps a size counter: empty is size == 0, full is size == cap. Every slot is usable, and every enqueue and dequeue updates the counter. Both are correct; the implementation in §04 uses scheme A, and RingLab lets you switch between them.

§04

Build one: a circular queue (this is LC 622)

Everything RingLab does, written as code you can submit.

The class below is exactly the solution to LeetCode 622, Design Circular Queue: a fixed-length array, a front and a rear index, and the modulo operator to wrap around. It uses scheme A, keeping one slot empty, which is why the constructor allocates k + 1 slots. Every line matches an action in RingLab:

my_circular_queue.py

1class MyCircularQueue:

2 def __init__(self, k: int):

3 self.data = [0] * (k + 1) # one extra slot: it stays empty to tell full from empty

4 self.front = 0 # front: position of the next element to leave

5 self.rear = 0 # rear: position where the next element is written

7 def enQueue(self, value: int) -> bool:

8 if self.isFull():

9 return False

10 self.data[self.rear] = value

11 self.rear = (self.rear + 1) % len(self.data) # modulo: wrap back to 0

12 return True

14 def deQueue(self) -> bool:

15 if self.isEmpty():

16 return False

17 self.front = (self.front + 1) % len(self.data) # one index moves, nothing else

18 return True

20 def Front(self) -> int:

21 return -1 if self.isEmpty() else self.data[self.front]

23 def Rear(self) -> int: # the last element sits one slot before rear

24 if self.isEmpty():

25 return -1

26 return self.data[(self.rear - 1) % len(self.data)] # in Python this is never negative

28 def isEmpty(self) -> bool:

29 return self.front == self.rear

31 def isFull(self) -> bool:

32 return (self.rear + 1) % len(self.data) == self.front

Detail: in Python -1 % 8 == 7, because the result takes the sign of the divisor. There is no need to add the length first the way Java and JavaScript do. If you write in more than one language, (i - 1 + n) % n is safe everywhere.

The linked queue is worth writing once as well. It is the form a queue usually takes inside the BFS code of chapter 7, and it hides one boundary case that interviews ask about: resetting tail.

linked_queue.py

1class Node:

2 def __init__(self, val):

3 self.val = val

4 self.next = None

6class LinkedQueue:

7 def __init__(self):

8 self.head = None # front: the end elements leave from

9 self.tail = None # back: the end elements enter at

10 self.size = 0

12 def offer(self, x): # enqueue: link after tail, O(1)

13 n = Node(x)

14 if self.tail is None:

15 self.head = self.tail = n # empty queue: both ends point at it

16 else:

17 self.tail.next = n

18 self.tail = n

19 self.size += 1

21 def poll(self): # dequeue: unlink head, O(1)

22 if self.head is None:

23 raise IndexError("queue is empty")

24 v = self.head.val

25 self.head = self.head.next

26 if self.head is None: # last element removed: reset tail too!

27 self.tail = None

28 self.size -= 1

29 return v

Why out at the head and in at the tail?

In a singly linked list, removing at the head is O(1), inserting at the tail is O(1) when you keep a tail pointer, and removing at the tail is O(n) because you have to find the predecessor. So dequeue must be at the head and enqueue must be at the tail. Turn the two around and one of them becomes O(n). It is the same reasoning as the array stack keeping its top at the end and the linked stack keeping its top at the head: use the end that costs nothing.

§05

Three languages: JavaScript has no queue type

Java and Python both ship one. JavaScript does not, so you build it.

The queue is the structure where the three standard libraries differ the most. Java and Python both provide a deque you can use directly. JavaScript provides nothing: Array.prototype.shift() looks like a dequeue, but it removes the first element and shifts the rest, which is O(n) in general. One language at a time:

queue_basics.py

1from collections import deque

3q = deque()

4q.append(1) # enqueue at the right end

5q.append(2)

6head = q[0] # look at the front -> 1 (both ends are O(1))

7x = q.popleft() # dequeue from the left end -> 1, O(1)

9# both ends are open

10q.appendleft(0) # insert at the left, O(1)

11q.pop() # remove at the right, O(1)

13# do not use a list as a queue

14bad = [1, 2, 3]

15bad.pop(0) # O(n): the first item leaves, everything else shifts left

17# queue.Queue is a different class: it passes items between threads and adds

18# locking. It is not the data structure interview problems mean by "queue".

How deque is built: a doubly linked list of blocks, where each block is a small array holding up to 64 elements. Both ends are O(1), and the memory is more compact than one node per element. The cost is that reading q[i] in the middle becomes O(n). list.pop(0) is the most common performance mistake in Python interview code.

Operation	Java (ArrayDeque)	Python (deque)	JavaScript (head index)	Complexity
Enqueue (back)	`q.offer(x)`	`q.append(x)`	`q.push(x)`	O(1) amortized
Dequeue (front)	`q.poll()`	`q.popleft()`	`q[head++]`	O(1)
Look at the front	`q.peek()`	`q[0]`	`q[head]`	O(1)
Insert at the front	`q.offerFirst(x)`	`q.appendleft(x)`	linked queue or two stacks	O(1)
Remove from the back	`q.pollLast()`	`q.pop()`	`q.pop()`	O(1)
Avoid	`LinkedList` (poor cache behavior)	`list.pop(0)`	`arr.shift()`	O(n)

§06

Patterns, and the monotonic deque

★ Interview core

The amortized analysis of a queue built from two stacks, and the standard solution for sliding window extremes.

PATTERN 01

A queue from two stacks

Two LIFO structures make one FIFO structure, because reversing twice restores the original order. It is the standard example for amortized analysis. LC 232, walkthrough A.

PATTERN 02

Monotonic deque

The maximum or minimum of a sliding window, available in O(1) at any moment. Two rules: drop weaker candidates at the back, drop expired indices at the front. LC 239, 1438, 862; walkthrough B.

PATTERN 03

Other uses of a deque

Palindrome checking (compare the two ends, then move inward), 0-1 BFS (an edge of weight 0 goes to the front, an edge of weight 1 goes to the back; chapter 12), and work-stealing schedulers (a thread uses its own end as a stack while other threads take tasks from the far end).

A monotonic deque is a deque whose contents stay in sorted order; the order is kept by removing elements before each insertion. Take the maximum of a sliding window as the goal. The deque holds indices, not values, and the values at those indices decrease from front to back. Two rules keep that true, one at each end:

RULE 01 · BACK

Drop weaker candidates

Before index i enters, remove from the back every index whose value is not greater than nums[i]. Each of them is smaller than the new element and also leaves the window earlier, so none of them can ever be a maximum again. Indices with an equal value are removed too, so the values in the deque strictly decrease.

RULE 02 · FRONT

Drop the expired index

When the front index falls outside the window, remove it from the front. Only the front can expire, because it is the oldest index in the deque, so one check per step is enough.

RESULT

The front is the answer

With both rules maintained, the front is always the index of the maximum of the current window, and reading it is O(1). One end drops weaker candidates and the other drops expired indices, so the structure has to be a deque.

The code has a while loop inside a for loop, which makes many learners assume O(n²). It is not. Each index enters the deque exactly once and leaves at most once, from either end, so the total number of deque operations over the whole array is at most 2n. The running time is O(n), and the space is O(k) because the deque never holds more indices than the window contains.

Monotonic stack and monotonic deque, side by side

Both reach O(n) the same way: an element that can never be the answer is discarded early. The difference is which end elements leave from. A monotonic stack answers questions such as “next greater element”, and an element’s answer is settled at the moment it is popped. A monotonic deque answers questions about a window, and it adds a second rule: the index at the front expires once the window moves past it. One end is enough for the stack; the window needs both.

Walkthrough A

LC 232 · Implement Queue using Stacks

EASY

The problem: implement push, pop, peek, and empty for a queue, using only stacks. The idea: a stack reverses the order, so reverse it a second time. The naive version: on every push, use the second stack to place the new element at the bottom, which makes push O(n). The better version: do not move anything until you have to. The in stack only accepts pushes, the out stack only serves pops, and in is emptied into out only when out is empty:

LC 232 · two stacks, one frame at a time

empty

in · push only

empty

out · pop only

Three rules only: every push goes into in; every pop and peek reads out; and in is emptied into out only when out is empty.

1 / 9

lc232_queue_with_stacks.py

1class MyQueue:

2 def __init__(self):

3 self.stk_in = [] # push only

4 self.stk_out = [] # pop only

6 def push(self, x: int) -> None:

7 self.stk_in.append(x) # O(1)

9 def pop(self) -> int:

10 self._transfer()

11 return self.stk_out.pop()

13 def peek(self) -> int:

14 self._transfer()

15 return self.stk_out[-1]

17 def empty(self) -> bool:

18 return not self.stk_in and not self.stk_out

20 def _transfer(self):

21 if self.stk_out: # out still holds older elements: do not transfer

22 return

23 while self.stk_in: # out is empty: move all of in across

24 self.stk_out.append(self.stk_in.pop()) # reversing twice restores order

Why pop is O(1) amortized

A single pop can be O(n), when it triggers the transfer. Count elements instead of operations. In its whole life an element is moved at most 4 times: into in, out of in, into out, out of out. Each of those happens at most once, because the transfer never runs while out is not empty, so no element is ever transferred twice. n operations therefore cost at most 4n moves, which averages to O(1) per operation. Array growth (1 + 2 + 4 + … < 2n) and the monotonic stack (each element pushed once and popped once, at most 2n) are counted the same way: amortized analysis spreads the cost of a rare expensive step over all the operations.

Complexity and follow-up questions

push is O(1); pop and peek are O(1) amortized; space is O(n). First follow-up: why must the transfer be skipped while out is not empty? Because the elements moved across would land on top of the older ones, and the order would immediately be wrong. Second follow-up: what about a stack built from queues? That is LC 225, in the problem set: after each push, move the n − 1 earlier elements to the back, which makes push O(n) and pop O(1). The two problems mirror each other.

Walkthrough B

LC 239 · Sliding Window Maximum

HARDMonotonic deque

The problem: a window of length k slides from left to right; report the maximum at every position. Brute force: scan k elements per window, O(nk), which is too slow at n = 10⁵. Why it can be improved: two neighboring windows share k − 1 elements, so brute force scans almost the same stretch again and again. It also throws information away: once an element has a larger element to its right, it can never be the maximum of any later window. Those elements do not need to be kept. Keep only the candidates that are still possible, in decreasing order, in a deque. That is a monotonic deque:

LC 239 · Monotonic deque (highlighted = in the deque, grey = outside the window)

nums = [5,3,1,4,2,6], k = 3. Brute force scans k elements in every window: O(nk). A monotonic deque reads the window maximum in O(1) instead. The deque holds indices, and the values at those indices decrease from front to back. Highlighted = currently in the deque.

1 / 9

lc239_sliding_window_max.py

1from collections import deque

3class Solution:

4 def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:

5 dq = deque() # indices; their values decrease from front to back

6 ans = []

7 for i, v in enumerate(nums):

8 # (1) drop every index at the back whose value is not greater than v

9 while dq and nums[dq[-1]] <= v:

10 dq.pop()

11 dq.append(i) # (2) i enters at the back

12 # (3) the front index has left the window -> remove it

13 if dq[0] <= i - k:

14 dq.popleft()

15 # (4) once the window is complete, the front is the maximum

16 if i >= k - 1:

17 ans.append(nums[dq[0]])

18 return ans

Complexity and follow-up questions

Time O(n): each index enters the deque once and leaves at most once, so there are at most 2n deque operations in total, even though the code has a while loop inside a for loop. Space O(k). First follow-up: the minimum of the window? Reverse every comparison and keep the values increasing. Second follow-up: the maximum and the minimum at the same time? Run two monotonic deques over the same window (LC 1438, in the problem set). Third follow-up: why store indices instead of values? Because the expiry test needs a position (front ≤ i − k). An index gives you the value, and a value does not give you the index — the same reason a monotonic stack stores indices.

§07

Problem set: 8 queue problems

Selected

Simulation, then design, then monotonic deques, easy to hard. Think for 30 seconds before you open the hint.

LC 933Number of Recent CallsQueueTime windowEASY

LC 225Implement Stack using QueuesQueueRotationEASY

LC 622Design Circular QueueCircular queueModuloMEDIUM

LC 641Design Circular DequeCircular queueDequeMEDIUM

LC 946Validate Stack SequencesStackSimulationGreedyMEDIUM

LC 649Dota2 SenateQueueGreedyRound-basedMEDIUM

LC 1438Longest Continuous Subarray With Absolute Diff Less Than or Equal to LimitSliding windowTwo monotonic dequesMEDIUM

LC 862Shortest Subarray with Sum at Least KPrefix sumMonotonic dequeHARD

§08

Quiz

✎ Quiz

All 7 correct turns this chapter green.

QUESTION 01 / 7

What does FIFO (First In, First Out) mean for a queue?

QUESTION 02 / 7

A circular queue runs rear = (rear + 1) % capacity on enqueue. What is the modulo for?

QUESTION 03 / 7

In a circular queue, front == rear. Is the queue full or empty?

QUESTION 04 / 7

What is the cost of inserting and removing at both ends of a deque?

QUESTION 05 / 7

You need a queue in JavaScript. Which of these keep dequeue at O(1)? (select all)

QUESTION 06 / 7

In a monotonic deque (take sliding window maximum, LC 239), what does the deque hold?

QUESTION 07 / 7

In the two-stack queue (LC 232), each element is moved at most 4 times in its whole life (into in, out of in, into out, out of out). So the amortized cost of one dequeue is O(___)?

What to take away from this chapter

A queue splits the two ends: enqueue at the back, dequeue at the front. The element removed is always the one that has waited longest, which is what FIFO means. A deque opens both ends and can act as a stack or as a queue.
A plain array queue forces a bad choice: shift on every dequeue (O(n)), or leave the freed front slots unused forever. The circular queue removes both problems by taking every index % cap. front == rear then means either full or empty, so the design resolves it by keeping one slot empty or by keeping a size counter.
What to use: ArrayDeque in Java (Queue is an interface; LinkedList implements it too but is slower, and ArrayDeque rejects null); collections.deque in Python (not list.pop(0), and queue.Queue is a separate class for threads). JavaScript has no queue type and shift() is O(n) in general: use a head index, two stacks, or a linked queue.
A queue from two stacks: reversing twice restores the arrival order, and each element is moved at most 4 times in its whole life, so pop is O(1) amortized — the same accounting as array growth and the monotonic stack.
A monotonic deque holds indices whose values decrease from front to back. Remove from the back every index whose value is not greater than the new element, and remove the front index once it has left the window. The front is then always the maximum of the current window, and the whole scan is O(n), because each index enters once and leaves at most once.