Linear Data Structures

Queue — First In, First Out

A queue models the most natural form of fairness: whoever arrives first is served first. Elements enter from one end (the rear) and leave from the other end (the front). This FIFO discipline makes queues the natural choice for any system where order of arrival determines order of service — operating system schedulers, network packet buffers, printer spoolers, and breadth-first graph traversal all rely on queues at their core.

The Concept

What is a Queue?

A queue is a linear data structure with a strict two-end access rule: elements are always added at the REAR (also called tail or back) and always removed from the FRONT (also called head). No element in the middle can be accessed directly. The first element enqueued is the first to be dequeued — FIFO.

⬅️ DEQUEUE FRONT

12front

35[1]

61[2]

48rear

➡️ ENQUEUE REAR

The element 12 arrived first — it sits at the FRONT and will leave first. Element 48 arrived last — it sits at the REAR and will be the last to leave. Unlike a stack, you cannot access any element other than the one at the FRONT.

Stack vs Queue: A stack is LIFO — the most recently added element leaves first (a stack of plates). A queue is FIFO — the element that has waited the longest leaves first (a queue of people at a counter). The difference is which end removal happens from.

Operations

Enqueue · Dequeue · Front · isEmpty

A queue has four primary operations. All are O(1) when implemented correctly.

➡️

ENQUEUE(value)

Adds a new element at the REAR of the queue. The queue grows from the rear. In an array implementation, rear is incremented and the value placed at arr[rear]. O(1)

⬅️

DEQUEUE()

Removes and returns the element at the FRONT. Front is incremented (array) or head pointer updated (linked list). Attempting to dequeue from an empty queue is an underflow error. O(1)

👁️

FRONT() / PEEK()

Returns the front element without removing it. Used to inspect the next element to be served. O(1)

❓

isEmpty()

Returns true if the queue has no elements. Used as a loop condition: "process while queue is not empty." O(1)

// Simple queue using array (pseudocode) front = 0, rear = -1 arr[MAX_SIZE] function enqueue(value): if rear == MAX_SIZE - 1: error("Queue Overflow") rear = rear + 1 arr[rear] = value function dequeue(): if front > rear: error("Queue Underflow") value = arr[front] front = front + 1 return value function peek(): if front > rear: error("Queue is empty") return arr[front]

The wasted space problem: In a simple array queue, every dequeue moves the front pointer forward but never reuses those slots. After n enqueue-dequeue pairs, the front pointer is at index n and the rear at index n — the array appears full even though all slots have been freed. The circular queue solves this.

Four Types

Simple · Circular · Deque · Priority Queue

1 · Simple Queue (Linear Queue)

FIFO · One direction

The basic form described above. Elements enter at the rear and leave from the front. The front and rear pointers move in one direction only — they never wrap around. Problem: once the rear pointer reaches the end of the array, no more elements can be enqueued even if the front portion of the array is empty after dequeues. The circular queue fixes this.

Use when: queue size is small and predictable, or a linked-list implementation is used (which has no wasted-space problem).

2 · Circular Queue

FIFO · Wraps around

The rear and front pointers wrap around to the beginning of the array when they reach the end. This reuses freed slots and solves the wasted-space problem entirely. The key formula is:

rear = (rear + 1) % MAX_SIZE // wrap rear front = (front + 1) % MAX_SIZE // wrap front isFull: (rear + 1) % MAX_SIZE == front isEmpty: front == rear

Visual — 8-slot circular queue with front=2, rear=6:

—[0]

—[1]

12FRONT[2]

35[3]

61[4]

48[5]

27REAR[6]

—[7]

Slots [0] and [1] are free — previously dequeued. The next enqueue goes to slot [7], then wraps to [0], then [1], reusing them.

Use when: fixed-size buffer with continuous enqueue-dequeue cycles — OS scheduling, network buffers, audio/video streaming buffers.

3 · Deque (Double-Ended Queue)

Insert and delete at both ends

A deque (pronounced "deck") allows insertion and deletion at both the front and the rear. It generalises both the stack and the queue — a deque restricted to one end is a stack; restricted to one direction of insertion/deletion is a queue.

AddFront(value) → insert at front end AddRear(value) → insert at rear end RemoveFront() → remove from front end RemoveRear() → remove from rear end PeekFront() → inspect front without removing PeekRear() → inspect rear without removing

Two restricted variants:
— Input-restricted deque: insertion only at rear; deletion at both ends.
— Output-restricted deque: insertion at both ends; deletion only at front.

Use when: undo/redo history (add or remove from either end), sliding window algorithms, palindrome checking, work-stealing schedulers.

4 · Priority Queue

Highest priority served first

A priority queue is a queue where each element has an associated priority value. Dequeue always removes the element with the highest priority (or lowest, depending on convention) — not the element that arrived first. Order of arrival is irrelevant; priority is everything.

A naive implementation uses a sorted array or linked list (O(n) insert, O(1) dequeue). The efficient implementation uses a heap, which gives O(log n) for both insert and dequeue — which is why heaps and priority queues are inseparable topics.

🔺 Priority Queue is covered in depth on the Heap page

Heap structure, min-heap and max-heap, heapify, heap sort, and why a heap gives O(log n) priority queue operations — all covered with interactive games.

Go to Heap →

Performance

Time Complexity Across Queue Types

Operation	Simple Queue	Circular Queue	Deque	Priority Queue (Heap)
Enqueue / AddRear	O(1)	O(1)	O(1)	O(log n)
Dequeue / RemoveFront	O(1)	O(1)	O(1)	O(log n)
AddFront	N/A	N/A	O(1)	N/A
RemoveRear	N/A	N/A	O(1)	N/A
Peek / Front	O(1)	O(1)	O(1)	O(1)
Search	O(n)	O(n)	O(n)	O(n)
Space usage	Wastes freed slots	Reuses all slots	Dynamic	Compact array

Why all basic operations are O(1): Both the front and rear are accessed directly by pointer or index — no scanning or sorting happens during enqueue or dequeue. The circular queue achieves this while also eliminating wasted space through the modulo wrap-around formula.

Applications

Where Queues Are Used

🖥️

CPU Scheduling — Round Robin

Operating systems use a circular queue to implement round-robin CPU scheduling. Each process is given a fixed time slice (quantum). When its quantum expires, the process is enqueued at the rear and the CPU moves to the front of the queue. Every process gets a fair share of CPU time in the order it was enqueued — no process starves. The circular structure means the queue never "runs out" of space as processes cycle through.

🔍

BFS — Breadth-First Search

BFS on a graph uses a queue as its core data structure. The algorithm starts at a source node, enqueues it, then repeatedly dequeues a node, visits it, and enqueues all its unvisited neighbours. Because a queue is FIFO, BFS always visits all nodes at distance 1 before any node at distance 2 — guaranteeing the shortest path in an unweighted graph.

queue.enqueue(source) while queue is not empty: node = queue.dequeue() for each neighbour of node: if neighbour not visited: visited[neighbour] = true queue.enqueue(neighbour)

🖨️

Print Spooler

A print spooler maintains a queue of print jobs. Jobs are enqueued as they are submitted and dequeued in FIFO order as the printer becomes free. No job can "jump the queue" — the first job submitted is the first to be printed. This is the most direct real-world analogy for a simple queue.

🌐

Network Packet Buffering

Routers and network switches use circular queues (ring buffers) to hold incoming packets while they wait to be forwarded. Packets arrive at varying speeds and are processed at a fixed rate. The circular queue absorbs bursts — when packets arrive faster than they are processed, they queue up. When the queue fills, new packets are dropped (congestion). TCP flow control is fundamentally a queue management problem.

🏪

Producer-Consumer Problem

The producer-consumer pattern — one or more threads producing data and others consuming it — is solved using a shared queue (usually circular). Producers enqueue items; consumers dequeue them. The queue decouples the production rate from the consumption rate. This pattern appears in web servers (request queue), compilers (token queue), and streaming pipelines (frame buffer). A deque is used when consumers can steal work from the rear of another consumer's queue — a technique called work-stealing used in Java's ForkJoinPool.

🪟

Sliding Window Algorithms

Deques are the data structure of choice for sliding window problems — finding the maximum or minimum in a moving window of size k over an array in O(n) total time. The deque stores indices of potential maximum candidates. Elements outside the window are dequeued from the front; elements smaller than the current element are removed from the rear (they can never be the maximum for any future window). This gives O(1) per element instead of O(k) per window.

Interactive Learning

Explore All Queue Types

The Linear DS Quest contains three dedicated tabs for queue types. Switch between them using the tabs inside the game. The Queue tab shows simple FIFO enqueue and dequeue. The Deque tab demonstrates insertions and deletions at both ends. The Circular Queue tab shows the wrap-around behaviour with a visual ring of 8 slots.