First Come, First Served at Rush Hour: Queues
At 8 a.m. the coffee shop's order screen freezes: serving each order from the front of a list moves every order behind it. Find a way to join at the back and serve from the front in one step each, and meet the structure built for it: the queue.
Apprentice · Data Structures · Updated
After this lesson you can
- Explain first in, first out with enqueue, dequeue and peek
- Explain why removing from the front of a plain array is O(n), and how a linked list or a front index makes it O(1)
Key takeaways
- A queue is first in, first out (FIFO): the first item to join is the first one served.
- Enqueue adds at the back, dequeue removes from the front and returns it, and peek reads the front.
- Dequeuing from the front of a plain array makes everyone scoot over: O(n) each time, O(n²) to serve everyone.
- A linked list with a head and a tail, or an array with a moving front index, makes every queue operation O(1).
- Adding at the front and serving from the end only moves the cost to joining; keeping every served order wastes memory.
Before this: Why Does This Loop Take Seconds? Your Language's List, where taking the first item off a list moved everyone behind it, and "Play Next" Without Moving Everyone: Linked Lists, which made the front cheap.
It's 8 a.m. at the coffee shop. Orders arrive from the counter and the app faster than the baristas can make them, and they wait on the order screen. Each time a drink is done, the barista taps Next order, and the screen shows the order that has waited longest. A busy morning puts 10,000 orders through that screen.
Today the screen keeps the waiting orders in a list: new orders go on the end, and Next order takes the one at index 0. On a quiet afternoon it's instant. At rush hour each tap takes longer than the one before, and by 8:30 the screen freezes. By the end of this lesson you'll have the structure that keeps the line fair and fast at any length, the queue. First, the plain fixes.
What would you try?
Today's code: take index 0. Removing the first item of a list moves every order behind it one slot forward, as in Jump to Song 500: Arrays. Serving 10,000 orders that way moves 9,999 + 9,998 + … + 1 = 49,995,000 orders: about 50 million moves, O(n²), for one morning.
Turn the list around: new orders at index 0, serve from the end. Now serving is quick, because nothing comes after the end. But every new order is an insert at index 0, which moves the whole line. The cost has moved from serving to joining; it hasn't gone away. Still about 50 million moves.
Never remove anything: keep the number of the next order to serve. Joining adds at the end, and serving reads the order at that number and adds 1 to it. Both are O(1), and nobody moves. But served orders never leave: by closing time the list holds every order of the day, and it keeps growing until the screen restarts.
| What we tried | Join the line | Serve the next order | Where it breaks |
|---|---|---|---|
| Take index 0 | O(1) | O(n): everyone behind moves | 50 million moves at rush hour |
| New orders at index 0, serve from the end | O(n): everyone moves | O(1) | the same 50 million, at joining |
| Keep the number of the next order | O(1) | O(1) | every order of the day stays in memory |
The questions that lead to it
Which places does the line touch? Only two: the back, where new orders join, and the front, where the next order is served. Never the middle.
What has to be fast? Both of them, all morning.
Which structure from the last chapter is cheap at both ends, and lets go of what it no longer needs? A linked list with a head and a tail. Join by coupling a new order behind the tail. Serve by taking the head and moving the head along to the next order. The served order isn't kept, and no other order moves.
How it got its name
This idea was so useful that it got a name: a queue, the British word for a line of people waiting. At the coffee shop, customers join the line at the back and the barista serves from the front. Nobody cuts in, and nobody at the back is served before the people ahead of them.
That rule is first in, first out, or FIFO (said "FIE-foe"): the first one in is the first one served, the opposite of a stack's last in, first out. A queue's operations work at its two ends:
- Enqueue (said "en-CUE") adds an item at the back.
- Dequeue (said "dee-CUE") removes the item at the front and gives it back.
- Peek reads the front item without removing it.


Building one on a linked list
This OrderQueue is a linked list used only at its two ends: the head is the front of the line, and the tail is the back. Enqueue couples a new node behind the back; dequeue moves the front along.
OrderQueue line = new OrderQueue();
line.Enqueue("oat latte");
line.Enqueue("cold brew");
line.Enqueue("chai tea");
Console.WriteLine("Next up: " + line.Peek());
Console.WriteLine("Served: " + line.Dequeue());
line.Enqueue("mocha");
while (line.Count > 0)
{
Console.WriteLine("Served: " + line.Dequeue());
}
Console.WriteLine("Orders waiting: " + line.Count);
class OrderNode
{
public string Order;
public OrderNode? Next;
public OrderNode(string order)
{
Order = order;
}
}
class OrderQueue
{
private OrderNode? front;
private OrderNode? back;
public int Count { get; private set; }
public void Enqueue(string order)
{
OrderNode node = new OrderNode(order);
if (back == null)
{
front = node;
}
else
{
back.Next = node;
}
back = node;
Count++;
}
public string Dequeue()
{
if (front == null)
{
throw new InvalidOperationException("No orders waiting");
}
string order = front.Order;
front = front.Next;
if (front == null) back = null;
Count--;
return order;
}
public string Peek()
{
if (front == null)
{
throw new InvalidOperationException("No orders waiting");
}
return front.Order;
}
}
Next up: oat latte
Served: oat latte
Served: cold brew
Served: chai tea
Served: mocha
Orders waiting: 0
class OrderNode {
String order;
OrderNode next;
OrderNode(String order) {
this.order = order;
}
}
class OrderQueue {
private OrderNode front;
private OrderNode back;
private int count;
int count() {
return count;
}
void enqueue(String order) {
OrderNode node = new OrderNode(order);
if (back == null) {
front = node;
} else {
back.next = node;
}
back = node;
count++;
}
String dequeue() {
if (front == null) {
throw new IllegalStateException("No orders waiting");
}
String order = front.order;
front = front.next;
if (front == null) back = null;
count--;
return order;
}
String peek() {
if (front == null) {
throw new IllegalStateException("No orders waiting");
}
return front.order;
}
}
void main() {
OrderQueue line = new OrderQueue();
line.enqueue("oat latte");
line.enqueue("cold brew");
line.enqueue("chai tea");
IO.println("Next up: " + line.peek());
IO.println("Served: " + line.dequeue());
line.enqueue("mocha");
while (line.count() > 0) {
IO.println("Served: " + line.dequeue());
}
IO.println("Orders waiting: " + line.count());
}
Next up: oat latte
Served: oat latte
Served: cold brew
Served: chai tea
Served: mocha
Orders waiting: 0
class OrderNode:
def __init__(self, order):
self.order = order
self.next = None
class OrderQueue:
def __init__(self):
self.front = None
self.back = None
self.count = 0
def enqueue(self, order):
node = OrderNode(order)
if self.back is None:
self.front = node
else:
self.back.next = node
self.back = node
self.count += 1
def dequeue(self):
if self.front is None:
raise IndexError("No orders waiting")
order = self.front.order
self.front = self.front.next
if self.front is None:
self.back = None
self.count -= 1
return order
def peek(self):
if self.front is None:
raise IndexError("No orders waiting")
return self.front.order
line = OrderQueue()
line.enqueue("oat latte")
line.enqueue("cold brew")
line.enqueue("chai tea")
print("Next up: " + line.peek())
print("Served: " + line.dequeue())
line.enqueue("mocha")
while line.count > 0:
print("Served: " + line.dequeue())
print(f"Orders waiting: {line.count}")
Next up: oat latte
Served: oat latte
Served: cold brew
Served: chai tea
Served: mocha
Orders waiting: 0
class OrderNode {
constructor(order) {
this.order = order;
this.next = null;
}
}
class OrderQueue {
front = null;
back = null;
count = 0;
enqueue(order) {
const node = new OrderNode(order);
if (this.back === null) {
this.front = node;
} else {
this.back.next = node;
}
this.back = node;
this.count++;
}
dequeue() {
if (this.front === null) {
throw new Error("No orders waiting");
}
const order = this.front.order;
this.front = this.front.next;
if (this.front === null) this.back = null;
this.count--;
return order;
}
peek() {
if (this.front === null) {
throw new Error("No orders waiting");
}
return this.front.order;
}
}
const line = new OrderQueue();
line.enqueue("oat latte");
line.enqueue("cold brew");
line.enqueue("chai tea");
console.log(`Next up: ${line.peek()}`);
console.log(`Served: ${line.dequeue()}`);
line.enqueue("mocha");
while (line.count > 0) {
console.log(`Served: ${line.dequeue()}`);
}
console.log(`Orders waiting: ${line.count}`);
Next up: oat latte
Served: oat latte
Served: cold brew
Served: chai tea
Served: mocha
Orders waiting: 0
class OrderNode {
order: string;
next: OrderNode | null = null;
constructor(order: string) {
this.order = order;
}
}
class OrderQueue {
private front: OrderNode | null = null;
private back: OrderNode | null = null;
count = 0;
enqueue(order: string): void {
const node = new OrderNode(order);
if (this.back === null) {
this.front = node;
} else {
this.back.next = node;
}
this.back = node;
this.count++;
}
dequeue(): string {
if (this.front === null) {
throw new Error("No orders waiting");
}
const order = this.front.order;
this.front = this.front.next;
if (this.front === null) this.back = null;
this.count--;
return order;
}
peek(): string {
if (this.front === null) {
throw new Error("No orders waiting");
}
return this.front.order;
}
}
const line = new OrderQueue();
line.enqueue("oat latte");
line.enqueue("cold brew");
line.enqueue("chai tea");
console.log(`Next up: ${line.peek()}`);
console.log(`Served: ${line.dequeue()}`);
line.enqueue("mocha");
while (line.count > 0) {
console.log(`Served: ${line.dequeue()}`);
}
console.log(`Orders waiting: ${line.count}`);
Next up: oat latte
Served: oat latte
Served: cold brew
Served: chai tea
Served: mocha
Orders waiting: 0
The orders come out in exactly the order they went in, mocha included, even though it joined after the first order was served. At rush hour, each enqueue and each dequeue is still one or two reference changes: 10,000 orders cost about 30,000 small steps instead of 50 million moves.
The front index, made tidy
The third try wasn't wrong, only wasteful: an array with a moving front index serves in O(1) without moving anyone. Its problem is the dead slots before the front, which pile up all day. The next lesson, Cutting In, and Keeping Only the Last 100: Deques and Ring Buffers, lets the back of the line wrap around and reuse them.
Your language's queue
| Language | The queue | Enqueue | Dequeue | Peek |
|---|---|---|---|---|
| C# | Queue<T> |
Enqueue(x) |
Dequeue() |
Peek() |
| Java | ArrayDeque<T> |
offer(x) |
poll() |
peek() |
| Python | collections.deque |
append(x) |
popleft() |
line[0] |
| JavaScript, TypeScript | none built in |
C#'s, Java's and Python's queues are all O(1) at both ends. JavaScript and TypeScript have no built-in queue. An array's shift() removes the first item, but it can move every item behind it, which is the slow way above. For a short line that's fine; for a long one, use a queue class like OrderQueue. Python's plain list has the same trap: pop(0) is O(n), which is why deque exists.
Try it. Enqueue two more orders, a flat white and an espresso, right after the mocha. In what order are they served? Then change OrderQueue so Peek (peek) on an empty line returns a message instead of throwing an error.
The queue's cost card
| Operation | Big-O | Why, in everyday words |
|---|---|---|
| Enqueue | O(1) | Join at the back of the line |
| Dequeue | O(1) | Serve the person at the front; nobody else moves |
| Peek | O(1) | See who's at the counter |
| Dequeue from a plain array's index 0 | O(n) | Everyone in line takes a step forward |
| Find an order in the line | O(n) | Ask down the line, one by one |
For a short line, honestly, a list served from index 0 is fine: moving 10 orders is nothing. The queue earns its place when the line can get long, and at rush hour it always does.
Check yourself
2 questions to try on the lesson page.
So what
Whenever work arrives over time and must be handled in order, a queue keeps it fair and fast. Spotting a list that's being emptied from the front, and swapping in a real queue, is one of the simplest speed-ups you'll ever make.