Queue Theory: FIFO Principle

Having explored Stacks and their LIFO (Last-In, First-Out) behavior, let's now turn our attention to another fundamental Abstract Data Type (ADT): the Queue. While a stack is like a pile where you add and remove from the top, a queue operates more like a line, introducing a different but equally important principle.

1. The FIFO Principle

The defining characteristic of a Queue is its FIFO (First-In, First-Out) principle. This means that the first element added to the queue will always be the first one to be removed. It's an exact opposite to the LIFO principle of stacks.

Concept: Elements are added at one end (traditionally called the "rear" or "tail") and removed from the other end (traditionally called the "front" or "head").
Analogy:
- A waiting line: Think of customers waiting in line at a store, or cars waiting at a traffic light. The person (or car) who arrived first is the one who gets served (or moves) first.
- A printer queue: Documents sent to a printer are usually printed in the order they were received.
- A customer service call queue: Calls are typically answered in the order they were placed.

2. Core Queue Operations

Similar to stacks, queues are defined by a specific set of operations that manipulate their elements, adhering strictly to the FIFO rule.

2.1. Enqueue: `.enqueue(element)`

Adds a new element to the rear (tail) of the queue.

Concept:
1. Place the element at the back of the line.
2. Increment the queue's size.
Time Complexity: O(1) (typically constant time, as you're always operating on one specific end).
Space Complexity: O(1) (for the new element).

2.2. Dequeue: `.dequeue()`

Removes and returns the element from the front (head) of the queue.

Concept:
1. Check if the queue is empty. If so, indicate an error (or return null/undefined).
2. Remove the element currently at the front of the line.
3. Decrement the queue's size.
4. Return the removed element.
Time Complexity: O(1) (typically constant time, as you're always operating on one specific end).
Space Complexity: O(1)

2.3. Peek (or Front): `.peek()` / `.front()`

Returns the element at the front of the queue without removing it.

Concept:
1. Check if the queue is empty. If so, indicate an error.
2. Return the element currently at the front.
Time Complexity: O(1)
Space Complexity: O(1)

2.4. IsEmpty: `.isEmpty()`

Checks if the queue contains any elements.

Concept:
1. Return true if the queue's size is zero; otherwise, return false.
Time Complexity: O(1)
Space Complexity: O(1)

2.5. Size: `.size()`

Returns the number of elements currently in the queue.

Concept:
1. Return the current count of elements in the queue.
Time Complexity: O(1)
Space Complexity: O(1)

Key Takeaway: The FIFO principle is the defining characteristic of a queue. All fundamental operations, enqueue and dequeue, always happen at opposite ends, ensuring that elements are processed in the order they arrived, usually with efficient O(1) time complexity.