A queue is a data structure that adheres to the First-In-First-Out (FIFO) principle and is designed to hold a collection of elements.

Core Operations

• Enqueue: Adding an element to the end of the queue.
• Dequeue: Removing an element from the front of the queue.
• IsEmpty: Checks if the queue is empty.
• IsFull: Checks if the queue has reached its capacity.
• Peek: Views the front element without removal.

All operations have a space complexity of $O(1)$ and time complexity of $O(1)$, except for Search, which has $O(n)$ time complexity.

Key Characteristics

1. Order: Maintains the order of elements according to their arrival time.
2. Size: Can be either bounded (fixed size) or unbounded (dynamic size).
3. Accessibility: Typically provides only restricted access to elements in front and at the rear.
4. Time Complexity: The time required to perform enqueue and dequeue is usually $O(1)$.

Visual Representation

Real-World Examples

• Ticket Counter: People form a queue, and the first person who joined the queue gets the ticket first.
• Printer Queue: Print jobs are processed in the order they were sent to the printer.

Practical Applications

1. Task Scheduling: Used by operating systems for managing processes ready to execute or awaiting specific events.
2. Handling of Requests: Servers in multi-threaded environments queue multiple user requests, processing them in arrival order.
3. Data Buffering: Supports asynchronous data transfers between processes, such as in IO buffers and pipes.
4. Breadth-First Search: Employed in graph algorithms, like BFS, to manage nodes for exploration.
5. Order Processing: E-commerce platforms queue customer orders for processing.
6. Call Center Systems: Incoming calls wait in a queue before connecting to the next available representative.

Code Example: Queue

Here is the Python code:

from collections import deque

class Queue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.popleft()
        raise Exception("Queue is empty.")

    def size(self):
        return len(self.queue)

    def is_empty(self):
        return len(self.queue) == 0

    def front(self):
        if not self.is_empty():
            return self.queue[0]
        raise Exception("Queue is empty.")

    def rear(self):
        if not self.is_empty():
            return self.queue[-1]
        raise Exception("Queue is empty.")

# Example Usage
q = Queue()
q.enqueue(5)
q.enqueue(6)
q.enqueue(3)
q.enqueue(2)
q.enqueue(7)
print("Queue:", list(q.queue))
print("Front:", q.front())
print("Rear:", q.rear())
q.dequeue()
print("After dequeue:", list(q.queue))