Queue Data Structure

A First In, First Out (FIFO) data structure where elements are added at the rear and removed from the front.

Definition

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means the first element added to the queue will be the first one to be removed. Think of it like a line of people waiting - the person who arrives first gets served first.

Key Properties

FIFO Principle

First In, First Out - oldest element is accessed first

Two Access Points

Front (dequeue) and Rear (enqueue)

Sequential Processing

Elements processed in order of arrival

Dynamic Size

Can grow and shrink as needed

Fair Scheduling

Ensures first-come-first-served order

Buffer Mechanism

Temporary storage for data processing

Queue Operations

Enqueue(element)

Adds an element to the rear of the queue

Time Complexity: O(1)

Dequeue()

Removes and returns the front element

Time Complexity: O(1)

Front() / Peek()

Returns the front element without removing it

Time Complexity: O(1)

isEmpty()

Checks if the queue is empty

Time Complexity: O(1)

Python Code Examples

Python Implementation

from collections import deque
import heapq

# Queue implementation using List
class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        """Add element to the rear"""
        self.items.append(item)

    def dequeue(self):
        """Remove element from the front"""
        if self.is_empty():
            return "Queue is empty"
        return self.items.pop(0)

    def front(self):
        """Get front element without removing"""
        if self.is_empty():
            return "Queue is empty"
        return self.items[0]

    def is_empty(self):
        """Check if queue is empty"""
        return len(self.items) == 0

    def size(self):
        """Return queue size"""
        return len(self.items)

    def display(self):
        """Display queue from front to rear"""
        return self.items.copy()

# Usage
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)

print("Queue:", queue.display())  # [10, 20, 30]
print("Front element:", queue.front())  # 10
print("Dequeued:", queue.dequeue())  # 10
print("Queue after dequeue:", queue.display())  # [20, 30]

# Using collections.deque (more efficient)
deque_queue = deque()
deque_queue.append(1)  # enqueue
deque_queue.append(2)
deque_queue.append(3)
print(deque_queue.popleft())  # 1 (dequeue)
print(deque_queue[0])  # 2 (front)

# Priority Queue using heapq
class PriorityQueue:
    def __init__(self):
        self.heap = []
        self.index = 0

    def enqueue(self, item, priority):
        """Add item with priority"""
        heapq.heappush(self.heap, (priority, self.index, item))
        self.index += 1

    def dequeue(self):
        """Remove highest priority item"""
        if self.is_empty():
            return "Queue is empty"
        return heapq.heappop(self.heap)[2]

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

# Usage
pq = PriorityQueue()
pq.enqueue("Task 1", 3)
pq.enqueue("Task 2", 1)
pq.enqueue("Task 3", 2)
print(pq.dequeue())  # "Task 2" (highest priority)

# Circular Queue implementation
class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.items = [None] * capacity
        self.front = 0
        self.rear = -1
        self.size = 0

    def enqueue(self, item):
        """Add element to the rear"""
        if self.is_full():
            return "Queue is full"
        self.rear = (self.rear + 1) % self.capacity
        self.items[self.rear] = item
        self.size += 1

    def dequeue(self):
        """Remove element from the front"""
        if self.is_empty():
            return "Queue is empty"
        item = self.items[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item

    def is_full(self):
        return self.size == self.capacity

    def is_empty(self):
        return self.size == 0

# Queue application: BFS (Breadth-First Search)
def bfs(graph, start):
    """Breadth-First Search using queue"""
    visited = set()
    queue = deque([start])
    result = []
    
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)
            # Add all unvisited neighbors to queue
            for neighbor in graph.get(vertex, []):
                if neighbor not in visited:
                    queue.append(neighbor)
    
    return result

# Example graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("BFS traversal:", bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

Common Use Cases

Task Scheduling

CPU scheduling, process management

Breadth-First Search

Graph traversal algorithms

Print Spooling

Managing print jobs

Call Center Systems

Customer service queue management

Buffer Management

Data streaming, I/O operations

Event Handling

GUI events, message queues

Web Server Requests

HTTP request processing

Cache Management

LRU cache implementation