🚶 Queue - FIFO Data Structure
🟢 Beginner Linear DS 45 min read
🎯 What is a Queue?
A Queue is a linear data structure following FIFO (First In, First Out). Like a line at a ticket counter: the first person to join is the first to be served. Elements are added at the rear and removed from the front.
Enqueue → [A][B][C][D] → Dequeue
↑ Front ↑ Rear
FIFO: A entered first → A leaves first💻 PHP Implementation
<?php
class Queue {
private array $items = [];
public function enqueue(mixed $item): void {
$this->items[] = $item; // O(1) amortized
}
public function dequeue(): mixed {
if ($this->isEmpty()) throw new UnderflowException('Queue empty');
return array_shift($this->items); // O(n) - reindexes!
}
public function peek(): mixed {
if ($this->isEmpty()) throw new UnderflowException('Queue empty');
return $this->items[0];
}
public function isEmpty(): bool { return empty($this->items); }
public function size(): int { return count($this->items); }
}
// Optimized: Circular Queue using array with front/rear pointers
class CircularQueue {
private array $arr;
private int $front = 0, $rear = -1, $size = 0, $capacity;
public function __construct(int $capacity) {
$this->capacity = $capacity;
$this->arr = array_fill(0, $capacity, null);
}
public function enqueue(int $val): bool {
if ($this->isFull()) return false;
$this->rear = ($this->rear + 1) % $this->capacity;
$this->arr[$this->rear] = $val;
$this->size++;
return true;
}
public function dequeue(): ?int {
if ($this->isEmpty()) return null;
$val = $this->arr[$this->front];
$this->front = ($this->front + 1) % $this->capacity;
$this->size--;
return $val;
}
public function isEmpty(): bool { return $this->size === 0; }
public function isFull(): bool { return $this->size === $this->capacity; }
}📂 Types of Queues
| Simple Queue | Basic FIFO | Printer queue |
| Circular Queue | Last position connects to first | CPU scheduling, buffering |
| Priority Queue | Elements have priority; higher priority dequeued first | Emergency room, Dijkstra |
| Deque (Double-Ended) | Insert/delete from both ends | Sliding window, undo/redo |
🐘 PHP Built-in: SplQueue
$queue = new SplQueue();
$queue->enqueue('First');
$queue->enqueue('Second');
$queue->enqueue('Third');
echo $queue->dequeue(); // First (FIFO)
echo $queue->count(); // 2
// Priority Queue
$pq = new SplPriorityQueue();
$pq->insert('Task A', 1); // priority 1 (low)
$pq->insert('Task B', 10); // priority 10 (high)
echo $pq->extract(); // Task B (highest first)💼 Interview Questions
Stack: LIFO (vertical). Queue: FIFO (horizontal). Stack has one end; queue has two ends (front/rear).
Enqueue: push to stack1. Dequeue: if stack2 empty, pop all from stack1 → push to stack2, then pop from stack2. Amortized O(1).
Use array of fixed size with front and rear pointers. Use modulo arithmetic:
rear = (rear + 1) % capacity. This avoids array_shift() O(n) cost. All ops O(1).