Queues in DSA: The FIFO Data Structure Explained

A queue is a linear data structure that follows the FIFO rule — First In, First Out. You add elements at one end (the rear) and remove them from the other end (the front), so items leave in the exact order they arrived. Think of a line at a checkout: whoever joined first is served first. This page explains the FIFO idea, the core operations, and where queues are used.

The FIFO idea

A queue is the mirror image of a stack. Where a stack reverses arrival order (LIFO), a queue preserves it (FIFO). This makes queues the natural choice for fair, in-order processing: tasks, requests, and messages handled in the sequence they came in.

Core operations

All operations are O(1):

enqueue(x) — add x at the rear.
dequeue() — remove and return the item at the front.
front() / peek() — look at the front item without removing it.
isEmpty() — is the queue empty?
size() — how many items are stored.

Here is a queue’s lifecycle using each language’s idiomatic built-in (building one yourself is covered in implementing a queue):

#include <queue>
std::queue<int> q;
q.push(1);          // enqueue
q.push(2);
q.push(3);          // front → rear: 1, 2, 3
int f = q.front();  // 1 — peek
q.pop();            // dequeue removes 1 (returns void)
int n = q.size();   // 2
bool empty = q.empty();

import java.util.*;
Deque<Integer> q = new ArrayDeque<>();
q.offer(1);            // enqueue at rear
q.offer(2);
q.offer(3);            // front → rear: 1, 2, 3
int f = q.peek();      // 1 — peek front
q.poll();              // dequeue removes and returns 1
int n = q.size();      // 2
boolean empty = q.isEmpty();

// A plain array works, but shift() is O(n). For interviews this is fine;
// see the implementation page for an O(1) version.
const q = [];
q.push(1);             // enqueue
q.push(2);
q.push(3);             // front is index 0
const f = q[0];        // 1 — peek
q.shift();             // dequeue removes and returns 1
const n = q.length;    // 2
const empty = q.length === 0;

from collections import deque
q = deque()
q.append(1)        # enqueue at rear
q.append(2)
q.append(3)        # front → rear: 1, 2, 3
f = q[0]           # 1 — peek front
q.popleft()        # dequeue removes and returns 1 — O(1)
n = len(q)         # 2
empty = not q

For beginners: “enqueue” just means join the line; “dequeue” means the front person leaves. The two ends never swap roles — additions at the back, removals at the front.

Why the FIFO order matters

Because additions happen at one end and removals at the other, a well-implemented queue does both in O(1) with O(n) storage. The catch is the implementation: removing from the front of a plain array is O(n) (everything shifts). That is why we use a circular buffer or a doubly-ended structure like deque — details on the implementation page.

Where queues are used

Task / job scheduling — print queues, CPU run queues, background job workers.
Breadth-First Search (BFS) — exploring graphs and trees level by level.
Buffering — keyboard input, streaming data, producer/consumer pipelines.
Request handling — web servers process incoming requests in arrival order.

Going deeper: A queue is an abstract data type (FIFO contract). Variants relax the “one end each” rule: a deque allows add/remove at both ends, a circular queue reuses a fixed array, and a priority queue serves the highest-priority item instead of the oldest.

When to use a queue

Use a queue whenever order of arrival should decide order of processing, or whenever you explore “all the near things before the far things” — that’s BFS. If instead the most recent item should come out first, you want a stack.

Next: implement a queue, then explore the circular queue and deque. Ready to practice? See the stacks & queues exercises.