In this article at OpenGenus, we will explore the implementation of a Queue in Python using the principles of Object-Oriented Programming (OOP). By utilizing OOP concepts in Python, we can create and manipulate queues in a structured and efficient manner.

Table of contents:

1. Introduction
2. Solution
3. Quiz

Introduction

In object-oriented programming (OOP), a queue is a data structure that follows the First-In-First-Out (FIFO) principle. It behaves like a real-world queue or line where the first person who joins the queue is the first one to be served. In Python, we can implement a queue using OOP concepts. It is commonly used in programming and computer science to manage data in a specific order.

An object-oriented approach allows us to encapsulate the queue's behavior and data within a class. The class represents the blueprint for creating individual queue objects. By encapsulating the behavior of a queue within a class, we can create multiple instances of the queue and manipulate them independently. Each instance maintains its own state, including the data it holds and its size. This encapsulation promotes code modularity, reusability, and organization. Additionally, the queue can be implemented using either an array (list) or a linked list in Python.

Solution

A queue class typically provides methods to perform common operations on the queue.

• Enqueue: The enqueue operation adds an item to the end of the queue. It represents inserting an element into the queue, and the newly added item becomes the last element in the queue.

• Dequeue: The dequeue operation removes and returns the item at the front of the queue. It represents removing the first item that was added to the queue, following the FIFO principle.

• Is Empty: This operation checks if the queue is empty, meaning it has no elements in it. It returns a boolean value indicating whether the queue is empty or not.

• Size: The size operation returns the number of elements currently present in the queue. It provides information about the current size or length of the queue.

• Peek: The peek operation allows accessing the item at the front of the queue without removing it. It returns the value of the first item in the queue, giving a glimpse of what is currently at the front.

• Display: The display operation in a queue class is used to show the elements present in the queue. It provides a way to visualize the contents of the queue.

Node Class

The Node class represents a single node in a linked list. It has two attributes: data, which stores the data value of the node, and next, which points to the next node in the linked list.

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

Queue Class

The Queue class serves as the base class for the queue implementation. It has three methods: init initializes the queue with size 0, is_empty checks if the queue is empty, and get_size returns the size of the queue.

class Queue:
    def __init__(self):
        self.size = 0

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

    def get_size(self):
        return self.size

ArrayListQueue Class

The ArrayListQueue class represents a queue implementation using an array-based list structure. It inherits from the Queue class, which provides the basic queue operations such as checking if the queue is empty, getting the size, and displaying the queue. The ArrayListQueue class overrides the inherited methods from the Queue class and provides its own implementations for enqueueing, dequeueing, peeking, and displaying elements.

The enqueue method adds an element to the end of the queue list by using the append method. It appends the given data to the list and increments the size attribute to reflect the added element.

The dequeue method removes and returns the element at the front of the queue list. It uses the pop method with an index of 0 to remove and retrieve the first element from the list. The method also decrements the size attribute to reflect the removed element.

The peek method returns the element at the front of the queue list without removing it. It simply accesses the element at index 0 in the list. The display method prints the elements in the queue list. If the queue is empty, it prints a message indicating that the queue is empty. Otherwise, it prints the entire contents of the queue list.

class ArrayListQueue(Queue):
    def __init__(self):
        super().__init__()
        self.queue = []

    def enqueue(self, data):
        self.queue.append(data)
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            return None
        self.size -= 1
        return self.queue.pop(0)

    def peek(self):
        if self.is_empty():
            return None
        return self.queue[0]

    def display(self):
        if self.is_empty():
            print("Queue is empty.")
        else:
            print("Queue:", self.queue)

LinkedList Queue

The LinkedListQueue class represents a queue implementation using a linked list data structure. It inherits from the Queue class, which provides the basic queue operations such as checking if the queue is empty, getting the size, and displaying the queue. The LinkedListQueue class has an additional Node class, which represents a single node in the linked list. Each node contains a data attribute to store the element and a next attribute to reference the next node in the list. The LinkedListQueue class overrides the inherited methods from the Queue class and provides its own implementations for enqueueing, dequeueing, peeking, and displaying elements.

The enqueue method adds an element to the end of the linked list by creating a new node with the given data and updating the tail attribute to point to the new node. If the queue is empty, both the head and tail attributes are set to the new node. The size attribute is incremented to reflect the added element.

The dequeue method removes and returns the element at the front of the queue. It updates the head attribute to point to the next node in the list and checks if the queue becomes empty after the removal. If so, the tail attribute is also set to None. The size attribute is decremented to reflect the removed element.

The peek method returns the element at the front of the queue without removing it. It simply accesses the data attribute of the head node. The display method prints the elements in the queue by traversing the linked list from the head node to the tail node. It prints each element's data and moves to the next node until reaching the end of the list.

class LinkedListQueue(Queue):
    def __init__(self):
        super().__init__()
        self.head = None
        self.tail = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            return None
        removed_node = self.head
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return removed_node.data

    def peek(self):
        if self.is_empty():
            return None
        return self.head.data

    def display(self):
        if self.is_empty():
            print("Queue is empty.")
        else:
            current = self.head
            print("Queue:", end=" ")
            while current:
                print(current.data, end=" ")
                current = current.next
            print()

Queue Implementation using ArrayList and LinkedList

In the code, two different queue implementations are created: ArrayListQueue and LinkedListQueue. These implementations inherit from a base Queue class and provide their specific functionality.

The ArrayListQueue implementation uses a Python list to store the elements. The enqueue method adds elements to the end of the list, while the dequeue method removes and returns the first element from the list. The peek method allows accessing the first element without removing it. The is_empty and get_size methods provide information about the state and size of the queue. The display method prints the contents of the queue.

The LinkedListQueue implementation uses a linked list data structure to store the elements. The enqueue method adds nodes to the end of the linked list, and the dequeue method removes and returns the first node. Similarly, the peek method allows accessing the data of the first node without removing it. The is_empty and get_size methods provide information about the state and size of the queue. The display method traverses the linked list and prints the data of each node.

arr_queue = ArrayListQueue()
arr_queue.enqueue(10)
arr_queue.enqueue(20)
arr_queue.enqueue(30)
arr_queue.display()
print("Peek:", arr_queue.peek())
print("Size:", arr_queue.get_size())
print("Is Empty:", arr_queue.is_empty())
print("Dequeue:", arr_queue.dequeue())
arr_queue.display()

ll_queue = LinkedListQueue()
ll_queue.enqueue(10)
ll_queue.enqueue(20)
ll_queue.enqueue(30)
ll_queue.display()
print("Peek:", ll_queue.peek())
print("Size:", ll_queue.get_size())
print("Is Empty:", ll_queue.is_empty())
print("Dequeue:", ll_queue.dequeue())
ll_queue.display()

Complete Implementation

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

class Queue:
    def __init__(self):
        self.size = 0

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

    def get_size(self):
        return self.size


class ArrayListQueue(Queue):
    def __init__(self):
        super().__init__()
        self.queue = []

    def enqueue(self, data):
        self.queue.append(data)
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            return None
        self.size -= 1
        return self.queue.pop(0)

    def peek(self):
        if self.is_empty():
            return None
        return self.queue[0]

    def display(self):
        if self.is_empty():
            print("Queue is empty.")
        else:
            print("Queue:", self.queue)


class LinkedListQueue(Queue):
    def __init__(self):
        super().__init__()
        self.head = None
        self.tail = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            return None
        removed_node = self.head
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return removed_node.data

    def peek(self):
        if self.is_empty():
            return None
        return self.head.data

    def display(self):
        if self.is_empty():
            print("Queue is empty.")
        else:
            current = self.head
            print("Queue:", end=" ")
            while current:
                print(current.data, end=" ")
                current = current.next
            print()

arr_queue = ArrayListQueue()
arr_queue.enqueue(10)
arr_queue.enqueue(20)
arr_queue.enqueue(30)
arr_queue.display()  
print("Peek:", arr_queue.peek())  
print("Size:", arr_queue.get_size()) 
print("Is Empty:", arr_queue.is_empty())
print("Dequeue:", arr_queue.dequeue())
arr_queue.display()  

ll_queue = LinkedListQueue()
ll_queue.enqueue(10)
ll_queue.enqueue(20)
ll_queue.enqueue(30)
ll_queue.display() 
print("Peek:", ll_queue.peek()) 
print("Size:", ll_queue.get_size())  
print("Is Empty:", ll_queue.is_empty())
print("Dequeue:", ll_queue.dequeue())
ll_queue.display() 

Output

Queue: [10, 20, 30]
Peek: 10
Size: 3
Is Empty: False
Dequeue: 10
Queue: [20, 30]
Queue: 10 20 30 
Peek: 10
Size: 3
Is Empty: False
Dequeue: 10
Queue: 20 30 

Time and Space Complexity

TIME COMPLEXITY

Enqueue Operation (enqueue(item)): The enqueue operation has a time complexity of O(1).

Dequeue Operation (dequeue()): The dequeue operation has a time complexity of O(n) in the worst case, where n is the number of elements in the queue.

Is Empty Operation (is_empty()): The is_empty operation has a time complexity of O(1).

Size Operation (size()): The size operation has a time complexity of O(1).

Peek Operation (peek()): The peek operation has a time complexity of O(1).

Display Operation (display()): The display operation has a time complexity of O(n), where n is the number of elements in the queue.

SPACE COMPLEXITY

The space complexity of the queue implementation is O(n), where n is the number of elements in the queue.

Output Explanation

Queue: [10, 20, 30]: This line displays the elements in the queue after enqueueing three elements (10, 20, and 30).

Peek: 10: This line prints the value at the front of the queue.

Size: 3: This line prints the current size of the queue.

Is Empty: False: This line checks if the queue is empty.

Dequeue: 10: This line removes and returns the first element from the queue.

Queue: [20, 30]: This line displays the updated queue after dequeuing an element. The element 10 is removed, and the remaining elements are [20, 30].

Queue: 10 20 30: This line displays the elements in the queue after enqueueing three elements (10, 20, and 30).

Peek: 10: This line prints the value at the front of the queue.

Size: 3: This line prints the current size of the queue.

Is Empty: False: This line checks if the queue is empty.

Dequeue: 10: This line removes and returns the first element from the queue.

Queue: 20 30: This line displays the updated queue after dequeuing an element. The element 10 is removed, and the remaining elements are 20, 30.

How OOP Concepts Are Used

• Classes: The code defines several classes, such as Node, Queue, ArrayListQueue, and LinkedListQueue. Classes are used to encapsulate related data and behavior into reusable entities.

• Encapsulation: Each class encapsulates its own data and methods, providing an abstraction of the underlying data structure and operations. For example, the ArrayListQueue class encapsulates the ArrayList-based implementation of a queue, while the LinkedListQueue class encapsulates the LinkedList-based implementation.

• Inheritance: The ArrayListQueue and LinkedListQueue classes inherit from the base Queue class. Inheritance allows the derived classes to inherit properties and methods from the base class, promoting code reuse and modularity. The derived classes inherit the is_empty, get_size, enqueue, dequeue, peek, and display methods from the Queue class.

Quiz