B2.2.4 Concept of a Queue as a "First In, First Out" (FIFO) Data Structure Notes

The Concept of a Queue as a "First In, First Out" (FIFO) Data Structure

1. A queue is a fundamental data structure that operates on the principle of First In, First Out (FIFO).
2. This means that the first element added to the queue is the first one to be removed, much like a line of people waiting for service.

Core Operations of a Queue

1. Enqueue: Adds an element to the back of the queue.
2. Dequeue: Removes the element from the front of the queue.
3. Front: Returns the element at the front without removing it.
4. isEmpty: Checks if the queue is empty.

Implementing a Queue

1. Array-based Queue: Fixed size, uses indices for front and rear.
2. Linked List Queue: Dynamic, grows/shrinks as needed.
3. Circular Queue: Optimized version of array queue; reuses empty spaces.

queue = []

# Enqueue
queue.append("A")

# Dequeue
item = queue.pop(0)

# Peek
front = queue[0] if queue else None

import java.util.LinkedList;
import java.util.Queue;

Queue<String> q = new LinkedList<>();
q.add("A");       // Enqueue
q.remove();       // Dequeue
q.peek();         // Front
q.isEmpty();      // Check empty

Performance and Memory Usage

1. Enqueue/Dequeue: O(1) for well-implemented queues (linked list or circular array).
2. Static Queues: Fixed size, simple but risk overflow or wasted memory.
3. Dynamic Queues: Flexible but may need extra memory (pointers, resizing).

Choosing the Right Queue for a Problem

1. Static Queue → when maximum size is known (e.g., buffering a fixed number of items).
2. Dynamic Queue → when size is unpredictable (e.g., network packet management).
3. Circular Queue → efficient memory reuse in resource-limited environments.

Applications of Queues

1. Task Scheduling: OS process scheduling, printer job queues.
2. Networking: Routers and switches manage packet queues.
3. Simulations: Customer service lines, traffic lights, and other real-world wait systems.
4. Breadth-First Search (BFS): In graph traversal and shortest path algorithms.