Noesis
3.2.7Linear Data Structures

Queue — FIFO semantics, enqueue - dequeue, circular array implementation

2,150 words10 min readdifficulty · medium2 backlinks
🇮🇳 Yeh note Hinglish mein padho →

WHAT is a Queue?

Contrast with a Stack (LIFO): a stack removes the most recent; a queue removes the oldest.

Operation Stack (LIFO) Queue (FIFO)
add push (top) enqueue (rear)
remove pop (top) dequeue (front)
who leaves first newest oldest

WHY does FIFO matter?

HOW to implement: the naïve array (and why it's bad)

Idea: keep a front index and a rear index in a plain array.

  • enqueue: write at rear, then rear++.
  • dequeue: read at front, then front++.

HOW: Circular Array (Ring Buffer)

The wrap-around is done with modulo: next(i)=(i+1) mod N\text{next}(i) = (i + 1) \bmod N where NN is the capacity.

Figure — Queue — FIFO semantics, enqueue - dequeue, circular array implementation

Deriving the layout from first principles

We store arr[N], plus a front index and a count (number of elements). Why count instead of a rear index? Because front-only + rear-only indices make "full" and "empty" look identical (both give front == rear). Tracking count removes the ambiguity cleanly.

  • Front of queue lives at arr[front].
  • Rear (next free slot) is derived: rear=(front+count) mod N\text{rear} = (\text{front} + \text{count}) \bmod N.

Reference implementation

class CircularQueue:
    def __init__(self, N):
        self.arr = [None] * N
        self.N = N
        self.front = 0
        self.count = 0
 
    def is_empty(self): return self.count == 0
    def is_full(self):  return self.count == self.N
 
    def enqueue(self, x):
        if self.is_full(): raise OverflowError("queue full")
        rear = (self.front + self.count) % self.N   # WHY: next free slot
        self.arr[rear] = x
        self.count += 1
 
    def dequeue(self):
        if self.is_empty(): raise IndexError("queue empty")
        x = self.arr[self.front]
        self.front = (self.front + 1) % self.N       # WHY: wrap front forward
        self.count -= 1
        return x
 
    def peek(self):
        if self.is_empty(): raise IndexError("queue empty")
        return self.arr[self.front]

All four core ops are O(1) time, O(N) space. No shifting, ever.

Worked Examples

Common Mistakes (Steel-manned)

Recall Feynman: explain to a 12-year-old

Imagine kids lining up for ice cream. The first kid in line gets ice cream first and leaves; new kids join at the end. That's a queue. Now suppose the line is drawn as a circle of chairs instead of a straight line — when you reach the last chair, the next kid sits in the very first chair again (if it's empty). That circle trick means you never run out of room by "walking off the end." We just remember which chair the front kid is in and how many kids are seated.

Active Recall

What discipline does a queue follow?
FIFO — First In, First Out (oldest element leaves first).
In a queue, where do you enqueue and where do you dequeue?
Enqueue at the rear/back; dequeue from the front.
Why is the naïve (non-circular) array queue space-inefficient?
front and rear drift rightward; once rear hits capacity the queue is "full" even though left slots are empty.
What math operation enables wrap-around in a circular queue?
Modulo: index = (index + 1) % N.
Formula for the next free (rear) slot using front and count?
rear = (front + count) % N.
How do you compute the new front after a dequeue?
front = (front + 1) % N.
Why track count instead of just front and rear indices?
Because front == rear is ambiguous (means both empty and full); count makes empty (0) vs full (N) unambiguous.
Time complexity of enqueue and dequeue in a circular array?
O(1) each — only indices move, no shifting.
Condition for queue empty (with count)?
count == 0.
Condition for queue full (with count, capacity N)?
count == N.
Queue vs Stack: who is removed first?
Queue removes the oldest (FIFO); Stack removes the newest (LIFO).
Which traversal needs a queue: BFS or DFS?
BFS (Breadth-First Search) uses a queue; DFS uses a stack.

Connections

  • Stack — LIFO (mirror image: newest-first vs oldest-first)
  • Modular Arithmetic (the % N that makes the ring work)
  • Breadth-First Search (BFS) (canonical queue user)
  • Deque — Double-Ended Queue (generalization: add/remove both ends)
  • Circular Buffer / Ring Buffer (same structure in OS & networking)
  • Amortized Analysis (compare to linked-list queue, no resize cost)
  • Priority Queue (breaks FIFO: order by priority, not arrival)

Concept Map

adds at rear

removes at front

contrasts with

guarantees

used by

indices drift right

fixed by

wraps via

tracks

removes ambiguity

derives

Queue FIFO

enqueue x

dequeue

Stack LIFO

Fairness in arrival order

BFS, CPU scheduling, buffers

Naive array with front and rear

Wasted space, false full

Circular array ring buffer

next i = i+1 mod N

front plus count

full vs empty distinct

rear = front+count mod N

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Queue ka matlab simple hai — line jaise ticket counter pe lagti hai. Jo pehle aaya, wo pehle jayega. Isko hum FIFO (First In, First Out) bolte hain. Naya element hamesha rear (peeche) se add hota hai — ye enqueue hai. Aur element hamesha front (aage) se nikalta hai — ye dequeue hai. Beech se kuch nahi nikaal sakte. Stack se ulta hai: stack mein naya wala pehle nikalta (LIFO), queue mein purana wala pehle.

Ab problem: agar aap normal array mein front aur rear pointer aage badhate raho, dono right side ki taraf khisak jaate hain. Ek time aata hai jab rear array ke end pe pahunch jaata hai aur queue "full" dikhta hai, jabki left side ki slots khaali padi hain — space waste! Iska smart solution hai circular array (ring buffer). Yahan hum maan lete hain ki array ka last slot first slot se juda hua hai, ek circle ki tarah. Jab rear end se gir jaata hai, wo % N (modulo) ki madad se index 0 pe wapas aa jaata hai. Koi element move nahi hota, sirf index ghoomta hai — isliye har operation O(1).

Important formula yaad rakho: agla khaali slot nikalta hai rear = (front + count) % N se. Aur dequeue ke baad front = (front + 1) % N. Hum count (kitne element hain) track karte hain, kyunki sirf front aur rear se "empty" aur "full" dono mein front == rear ho jaata hai — confuse ho jaata hai. count rakhne se: count == 0 matlab empty, count == N matlab full. Bilkul clear.

Real life mein queue bahut jagah use hoti hai — CPU scheduling, printer jobs, web server requests, aur graph ka BFS (Breadth-First Search). Jahan bhi "jo pehle aaya use pehle serve karo" chahiye, wahan queue lagao. Modulo wala circle trick samajh liya to ring buffer pakka clear ho gaya.

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 1,777 wordsD2Visual walkthroughThe derivation in pictures · 2,082 wordsD3Worked examplesEvery scenario covered · 3,584 wordsD4ExercisesGraded, full solutions · 3,707 wordsD5Question bankConcept traps, quick reveals · 1,646 words

Test yourself — Linear Data Structures

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

Modular arithmetic — definition, addition, multiplication, congruenceMaths · 2.5.6Deque (double-ended queue) — operations, use casesCoding · 3.2.8Amortized analysis — aggregate, accounting, potential methodsCoding · 3.1.5Priority Queue — concept (heap-based implementation covered later)Coding · 3.2.9Circular linked list — applicationsCoding · 3.2.4Deque (double-ended queue) — operations, use casesCoding · 3.2.8