Written in Python.

• Linear data structure
• FIFO (First-In First-Out)
• Insertion: rear
• Deletion: front

• Example

  • waiting in the queue to enter a restaurant
• Useful in streaming, BFS

Basic Operations

• enqueue or put: Add an item at the rear.

  • If the queue is full → Overflow condition
  • append(item)

• dequeue or get: Remove an item from the front.

  • If the queue is empty → Underflow condition
  • pop(0)
• front: Get the front item from queue.
• rear: Get the last item from queue.

Big-O Complexity for Queue

• Time complexity

  • Insertion/Deletion: O(1)
  • Access/Search: O(n)
• Space complexity: O(n)

Implementation

# Create queue class
class Queue:
  # Initialize
  def __init__(self):
    self.items = []

  # Add an item to the end
  def enqueue(self, item):
    self.items.append(item)
  
  # Remove an item from the front
  def dequeue(self):
    # Check if stack is not empty
    if not self.isEmpty():
      return self.items.pop(0)
    else:
      print('Stack underflow')
      exit()

  # Check if stack is empty
  def isEmpty(self):
    return len(self.items) == 0

  # Return size of stack
  def size(self):
    return len(self.items)