Queue FIFO Principle Explained

The FIFO Principle

A queue is an abstract data type that follows the First In, First Out (FIFO) principle. The first element added is the first to be removed, just like a line of people waiting at a counter.

Core Operations

Operation	Description	Time Complexity
enqueue(x)	Add element x to the rear	O(1)
dequeue()	Remove and return the front element	O(1)
front()	View the front element without removing	O(1)
isEmpty()	Check if the queue is empty	O(1)

How FIFO Works

enqueue(A): [A]           <- A is at front
enqueue(B): [A, B]        <- A is still at front, B is at rear
enqueue(C): [A, B, C]     <- A is at front, C is at rear
dequeue():  [B, C]        <- A removed (first in, first out)
dequeue():  [C]           <- B removed

Unlike a stack where the most recent element is processed first, a queue ensures fairness — elements are processed in the order they arrive.

Implementation Strategies

1. Array-based (circular buffer): Uses two pointers (front and rear) that wrap around. Avoids shifting elements after dequeue. All operations are O(1).

2. Linked list-based: Maintains a head (front) and tail (rear) pointer. Enqueue appends to tail; dequeue removes from head. Always O(1).

3. Two-stack implementation: Uses two stacks to simulate a queue. Amortized O(1) per operation. This is a classic interview question.

Queue vs Stack

Property	Stack	Queue
Order	LIFO	FIFO
Add	Push (top)	Enqueue (rear)
Remove	Pop (top)	Dequeue (front)
Use case	Recursion, undo	Scheduling, BFS

Variants

• Double-ended queue (deque): Allows insertion and removal at both ends.
• Priority queue: Elements are dequeued based on priority, not insertion order. Typically implemented with a heap.
• Circular queue: Fixed-size queue that wraps around to avoid wasted space.