A queue is a linear data structure that follows the FIFO (First In, First Out) principle — the element added earliest is the first one to be removed. Think of a queue at a bus stop: the person who joined first boards first.
Key Terminology
- FIFO — First In, First Out: the defining property of a queue.
- Front (Head) — the end from which elements are removed (dequeue).
- Rear (Tail) — the end where new elements are inserted (enqueue).
- Enqueue — INSERT an element at the REAR.
- Dequeue — REMOVE an element from the FRONT.
- Peek / Front — VIEW the front element without removing it.
- isEmpty — check whether the queue is empty.
- Overflow — enqueue on a full (fixed-size) queue.
- Underflow — dequeue from an empty queue.
Queue Using a Python List
While a list CAN be used as a queue, it is inefficient (dequeue requires shifting all elements). The recommended approach is Python's collections.deque:
```
from collections import deque
q = deque()
q.append(10) # enqueue at rear
q.append(20)
q.append(30)
print(q.popleft()) # dequeue from front → 10
print(q[0]) # peek front → 20
```
- Alternatively for CBSE problems, a list can be used:
- Enqueue: list.append(element)
- Dequeue: list.pop(0) — removes first element (O(n) but acceptable for exam purposes)
Queue Operations — Step-by-Step
| Operation | Queue State (left=front, right=rear) |
|-----------|--------------------------------------|
| Initial | [] |
| enqueue(A) | [A] |
| enqueue(B) | [A, B] |
| enqueue(C) | [A, B, C] |
| dequeue() → A | [B, C] |
| peek() → B | [B, C] (unchanged) |
| enqueue(D) | [B, C, D] |
| dequeue() → B | [C, D] |
Types of Queues
Simple Queue — Basic FIFO queue as described above.
Circular Queue — The rear connects back to the front, making use of empty slots vacated by dequeue. Avoids "false overflow" in array implementations. Position formula: rear = (rear + 1) % maxsize.
Double-Ended Queue (Deque) — Insertion and deletion are allowed at BOTH ends.
Priority Queue — Each element has a priority; elements with higher priority are dequeued first, regardless of insertion order.
Applications of Queue
- 1.CPU Scheduling — Round-robin scheduling uses a queue.
- 2.Print Spooler — Documents are printed in the order they are sent.
- 3.Keyboard Buffer — Keystrokes are stored and processed in order.
- 4.Breadth First Search (BFS) — Graph traversal uses a queue.
- 5.Simulation — Modelling real-world waiting lines (bank, ticket counter).
- 6.Network data packets — Routers use queues to manage packet flow.
- 7.Call centre systems — Incoming calls are queued until an agent is free.
Difference Between Stack and Queue
| Feature | Stack | Queue |
|---------|-------|-------|
| Principle | LIFO | FIFO |
| Insertion point | Top | Rear |
| Deletion point | Top | Front |
| Use case | Function calls, undo | Scheduling, buffering |
Common mistakes
- Confusing Stack and Queue — Stack uses one end for both insert and delete; Queue uses TWO ends.
- Using list.pop(0) for large data — O(n) operation; prefer deque.popleft() for efficiency.
- Forgetting to check isEmpty before dequeue — causes IndexError / Underflow.
- Circular queue index update — always use modulo arithmetic; forgetting it causes index out-of-range errors.
Summary
A queue is a FIFO structure with enqueue (at rear) and dequeue (from front) operations. Python's collections.deque is the efficient implementation. Variants include circular queue, deque, and priority queue. Queues are fundamental to scheduling, buffering, and BFS algorithms.