DSA · Linear structures

The queue that never moves an element

Q: How would you implement a queue using two stacks?

Keep an in stack and an out stack. enqueue pushes onto in . dequeue pops from out , and if out is empty you first pour all of in into it, which reverses the order and puts the oldest element on top. Each element changes stacks at most twice in its life, so dequeue is amortised O(1) even though one individual call can cost O(n). The common mistake is pouring back after every dequeue — then every operation is O(n).

Serve people in the order they arrived. Build that on a plain array and every dequeue drags the whole queue one slot left. One modulo operator removes the dragging, and opening the two doors a queue keeps shut turns it into a deque that answers sliding window maximum in a single pass.

Wrap front and rear around a 5-slot ring →

Naive arraydequeue shifts every survivor · O(n)

→

Circular queuefront and rear step mod 5 · O(1)

→

Dequeboth ends open · window maximum in one pass

01 The idea

Serve in the order people arrived

Stand in the queue at a railway ticket counter. You join at the back, the clerk serves the front, and nobody in the middle is ever touched. That is the whole contract of a queue: two ends, one direction of travel, no reordering. A print spooler works this way, so does the ready queue of processes waiting for the CPU, so does the frontier of a breadth-first search.

The interesting part is not the idea, it is the storage. A queue grows at one end and shrinks at the other, so the region it occupies inside an array keeps drifting to the right. Do nothing about that drift and you either run out of array while the front sits empty, or you pay to slide everything back. The fix is to stop thinking of the array as a line and start thinking of it as a ring, where slot 4 is followed by slot 0.

Add at the rear, remove from the front, never touch anything in between. The element that has waited longest is the one that leaves next.

FIFOFirst in, first out. The oldest element leaves next. A stack is the opposite, LIFO, which is why depth-first search uses a stack and breadth-first search uses a queue.

Front and rearfront is the index you read from, rear the index you last wrote to. A queue exposes only these two positions, so anything in the middle costs O(n) to reach.

Wrap-aroundWhen an index walks past the last slot it starts again at 0. (i + 1) % cap does that in one expression, and it is the only reason a fixed array can behave like a ring.

02 Worked example

Thirteen operations on a 5-slot ring

Capacity 5. The stream of values arriving is 9 4 6 2 8 3 5. The queue starts with front = 0, rear = −1 because nothing has been written yet, and size = 0. Every row below is one operation, except the first, which folds the five opening enqueues into a single line — thirteen operations in nine rows. The rose box is the slot that operation touched, and the note on the right gives the index arithmetic. The 3 that gets refused is retried later, once two dequeues have freed room for it. Watch rear walk off the end on the second enq 3 row — the one that succeeds — and front do the same on the last dequeue.

slot01234

start·····front 0 · rear −1 · size 0

enq ×5946289 4 6 2 8 · rear 0→4 · size 5 · full

enq 394628size 5 = capacity · refused · overflow

deq → 994628front 0→1 · size 4

deq → 4·4628front 1→2 · size 3

enq 33·628rear (4 + 1) % 5 = 0 · wraps

enq 535628rear 1 · size 5 · full again

deq → 635628front 2→3 · size 4

deq → 235·28front 3→4 · size 3

deq → 835··8front (4 + 1) % 5 = 0 · wraps

result35···queue is 3 5 · front 0 · rear 1 · 0 elements moved

A free slot is not a blank slot. After the first dequeue, 9 is still physically sitting in a[0] — the queue has only stopped counting it, and the next enqueue overwrites it. size is the one thing that knows which slots the queue actually owns.

Both indices walked off the end and came back to slot 0, and not one value was copied from one slot to another. All thirteen operations did constant work — including the sixth, which was refused in O(1) the moment size was seen to equal the capacity. That is the insight the code below encodes: instead of moving the data to fit a fixed window, move the window around the data.

03 The code

Shift the data, or move the indices

Both versions store the queue in one array of size cap and expose the same two operations. The naive one keeps the front pinned at index 0, which means every dequeue has to slide the survivors down. The circular one lets the front drift and brings it back with a modulo. Compare the two dequeue bodies: one contains a loop, the other does not, and that single difference is the whole lesson.

Naive array queue — dequeue shifts

n = 0                                # how many are storedenqueue(x):    if n == cap: return FULL    a[n] = x;  n = n + 1dequeue():    if n == 0: return EMPTY    x = a[0]    for i in 0 .. n-2: a[i] = a[i+1]   # slide    n = n - 1;  return x

Circular queue — indices wrap

front = 0;  rear = -1;  size = 0enqueue(x):    if size == cap: return FULL    rear = (rear + 1) % cap        # 4 -> 0    a[rear] = x;  size = size + 1dequeue():    if size == 0: return EMPTY    x = a[front]    front = (front + 1) % cap      # 4 -> 0    size = size - 1;  return x

Why the shift is the whole problem. In the trace, the five successful dequeues happened while the queue held 5, 4, 5, 4 and 3 elements, so the naive version would have copied 4 + 3 + 4 + 3 + 2 = 16 values to achieve exactly what the circular version did with five additions. One dequeue is O(n), so draining a queue of n elements is O(n²). On a million-element buffer a single dequeue copies a million values.

Why keep a size counter. Without it, full and empty are indistinguishable. In both states rear ends up sitting one step behind front, and the indices alone cannot tell you which of the two you are in. A counter answers isEmpty and isFull in O(1). The standard alternative is to keep one slot permanently unused so the two states can never collide — which means a capacity-5 array stores 4 elements.

Why a linked queue needs neither. Hold a head and a tail node pointer: enqueue links a new node after tail, dequeue unlinks head. Both are O(1) with no capacity and no modulo, and it grows instead of refusing work. You pay one pointer per element and lose the contiguous memory, so the fixed ring wins whenever you know the maximum size in advance.

The deque. A double-ended queue is the same ring with both doors open — push_front, push_back, pop_front, pop_back, every one O(1). To walk the front pointer backwards you write front = (front − 1 + cap) % cap. The + cap matters: in C, C++ and Java, −1 % 5 is −1, not 4.

05 Cheat sheet

Costs worth memorising

Operation	Cost	Note
enqueue, circular queue	`O(1)`	One modulo, one write, one increment. No element moves.
dequeue, circular queue	`O(1)`	front steps forward mod cap; the old value stays in its slot until overwritten.
dequeue, naive array queue	`O(n)`	Slides every survivor left. The lesson script pays 16 copies for 5 dequeues, and draining n elements is `O(n²)`.
peek front or rear	`O(1)`	One array read. Not the same as dequeue — it does not move front.
push_front / pop_back, deque	`O(1)`	(front − 1 + cap) % cap and (rear − 1 + cap) % cap. The + cap keeps the result non-negative.
search for a value	`O(n)`	A queue exposes two ends only. If you need to look inside, you picked the wrong structure.
space, array ring	`O(cap)`	Allocated up front, whether or not it is full. One allocation, contiguous, cache-friendly.
space, linked queue	`O(n)`	One node and one pointer per element, allocated on demand. No capacity limit.
sliding window maximum, deque	`O(n)`	Each index is pushed once and removed once, so the total deque work is linear in n and does not depend on k.
sliding window maximum, brute force	`O(n·k)`	Recomputes the maximum of every window from scratch. At n = 1,000,000 and k = 1,000 that is about a billion comparisons.

Modulo is the whole trick(i + 1) % cap is the only difference between an O(n) dequeue and an O(1) one. Nothing else about the class changes.

size is the source of truthFront and rear alone cannot separate full from empty. Keep a count, or sacrifice one slot — the two indices on their own will never tell you.

A deque is a supersetIt does everything a queue does and everything a stack does, at the same O(1) costs. In practice: collections.deque, ArrayDeque, std::deque.

06 Where & why

Queue, deque, or something else

A queue is not a fast structure, it is a fair one. Nothing about it beats a plain array on raw speed; what it buys you is the guarantee that whatever arrived first is served first, in constant time, with no scanning and no reordering. Choose it when arrival order is part of the correctness of your program, not when you merely want a list.

Reach for it when…

Arrival order is the rulePrint spooler, HTTP request queue, CPU ready queue, message broker. Anywhere jumping the line is a bug rather than an optimisation.

You are searching breadth-firstBFS on a graph or grid, level-order tree traversal, shortest path on unweighted edges. The frontier is a queue, and that FIFO order is exactly why BFS finds shortest paths.

A fixed buffer sits between producer and consumerAudio samples, keystrokes, network packets, log lines. A ring buffer of known capacity never allocates while it is running, which is why kernels and drivers use one.

A window slides and you need its best valueSliding window maximum or minimum, and any "best value in the last k items" question. You must drop from the front and from the back, so this one needs a deque.

Use something else when…

Situation	Better choice	Why
You need the largest or smallest item next, not the oldest	Priority queue / binary heap	`O(log n)` insert and extract keeps order by value. Scanning a queue for its maximum is `O(n)` every time.
You need the newest item first	Stack	Same `O(1)` costs, opposite discipline. DFS, undo history and expression parsing all want LIFO.
You need indexing, or search by value	Array or hash table	A queue exposes only its two ends, so reaching an arbitrary element costs `O(n)`.
The maximum size is unknown and can spike	Linked queue or a growable deque	A fixed ring refuses the enqueue when it is full. A linked queue grows instead of dropping work, at one pointer per element.

In real code you will call collections.deque in Python, ArrayDeque in Java or std::deque in C++, and all three already handle the wrap-around for you. Interviews still make you build the ring by hand, because (i + 1) % cap and the full-versus-empty test are precisely where people slip — and those same two lines are what a ring buffer inside a network driver is doing right now.

07 Interview questions

What interviewers actually ask

Eleven questions in the order an interview escalates: what it is, what it costs, why the naive version is slow, and then the deque follow-up that separates candidates who have only read about it.

What is a queue, and how is it different from a stack?

A queue is a linear collection with two ends: you add at the rear and remove from the front, so the element that has waited longest leaves next — first in, first out. A stack adds and removes at the same end, so the newest element leaves first. Both give O(1) insert and remove; the only difference is which end you take from, and that is why breadth-first search uses a queue and depth-first search uses a stack.

What are the queue operations, and what does each one cost?

enqueue adds at the rear, dequeue removes from the front, peek reads the front without removing it, and isEmpty / isFull answer size questions. On a circular array, or a linked list with a tail pointer, every one of them is O(1). Searching for a value is O(n), because a queue exposes only its two ends.

Why is dequeue O(n) if you just store the queue in a plain array?

Because you return a[0] and then have to slide every survivor one slot left to keep the front at index 0. In the lesson script, five dequeues copy 16 elements. The obvious alternative — leave the data alone and move a front index instead — fixes the copying but makes the queue drift right until it hits the end of the array while the freed slots at the front sit unreachable.

How does a circular queue fix that?

It stops moving the data and moves the indices instead. rear = (rear + 1) % cap on enqueue and front = (front + 1) % cap on dequeue, so whichever index walks past the last slot lands back on slot 0 and reuses the space the dequeues freed. Nothing is ever copied, so both operations are O(1) inside a fixed block of memory.

In a circular queue, how do you tell full apart from empty?

You cannot, from the indices alone — in both states rear ends up one step behind front, so you need one extra piece of information. The usual answer is a size counter: empty is size == 0, full is size == cap, both O(1). Another accepted answer is to keep one slot permanently unused so the two states can never produce the same index pair, which costs you one slot of capacity.

Array-based queue or linked-list queue — which would you pick?

If I know a sensible maximum size, the array ring: one allocation, contiguous memory, cache-friendly, and no surprise malloc in the middle of a hot loop. If the size is unbounded or spiky, the linked queue with head and tail pointers, because it grows instead of refusing the enqueue. The linked version pays one pointer per element and a likely cache miss on every hop.

What is a deque, and what does it give you that a queue does not?

A deque, short for double-ended queue, allows insert and remove at both ends — push_front, push_back, pop_front, pop_back, all O(1). So it can behave as a queue or as a stack, and it can do what neither can: drop stale elements from the front while also dropping useless ones from the back. On a fixed array the front index walks backwards with (front − 1 + cap) % cap; the + cap is there because −1 % 5 is −1 in C, C++ and Java, not 4.

How would you implement a queue using two stacks?

Keep an in stack and an out stack. enqueue pushes onto in. dequeue pops from out, and if out is empty you first pour all of in into it, which reverses the order and puts the oldest element on top. Each element changes stacks at most twice in its life, so dequeue is amortised O(1) even though one individual call can cost O(n). The common mistake is pouring back after every dequeue — then every operation is O(n).

Explain sliding window maximum with a deque, and why it is O(n).

Keep a deque of indices whose values decrease from front to back. Before pushing index i, pop every back index whose value is at most a[i] — an older and smaller element can never be a maximum while i is in the window. Then drop the front if its index is at most i − k, and the front is the answer for this window. Every index is pushed once and removed once, so the total work is O(n), against O(n·k) for recomputing each window.

A queue and a priority queue are both called queues. Are they the same thing?

Hard

Given an array and a limit, return the length of the longest contiguous subarray in which the largest value minus the smallest value is at most the limit.

Follow-up

The window moves at both ends, and the element that was the maximum can leave it while the limit is still violated — so neither the maximum nor the minimum can be carried in a single variable you update as you go.

Show the hint

Track the window maximum and the window minimum the way the console tracks a window maximum: one deque each, with opposite pop rules. While the spread exceeds the limit, advance the left edge and discard any deque front that has fallen behind it.