Implement Queue Data Structure in Python Using a Linked List

Rate this post

πŸ’‘ Problem Formulation: The objective is to design a Python program that efficiently implements the queue data structure using a linked list. In a queue, elements are added at one end (the rear or tail) and removed from the other (the front or head), following First-In-First-Out (FIFO) order. For example, input operations like enqueue(10), enqueue(20), dequeue() should result in the output being 10 (the first element added is the first one to be removed).

Method 1: Using Node Class and Two Pointers

An intuitive approach to implement a queue using a linked list is to create a Node class defining each element, and then maintain two pointers, ‘front’ and ‘rear’, to keep track of the queue’s ends. Enqueue operations will update the rear pointer, whereas dequeue operations will update the front pointer.

Here’s an example:

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

class Queue:
    def __init__(self):
        self.front = self.rear = None

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

    def enqueue(self, item):
        temp = Node(item)
        if self.rear is None:
            self.front = self.rear = temp
            return
        self.rear.next = temp
        self.rear = temp

    def dequeue(self):
        if self.isEmpty():
            return None
        temp = self.front
        self.front = temp.next
        if(self.front is None):
            self.rear = None
        return temp.value

q = Queue()
q.enqueue(10)
q.enqueue(20)
print(q.dequeue())
print(q.dequeue())

Output:

10
20

This code demonstrates a queue implementation where the enqueue() method adds a new element to the end of the linked list (queue), and the dequeue() method removes the element at the front, returning its value. The isEmpty() helper method checks whether the queue is empty, a condition needed for dequeue operation.

Method 2: Using Collections.deque for Internally Linked List Operations

Python’s collection module has a deque class that can be used to represent a queue with efficient append and pop operations. By utilizing deque, one can leverage its doubly linked list properties and build a queue without explicitly managing the pointers and nodes.

Here’s an example:

from collections import deque

class Queue:
    def __init__(self):
        self.queue = deque()
    
    def enqueue(self, item):
        self.queue.append(item)
    
    def dequeue(self):
        return self.queue.popleft() if self.queue else None

q = Queue()
q.enqueue(10)
q.enqueue(20)
print(q.dequeue())
print(q.dequeue())

Output:

10
20

Here, Queue utilizes the deque object for queue operations. The enqueue() function appends elements to the right end of the deque, while the dequeue() function pops elements from the left end, mimicking the queue behavior.

Method 3: Using Single Pointer with a Tail Reference

Another simple method is to use a singular pointer ‘front’ but keep a reference to the last node ‘tail’ directly within each Node to facilitate O(1) time complexity for enqueue operations, thus removing the need for a separate ‘rear’ pointer.

Here’s an example:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.tail = None  # Reference to the tail node

class Queue:
    def __init__(self):
        self.front = None

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

    def enqueue(self, item):
        if self.isEmpty():
            self.front = self.tail = Node(item)
        else:
            self.tail.next = Node(item)
            self.tail = self.tail.next

    def dequeue(self):
        if self.isEmpty():
            return None
        result = self.front.value
        self.front = self.front.next
        return result

q = Queue()
q.enqueue(10)
q.enqueue(20)
print(q.dequeue())
print(q.dequeue())

Output:

10
20

In this code snippet, when enqueueing, we update the next pointer of the old tail to point to the new node and then the tail reference of every node now points to the actual tail node of the queue. When dequeueing, we simply move the front pointer to the next in line.

Bonus One-Liner Method 5: Using List with Encapsulation

While not recommended due to potential performance issues on large queues, Python lists can be used as a quick and easy queue by encapsulating list operations to respect queue operations, such as using append for enqueue and pop with an index for dequeue.

Here’s an example:

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

    def enqueue(self, item):
        self.items.append(item)
    
    def dequeue(self):
        return self.items.pop(0) if self.items else None

q = Queue()
q.enqueue(10)
q.enqueue(20)
print(q.dequeue())
print(q.dequeue())

Output:

10
20

This snippet shows the queue implementation by using a regular list. The enqueue() method adds to the end of the list, and the dequeue() method removes from the beginning of the list. Note, this has O(n) time complexity for dequeue due to list index shifting.

Summary/Discussion

  • Method 1: Node Class with Two Pointers. Provides a clear data structure with O(1) enqueue and dequeue operations. However, it requires manual management of the node and pointers.
  • Method 2: Using Collections.deque. Offers simplicity and readability while still being very performant with O(1) operations, but doesn’t explicity demonstrate linked list operations.
  • Method 3: Single Pointer with Tail Reference. Simplifies the tracking of nodes but preserves the O(1) queue operations. Can be slightly less intuitive when tracking the tail within each node.
  • Bonus One-Liner Method 5: Using List with Encapsulation. It’s a straightforward implementation with native Python lists that’s quick to write but inefficient for larger queues, especially during dequeue operations due to its O(n) complexity.