DSA Series Chapter 6 – QUEUE (Python Version)

on


 [Follow here] for daily coding insights

DSA Series – QUEUE (Python Version)

Labels: Data Structures, Queue, Linear Data Structures, Python DSA

1. Queue Introduction (Python Perspective)

A Queue processes data in the order it arrives:

  • Insert at rear → enqueue()

  • Remove from front → dequeue()

Real-world uses:

  • BFS traversal

  • CPU scheduling

  • Task/job queues

  • Network buffering

  • Printers queue

  • Simulation systems

2. Queue Using Python List (Not Recommended for Large Data)

Python lists allow append at end, but deletion from front is O(n) (slow), because it shifts elements.

Code:

class QueueList:
    def __init__(self):
        self.items = []

    def enqueue(self, value):
        self.items.append(value)   # O(1)
        print(f"{value} inserted")

    def dequeue(self):
        if self.is_empty():
            print("Queue is EMPTY")
            return None
        value = self.items.pop(0)   # O(n) - shifting occurs
        print(f"{value} removed")
        return value

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

    def display(self):
        print("Queue:", self.items)


Explanation of the Code


1. __init__()
Initializes an empty list which will act as the queue.
2. enqueue(data)
  • Uses append() to add an element at the end.
  • This is O(1) in Python because append doesn’t shift elements.
3. dequeue()
  • Uses pop(0) to remove the first element.
  • This is O(n) because all remaining elements shift one position.
4. peek()
Returns the first element without removing.


5. is_empty()
Checks whether the queue has no elements.
6. display()
Prints the entire list as a queue.

3. Queue Using collections.deque (Highly Recommended)

deque provides O(1) insertions and deletions from both ends.

Code:

from collections import deque

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

    def enqueue(self, value):
        self.queue.append(value)   # O(1)
        print(f"{value} inserted")

    def dequeue(self):
        if self.is_empty():
            print("Queue is EMPTY")
            return None
        value = self.queue.popleft()  # O(1)
        print(f"{value} removed")
        return value

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

    def display(self):
        print("Queue:", list(self.queue))

Why deque is best?

  • No shifting

  • Efficient memory management

  • Fast append/pop at both ends

  • Built specifically for queues

4. Queue Using Linked List (Manual Implementation)

This gives full control like in C and is best for learning DSA.

Node Class

class Node:
    def __init__(self, value):
        self.data = value
        self.next = None

Queue Class (Linked List)

class LinkedListQueue:
    def __init__(self):
        self.front = None   # Points to first node
        self.rear = None    # Points to last node

    def is_empty(self):
        return self.front is None

    def enqueue(self, value):
        newNode = Node(value)

        # If empty queue
        if self.rear is None:
            self.front = self.rear = newNode
            print(f"{value} inserted")
            return

        # Add to end
        self.rear.next = newNode
        self.rear = newNode
        print(f"{value} inserted")

    def dequeue(self):
        if self.front is None:
            print("Queue is EMPTY")
            return None

        value = self.front.data
        self.front = self.front.next

        # If queue becomes empty
        if self.front is None:
            self.rear = None

        print(f"{value} removed")
        return value

    def display(self):
        if self.front is None:
            print("Queue is EMPTY")
            return
        
        temp = self.front
        print("Queue:", end=" ")
        while temp:
            print(temp.data, end=" ")
            temp = temp.next
        print()


Explanation of the Code
1. Node Class
  • Each node stores data and a pointer to the next node.
  • Equivalent to C structure:
    struct Node {
    int data;
    struct Node* next;
};
2. QueueLinkedList Initialization


  • front → first node
  • rear → last node
    
Initially both are None because queue is empty.
3. enqueue(data)
  • Create a new node.
  • If queue is empty:
    • Set both front and rear to new node.
  • Otherwise:
    • Add new node after the current rear.
    • Update rear to the new node.
  • This is O(1) because we directly access the rear.
4. dequeue()
  • If queue empty → underflow.
  • Store the front node.
  • Move front to next node.
  • If queue becomes empty → set rear = None.
  • Return removed node’s data.
  • This is O(1) because no shifting.
5. peek()
Returns the value of front node without removing it.
6. is_empty()
Checks whether queue has any nodes.
7. display()
Traverses from front to rear and prints nodes.

5. Example Run

q = LinkedListQueue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
q.display()
q.dequeue()
q.display()

Output

10 inserted
20 inserted
30 inserted
Queue: 10 20 30
10 removed
Queue: 20 30

6. Time & Space Complexity

Operation List deque Linked List
Enqueue O(1) O(1) O(1)
Dequeue O(n) (slow) O(1) O(1)
Space O(n) O(n) O(n)

7. When to Use Which Queue Implementation?

Situation Best Choice
Fast queue operations deque
Pure DSA learning Linked list queue
Simple scripting tasks Python list
BFS, job queues, simulations deque
Unlimited dynamic growth Linked list queue


ALSO CHECK 

DS(Data Structure) Python&C Edition

DSA Series Chapter 1 Time & Space Complexity ( C Edition)

DSA Series Chapter 2 Arrays  (C Version)


DSA Series Chapter 2 Arrays  (Python Version)

DSA Series Chapter 3 Strings (C Version)


DSA Series Chapter 3 Strings (Python Version)


DSA Series Chapter 4 Linked Lists (Python Version)


DSA Series Chapter 4 Linked Lists (C Version)


DSA Series Chapter 5 Stacks (Python Version)


DSA Series Chapter 5  Stacks  (C Version)











Tail Recursion Optimization: How Compilers Convert Recursion Into Iteration


Advanced Recursion: Memoization vs. Tabulation — The Deep Optimization Blueprint for Professionals


Advanced Sorting Algorithms: Merge Sort Internals — Merge Tree, Cache Behavior & Real Cost Analysis


Enjoyed this post? [Follow here] for daily coding insights.

Comments

Post a Comment