Queue

Created : January 30, 2021

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)