Queue

A queue is a fundamental linear data structure that follows the First-In, First-Out (FIFO) principle. This means the first element added to the queue will be the first one to be removed. It's analogous to a real-world waiting line at a ticket counter or a supermarket, where people are served in the order they arrived. This principle makes queues suitable for scenarios where the order of processing is critical.

The primary operations associated with a queue are:
- Enqueue (or `add`/`put`): Adds an element to the rear (back) of the queue. The new element waits at the end of the line.
- Dequeue (or `remove`/`get`): Removes an element from the front of the queue. The element that has been waiting the longest is removed and processed.

Other common operations include:
- Front (or `peek`): Returns the element at the front of the queue without removing it. It allows inspecting the next element to be processed.
- IsEmpty: Checks if the queue contains any elements.
- Size: Returns the number of elements currently in the queue.

Queues can be implemented using various underlying data structures, such as arrays or linked lists. In Python, the standard library provides highly efficient and convenient ways to implement queues:

1. `collections.deque` (Double-Ended Queue): This is a list-like container that allows fast appends and pops from both ends. For implementing a standard FIFO queue, `deque` is an excellent choice as its `append()` (enqueue) and `popleft()` (dequeue) operations run in O(1) (constant) time. It is generally preferred for basic queue functionality in single-threaded contexts.

2. `queue.Queue`: This module provides several thread-safe queue implementations, such as `queue.Queue`, `queue.LifoQueue` (for LIFO), and `queue.PriorityQueue`. `queue.Queue` is specifically designed for multithreaded programming to facilitate communication between threads safely, preventing race conditions. It includes features like blocking operations (`get(block=True)`) that wait until an item is available or space becomes free.

Queues are widely used in various computer science applications and algorithms, including:
- Task Scheduling: Managing jobs or processes in an operating system or a server.
- Breadth-First Search (BFS): An algorithm for traversing graphs or trees level by level.
- Spooling: Handling print jobs, where documents are printed in the order they were sent.
- Buffer Management: Handling data streams or network packets, ensuring they are processed in order.
- Event Handling: Processing events in the order they occur.

import collections
import queue

 --- Using collections.deque as a simple Queue (efficient and common for general use) ---
print("--- Using collections.deque as a Queue ---")
my_queue = collections.deque()

 Enqueue elements (add to the right/rear)
print("Enqueuing elements...")
my_queue.append("Task A")
my_queue.append("Task B")
my_queue.append("Task C")
print(f"Current Queue: {list(my_queue)}")  Convert to list for easy printing

 Peek at the front element (element at the left/front)
if my_queue:
    print(f"Front element (peek): {my_queue[0]}")

 Dequeue elements (remove from the left/front)
print("\nDequeuing elements...")
if my_queue:
    dequeued_item = my_queue.popleft()
    print(f"Dequeued: {dequeued_item}")
print(f"Queue after first dequeue: {list(my_queue)}")

if my_queue:
    dequeued_item = my_queue.popleft()
    print(f"Dequeued: {dequeued_item}")
print(f"Queue after second dequeue: {list(my_queue)}")

 Check queue size
print(f"\nCurrent queue size: {len(my_queue)}")

 Check if queue is empty
print(f"Is queue empty? {not bool(my_queue)}")

 Enqueue another element
print("\nEnqueuing Task D...")
my_queue.append("Task D")
print(f"Queue after enqueuing Task D: {list(my_queue)}")

 Dequeue all remaining elements
print("\nDequeuing all remaining elements:")
while my_queue:
    print(f"Dequeuing: {my_queue.popleft()}")
print(f"Queue after dequeuing all: {list(my_queue)}")
print(f"Is queue empty now? {not bool(my_queue)}")


 --- Using queue.Queue for multithreaded scenarios (thread-safe) ---
print("\n--- Using queue.Queue (thread-safe for multithreading) ---")
thread_safe_queue = queue.Queue()  Max size can be specified, e.g., queue.Queue(maxsize=3)

 Enqueue elements (using put)
print("Enqueuing elements...")
thread_safe_queue.put("Job 1")
thread_safe_queue.put("Job 2")
print(f"Queue size: {thread_safe_queue.qsize()}")

 Dequeue elements (using get)
print("\nDequeuing elements...")
if not thread_safe_queue.empty():
    dequeued_job = thread_safe_queue.get()  By default, this blocks until an item is available
    print(f"Dequeued: {dequeued_job}")
    thread_safe_queue.task_done()  Indicate that a retrieved task is complete
print(f"Queue size: {thread_safe_queue.qsize()}")

if not thread_safe_queue.empty():
    dequeued_job = thread_safe_queue.get()
    print(f"Dequeued: {dequeued_job}")
    thread_safe_queue.task_done()
print(f"Queue size: {thread_safe_queue.qsize()}")

print(f"Is thread-safe queue empty? {thread_safe_queue.empty()}")