Skip to content

Queues

Lesson 6 of 7 in Foundations · 25 min · Beginner

First in, first out — a line at the counter.

Introduction

A printer has 20 jobs waiting. When the first one finishes, who prints next, and how does the computer keep the line without sliding all the other jobs forward?

Jobs must print in the order they arrived. Store them in a row of boxes and the first job sits in box 0. When it finishes, the obvious fix is to slide jobs 2 to 20 one box to the left: 19 moves for every page that prints.

That is a lot of shuffling just to forget one job. What if every job stayed exactly where it is, and only something small changed?

Lesson overview

This lesson will show you how to:

  • Explain why a queue serves items in first-in, first-out order.
  • Trace enqueue and dequeue on a circular buffer with wrap-around.
  • Explain why moving only front and back keeps each step O(1).
  • Use a monotonic deque to track a sliding window's maximum.
  • Choose a stack instead when the newest item must come out first.

The picture

line80312237455frontbackleaves firstwrapped past the endnext arrival lands hereArray line with 6 slots: 8, 3, empty, 2, 7, 5. Pointers: front at index 3; back at index 1. Marked: index 1 changed.

Mental model

A ticket counter calls tickets in the order people joined the line: newcomers go to the back, the front is served next, and nobody walks forward when someone leaves.

Now picture a sushi belt with 6 spots that loops back on itself. After spot 5 comes spot 0 again, so a spot you just emptied is the next one a new plate can use. That belt is a circular buffer.

Nobody in the line moves, only two markers do: front says who is served next, back says where the newcomer goes, and both wrap from the last slot to slot 0.

Words to know

enqueue
Join the line: put a new item at the back.
dequeue
Serve the line: remove and return the item at the front.
front
The oldest item, the next one to leave. Also called the head.
back
The newest item, the last to arrive. Also called the tail or rear.
FIFO
First in, first out. Items leave in exactly the order they arrived.
circular buffer
A fixed array treated as a loop: front and back move forward with % capacity, so freed slots get reused and nothing ever shifts.
deque
A double-ended queue (say "deck"): you can add and remove at both the front and the back, each in O(1).
monotonic deque
A deque whose values stay in one order, like biggest to smallest, because you pop anything that would break it before adding a new item.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: Things must be handled in the order they arrived: print jobs, tickets, requests, messages.
  • Yes: You explore a tree, grid or graph level by level, or the nearest things first (BFS): shortest path with equal steps, minimum moves.
  • Yes: Only the most recent items matter and old ones expire from the front: the last 3000 ms of calls, a moving average.
  • Yes: A window slides along and you need its maximum or minimum at every step: a monotonic deque.

Not this when

  • No: The newest item must come out first (undo, matching brackets, backtracking): that is a stack.
  • No: The best item must come out next, whatever order it arrived in (most urgent, smallest, top K): that is a heap.
  • No: You need an item by position or by value: an array or a hash map reaches it directly, a queue only shows its ends.

Which pattern fits?

  1. Which pattern? 1 of 5

    Count how many requests arrived in the last 3000 milliseconds, every time a new request comes in. Timestamps only go up.

  2. Which pattern? 2 of 5

    Given a binary tree, return its values level by level, from the root down, left to right.

  3. Which pattern? 3 of 5

    Check whether a string of brackets like ( [ { } ] ) is properly nested and closed.

  4. Which pattern? 4 of 5

    An emergency room always treats the most critical patient next, no matter who arrived first.

  5. Which pattern? 5 of 5

    Given an array and k, return the maximum of every window of k consecutive numbers, in O(n) time.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. 1buffer = 6 empty slots; front = 0, back = 5, size = 0
  2. enqueue(x):
  3. 2if size == 6: refuse (the line is full)
  4. 3back = (back + 1) % 6, buffer[back] = x, size = size + 1
  5. dequeue():
  6. 4if size == 0: refuse (nobody to serve)
  7. 5x = buffer[front], front = (front + 1) % 6, size = size - 1, return x

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.buf = [None] * capacity
        self.front = 0
        self.back = capacity - 1
        self.size = 0

    def enqueue(self, x):
        if self.size == self.capacity:
            return False
        self.back = (self.back + 1) % self.capacity
        self.buf[self.back] = x
        self.size += 1
        return True

    def dequeue(self):
        if self.size == 0:
            return None
        x = self.buf[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return x
Time · O(1) per enqueue or dequeueSpace · O(k) for a buffer of k slots
  • Neither operation loops, so both are O(1). The only way to make dequeue slow is to shift items forward, which is exactly what front and back avoid.
  • front and back look the same when the line is full and when it is empty. Keep a size counter (as here), or leave one slot unused, to tell them apart.
  • Empty-queue behaviour depends on the language. Python's deque.popleft() raises IndexError, Java's Queue.poll() returns null (remove() throws NoSuchElementException), and C++'s std::queue::pop() on an empty queue is undefined behaviour, so check empty() first.
  • In real code use the library queue: collections.deque in Python (never list.pop(0), which shifts everything), ArrayDeque in Java, std::queue or std::deque in C++. They are mostly circular arrays or block lists, not plain linked lists.
  • For sliding window maximum the deque holds indexes, not values, so you can tell when the front has left the window. Each index is pushed once and popped at most once, which is why the whole pass is O(n).

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

Build a queue with a fixed capacity k that reuses freed space. Support enQueue, deQueue, Front, Rear, isEmpty and isFull, each in O(1).

Input

MyCircularQueue(3), enQueue(1), enQueue(2), enQueue(3), enQueue(4), Rear(), isFull(), deQueue(), enQueue(4), Rear()

Output

[null, true, true, true, false, 3, true, true, true, 4]

Approach

  1. Keep an array of k slots plus front, back and size. Start with front = 0 and back = k - 1 so the first enqueue lands in slot 0.
  2. enQueue: if size == k return false. Otherwise back = (back + 1) % k, store the value there and grow size.
  3. deQueue: if size == 0 return false. Otherwise front = (front + 1) % k and shrink size. The old value just stays unread.
  4. In the example the fourth enQueue is refused (full), and after one deQueue the fifth lands in slot 0, so Rear() is 4.
class MyCircularQueue:
    def __init__(self, k):
        self.capacity = k
        self.buf = [0] * k
        self.front = 0
        self.back = k - 1
        self.size = 0

    def enQueue(self, value):
        if self.size == self.capacity:
            return False
        self.back = (self.back + 1) % self.capacity
        self.buf[self.back] = value
        self.size += 1
        return True

    def deQueue(self):
        if self.size == 0:
            return False
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return True

    def Front(self):
        return -1 if self.size == 0 else self.buf[self.front]

    def Rear(self):
        return -1 if self.size == 0 else self.buf[self.back]

    def isEmpty(self):
        return self.size == 0

    def isFull(self):
        return self.size == self.capacity
Time · O(1) per operationSpace · O(k)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. A circular queue has 6 slots and is not full. back is at slot 5. Where does the next enqueue go?
  2. Why does a circular queue not need to shift everyone forward after a dequeue?
  3. In a circular queue with 6 slots, front == (back + 1) % 6. Is the line full or empty?
  4. You call dequeue on an empty queue. What happens?
  5. Sliding window maximum: the deque holds the values 9, 5, 4 from front to back, and a new number 7 arrives. What happens?

Question 1 of 5

A circular queue has 6 slots and is not full. back is at slot 5. Where does the next enqueue go?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

  1. Solve Number of Recent Calls (opens in a new tab) (LeetCode, easy)

    Hint: Timestamps only go up, so old pings sit at the front. Dequeue while the front is older than t - 3000; the queue's size is the answer.

  2. Solve Time Needed to Buy Tickets (opens in a new tab) (LeetCode, easy)

    Hint: Simulate the line: whoever is served buys one ticket and rejoins the back if they still need more. Count seconds until person k is done.

  3. Solve Implement Stack using Queues (opens in a new tab) (LeetCode, easy)

    Hint: After enqueueing x, rotate the older items behind it by moving size - 1 items from the front to the back, so the newest sits at the front.

  4. Solve Design Circular Deque (opens in a new tab) (LeetCode, medium)

    Hint: Same circular buffer, but both ends move. Moving front backwards needs (front - 1 + k) % k so the index never goes negative.

  5. Solve Reveal Cards In Increasing Order (opens in a new tab) (LeetCode, medium)

    Hint: Run the reveal rule on a queue of positions, not cards: the first position gets the smallest card, the next position goes to the back.

  6. Solve Rotting Oranges (opens in a new tab) (LeetCode, medium)

    Hint: Queue every rotten orange first. Each round rots the neighbours of everything currently in the queue, so the number of rounds is the answer.

  7. Solve Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (opens in a new tab) (LeetCode, medium)

    Hint: Keep one monotonic deque for the window's max and one for its min. Shrink from the left while max minus min is over the limit.

  8. Solve Shortest Subarray with Sum at Least K (opens in a new tab) (LeetCode, hard)

    Hint: Work on prefix sums, with negatives allowed. A deque of indexes with increasing prefix sums lets you pop the front when it is long enough and the back when it can't help.

Additional resources