1. Simple Queue

  • Basic FIFO structure.
  • Use a list or collections.deque in Python.

2. Circular Queue

  • The last position connects back to the first to form a circle.

3. Priority Queue

  • Elements are dequeued based on priority, not arrival time.
  • Use Python’s heapq module for implementation.

4. Double-Ended Queue (Deque)

  • Elements can be added or removed from both ends.
  • Use collections.deque for an efficient implementation.

Common Operations

  1. Enqueue: Add an element to the back of the queue.
  2. Dequeue: Remove an element from the front of the queue.
  3. Peek/Front: View the element at the front of the queue without removing it.
  4. IsEmpty: Check if the queue is empty.

Queue Implementation Examples

1. Simple Queue Using Deque

from collections import deque

class SimpleQueue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, value):
        self.queue.append(value)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.queue.popleft()

    def peek(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.queue[0]

    def is_empty(self):
        return len(self.queue) == 0

2. Priority Queue

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def enqueue(self, value):
        heapq.heappush(self.heap, value)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return heapq.heappop(self.heap)

    def peek(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.heap[0]

    def is_empty(self):
        return len(self.heap) == 0

BFS With Queue

Breadth-first search (BFS) is one of the most common applications of a queue.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")
            queue.extend(graph[node] - visited)