A Queue is a data structure that operates on the FIFO (First In, First Out) principle, meaning "first in, first out." It resembles a real-life line at a store: the first person to join the queue is the first to be served.

Basic Queue Operations

  1. enqueue(x) — Adds element x to the end (rear) of the queue.
  1. dequeue() — Removes and returns the element from the front of the queue.
  1. front() / peek() — Views the first element without removing it.
  1. is_empty() — Checks whether the queue is empty.
  1. size() — Returns the number of elements in the queue.

Implementation Approaches

A queue can be implemented in several ways:

  1. Array-based (list in Python):
  2. Simple method, but operations can be slow due to the need to shift elements.
  1. Using Two Stacks:
  2. Often used in algorithmic problems to optimize operations.
  1. Linked List-based:
  2. Fast implementation without the need to shift elements.
  1. Built-in Structures:
  2. In Python — collections.deque or queue.Queue.

Use Cases

Queues are applied in the following scenarios:

  1. Task Scheduling: (e.g., CPU task execution).
  1. Data Processing: (e.g., streaming data reading).
  1. Real-world Modeling: (e.g., customer queues in a bank or shop).
  1. Graph Algorithms: (e.g., BFS — Breadth-First Search).

Advantages of a Queue

  • Simplicity of implementation.
  • High efficiency of operations (when shifting elements is not required, unlike plain dynamic lists).

Disadvantages of a Queue

  • Restricted access: You can only interact with the front and rear of the queue.
  • Fixed capacity: If implemented using a standard array, it may be limited in size.