What do you know about the data structure 'queue'?

Queue — a linear data structure implementing the FIFO (First-In, First-Out) principle: the first added element will be the first to be removed.

Main operations:

• enqueue: adding an element to the end of the queue.
• dequeue: removing an element from the beginning of the queue.
• peek (or front): viewing the value of the element at the front of the queue without removing it.
• is_empty: checking if the queue is empty.
• size: getting the current number of elements in the queue.

Implementations:

• List: Inefficient for large queues due to O(n) when removing from the front (shifting elements).

  # Adding
  queue = []
  queue.append(item)
  
  # Removing
  if queue:
      item = queue.pop(0) # O(n) operation
  

• collections.deque: A doubly linked list optimized for fast addition/removal from both ends. O(1) for enqueue and dequeue.

  import collections
  
  # Creating
  queue = collections.deque()
  
  # Adding
  queue.append(item) # O(1)
  
  # Removing
  if queue:
      item = queue.popleft() # O(1)
  

• queue.Queue: Thread-safe implementation for multi-threaded applications. Uses collections.deque internally. Methods put() and get() are thread-safe.

  import queue
  
  # Creating
  q = queue.Queue()
  
  # Enqueue (can use timeout)
  q.put(item)
  
  # Dequeue (can use timeout or blocking)
  try:
      item = q.get(block=False) # non-blocking call
  except queue.Empty:
      pass # Queue is empty
      
  # Indicate successful processing of an item
  q.task_done() 
  

Applications:

• Handling server requests.
• Data buffering.
• Implementing algorithms (e.g., Breadth-First Search - BFS).
• Thread-safe interaction between threads (using queue.Queue).