Queue in Python

The queues data structure in which data is inserted and removed in a 'First in First out' or FIFO format. That is the last added element will get extracted last, and the one added the earliest will get extracted first.

Queues are implemented in different programming languages in different ways. They are often used during the procedural execution of commands or programs.
d110

Operations on Queues

The front and rear variables hold the respective elements of the queue for reference during the addition and deletion of elements.

  1. enqueue() - It is used to add data to the queue tail, the rear variable is updated to the new value
  2. dequeue() - It is used to delete the data at the front of the queue, that is the earliest added data, and the front variable gets updated
  3. front() - It is used to return the value of the frontmost element of the queue
  4. rear() - It is used to return the value of the rearmost element or the tail element of the queue
  5. empty() - It is used to check whether a queue is empty or not

Queue implementation with Python Lists

Queues in Python can be implemented using the object-oriented programming feature of Python, that is classes.

The List built-in data structure in Python can be used to implement the queue. Elements can be appended and removed to simulate the enqueue() and dequeue() methods of queues. This can be achieved in Python via classes as follows:

Steps to define a class to implement a queue

  1. Define the queue class
    class queue:​
  2. Define the class initialization step along with the empty Python list which will act as the queue, and the front and rear variables
        def __init__(self):
            self.queue_ds = []
            self.Front = -1
            self.Rear = -1​
  3. Define the enqueue() method, which is used to add elements to the rear of the queue and thus update the respective front and rear variables
        def enqueue(self, val):
            self.queue_ds.append(val)
            if self.Front == -1:
                self.Front += 1
                self.Rear += 1
            else:
                self.Rear += 1​
  4. Define the dequeue() method, which is used to extract elements from the front end of the queue and thus update the respective front and rear variables
        def dequeue(self):
            if self.empty() is True:
                print("Queue is empty")
                return
            else:
                temp = self.queue_ds.pop(self.Front)
                self.Rear -= 1
                if self.empty() is True:
                    self.Front = -1
                    self.Rear = -1
                return temp​
  5. Define the front() method, which returns the variable that holds the front index of the queue
        def front(self):
            if self.empty() is True:
                print("Queue empty")
            return self.Front​
  6. Define the rear() method, which returns the variable that holds the rear index of the queue
        def rear(self):
            if self.empty() is True:
                print("Queue empty")
            return self.Rear​
  7. Define the empty() method, which is used to check whether a queue is empty or not
        def empty(self):
            if len(self.queue_ds) == 0:
                return True
            else:
                return False​
  8. Define the display() function, which is used to display the queue in an user-comprehendible format
        def display(self):
            if self.empty() is True:
                print("Queue empty")
                return
            print("The Queue")
            if self.Front == self.Rear:
                print(self.queue_ds[self.Front], "<== Front <== Rear")
                return
            print(self.queue_ds[self.Front], "<== FRONT")
            i = self.Front + 1
            while i < self.Rear:
                print(self.queue_ds[i])
                i += 1
            print(self.queue_ds[self.Rear], "<== REAR")
            print("The Queue Ends")
  9. After assembling the entire program, creating an instance of the queue class, implementing the methods used to manipulate it, and lastly compiling the program
    class queue:
        def __init__(self):
            self.queue_ds = []
            self.Front = -1
            self.Rear = -1
    
        def enqueue(self, val):
            self.queue_ds.append(val)
            if self.Front == -1:
                self.Front += 1
                self.Rear += 1
            else:
                self.Rear += 1
    
        def dequeue(self):
            if self.empty() is True:
                print("Queue is empty")
                return
            else:
                temp = self.queue_ds.pop(self.Front)
                self.Rear -= 1
                if self.empty() is True:
                    self.Front = -1
                    self.Rear = -1
                return temp
    
        def front(self):
            if self.empty() is True:
                print("Queue empty")
            return self.Front
    
        def rear(self):
            if self.empty() is True:
                print("Queue empty")
            return self.Rear
    
        def empty(self):
            if len(self.queue_ds) == 0:
                return True
            else:
                return False
    
        def display(self):
            if self.empty() is True:
                print("Queue empty")
                return
            print("The Queue")
            if self.Front == self.Rear:
                print(self.queue_ds[self.Front], "<== Front <== Rear")
                return
            print(self.queue_ds[self.Front], "<== FRONT")
            i = self.Front + 1
            while i < self.Rear:
                print(self.queue_ds[i])
                i += 1
            print(self.queue_ds[self.Rear], "<== REAR")
            print("The Queue Ends")
    
    
    a = queue()
    a.enqueue(1)
    a.enqueue(2)
    a.display()
    print(a.dequeue())
    a.display()
    print(a.front())
    a.dequeue()
    print(a.rear())

    the output of the compiled program is

    The Queue
    1 <== FRONT
    2 <== REAR
    The Queue Ends
    1
    The Queue
    2 <== Front <== Rear
    0
    Queue empty
    -1

Implementing Queue in Python using Linked Lists

Queues can be implemented using Python linked lists too. The queue methods and variables, in general, remain the same. In this case, Python classes are used to implement the data structure.

The two main classes used to implement Queue in Python are:

  • Node class - it represents a single data element in the queue and contains a link field that is used to connect via address to the next data element
  • queue class - it represents the queue in question itself and contains the front and the rear variables which hold the front and rear elements of the queue

Steps to define Queue in Python using Linked Lists

  1. Define the Node class which contains a value field that holds the value for that data element, and a link field that holds the next Node of the linked list
    class Node:
        def __init__(self, val):
            self.value = val
            self.next = None​
  2. Define and initialize the queue class which contains the front and rear variables that hold the respective data elements of the queue
    class queue:
        def __init__(self):
            self.Front = None
            self.Rear = None​
  3. Define the enqueue() method to add data elements to the queue, and thereby update the respective front and rear variables
        def enqueue(self, val):
            if self.empty() is True:
                self.Front = Node(val)
                self.Rear = self.Front
                return
            self.Rear.next = Node(val)
            self.Rear = self.Rear.next​
  4. Define the dequeue() method to extract the earliest added data element from the queue, and thus update the relevant front and rear variables
        def dequeue(self):
            if self.empty() is True:
                print("Queue is empty")
                return -1
            elif self.Front == self.Rear:
                temp = self.Front.value
                self.Front = None
                self.Rear = None
                return temp
            else:
                temp = self.Front.value
                self.Front = self.Front.next
                return temp​
  5. Define the front() method, that is used to return the front variable of the queue
        def front(self):
            if self.empty() is True:
                print("Queue empty")
                return -1
            else:
                return self.Front.value​
  6. Define the rear() method, that is used to return the rear variable of the queue
        def rear(self):
            if self.empty() is True:
                print("Queue empty")
                return -1
            else:
                return self.Rear.value​
  7. Define the empty() method that is used to check whether the queue is empty or not
        def empty(self):
            if self.Rear is None:
                return True
            else:
                return False​
  8. Define the display() method that is used to display the Queue in Python using Linked Lists in a user-comprehensible way
        def display(self):
            print("The Queue")
            if self.empty() is True:
                print("Queue empty")
            elif self.Front == self.Rear:
                print(self.Front.value, "<== FRONT <== REAR")
            else:
                i = self.Front.next
                print(self.Front.value, "<== FRONT")
                while i is not self.Rear:
                    print(i.value)
                    i = i.next
                print(self.Rear.value, "<== REAR")
            print("Queue Over")​
  9. Finally, after assembling, creating an instance, implementing the associated methods, and ultimately compiling the program
    class Node:
        def __init__(self, val):
            self.value = val
            self.next = None
    
    class queue:
        def __init__(self):
            self.Front = None
            self.Rear = None
    
        def enqueue(self, val):
            if self.empty() is True:
                self.Front = Node(val)
                self.Rear = self.Front
                return
            self.Rear.next = Node(val)
            self.Rear = self.Rear.next
    
        def dequeue(self):
            if self.empty() is True:
                print("Queue is empty")
                return -1
            elif self.Front == self.Rear:
                temp = self.Front.value
                self.Front = None
                self.Rear = None
                return temp
            else:
                temp = self.Front.value
                self.Front = self.Front.next
                return temp
    
        def front(self):
            if self.empty() is True:
                print("Queue empty")
                return -1
            else:
                return self.Front.value
    
        def rear(self):
            if self.empty() is True:
                print("Queue empty")
                return -1
            else:
                return self.Rear.value
    
        def empty(self):
            if self.Rear is None:
                return True
            else:
                return False
    
        def display(self):
            print("The Queue")
            if self.empty() is True:
                print("Queue empty")
            elif self.Front == self.Rear:
                print(self.Front.value, "<== FRONT <== REAR")
            else:
                i = self.Front.next
                print(self.Front.value, "<== FRONT")
                while i is not self.Rear:
                    print(i.value)
                    i = i.next
                print(self.Rear.value, "<== REAR")
            print("Queue Over")
    
    a = queue()
    a.enqueue(1)
    a.enqueue(2)
    a.display()
    print(a.dequeue())
    a.display()
    print(a.front())
    a.dequeue()
    print(a.rear())
    a.display()​

    the output of the Queue in Python implemented using Linked Lists is

    The Queue
    1 <== FRONT
    2 <== REAR
    Queue Over
    1
    The Queue
    2 <== FRONT <== REAR
    Queue Over
    2
    Queue empty
    -1
    The Queue
    Queue empty
    Queue Over

Advantages and Disadvantages of Queues in Python

Advantages
  • Flexibility
  • Easy to use
  • Fast operation
  • Can handle multiple data types
Disadvantages
  • Searching is cumbersome
  • Data elements cannot be added at an intermediate level

Applications of Queues in Python

  1. Program service request scheduling
  2. Hardware service request scheduling
  3. Efficient interrupt handling
  4. Disc scheduling
  5. I/O or Input Buffer pipes
0 results
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions