=========================================================
SUBJECT: CS104 - Abstract Data Types
TOPIC: The Queue (FIFO)
=========================================================
### 1. WHAT IS A QUEUE?
A Queue is an Abstract Data Type (ADT) that follows the **FIFO (First-In, First-
Out)** principle. This is just like a real-world queue or line: the first person to
get in line is the first person to be served.
Elements are added to one end (the **rear** or **tail**) and removed from the other
end (the **front** or **head**).
### 2. CORE OPERATIONS
* **Enqueue:** Add an element to the rear of the queue.
* **Dequeue:** Remove the element from the front of the queue and return it.
* **Peek (or Front):** Look at the element at the front of the queue without
removing it.
* **isEmpty:** Check if the queue is empty.
### 3. IMPLEMENTATION & COMPLEXITY
A queue is typically implemented using a **Linked List** or an **Array** (often a
special type called a Circular Array to make it efficient).
| Operation | Time Complexity (Linked List / Circular Array) | Explanation
|
|-----------|------------------------------------------------|---------------------
-----------------------------------------|
| Enqueue | O(1) | Add to the tail of
the list or the rear of the array. |
| Dequeue | O(1) | Remove from the head
of the list or front of the array. |
| Peek | O(1) | Access the
head/front element. |
| Search | O(N) | Not a primary
operation; requires iterating through the queue.|
**Space Complexity:** O(N) for storing N elements.
### 4. COMMON USE CASES
* **Task Scheduling:** Operating systems use queues to schedule CPU tasks or I/O
requests.
* **Print Spooling:** Print jobs are added to a queue and printed in the order they
were received.
* **Breadth-First Search (BFS):** A core algorithm for traversing trees and graphs
uses a queue to keep track of nodes to visit.
* **Buffering:** Used in streaming data (like video) where data is added to a
buffer and consumed from it at a steady rate.
* **Asynchronous Processing:** Handling requests in web servers or message queues
in distributed systems.
