Dequeue in Python

Doubly ended Queues or Deques are derived data structures that are similar to queues but can be enqueued or dequeued from either of the ends. Dequeues in Python can be implemented using both Python lists as well as Linked Lists.

Dequeues have a number of applications including the A-steal algorithm which implements multiprocessor task scheduling.
dequeue

Characteristics of Dequeues in Python
  • Dynamic data structure
  • No fixed length
  • Elements can be added and deleted from both ends

Manipulating a Dequeue in Python

Methods
  1. addLeft() - Adds an element to the left-hand side of the dequeue
  2. addRight() - Adds an element to the right-hand side of the dequeue
  3. delLeft() - Deletes an element to the left-hand side of the dequeue
  4. delRight() - Deletes an element to the right-hand side of the dequeue
  5. peekLeft() - Returns the left-most element of the dequeue
  6. peekRight() - Returns the right-most element of the dequeue
  7. empty() - Returns whether the dequeue is empty or not
  8. display() - Displays the dequeue in a user-comprehendible format
Variables

There are two variables; left and right; each of which holds one each end of the dequeue.

Implementing a dequeue using Python Lists

A Dequeue can be implemented using Python lists by following these steps:

  1. Defining the Dequeue class
    class Dequeue:​
  2. Initializing the Python List along with the left and right variables
        def __init__(self):
            self.queue_ds = []
            self.left = -1
            self.right = -1​
  3. Defining the addLeft() method which adds an element to the left-hand side of the Dequeue
        def addLeft(self, val):
            self.queue_ds.insert(0, val)
            if self.left == -1:
                self.left += 1
                self.right += 1
            else:
                self.right += 1​
  4. Defining the addRight() method which adds an element to the right-hand side of the Dequeue in Python
        def addRight(self, val):
            self.queue_ds.append(val)
            if self.left == -1:
                self.left += 1
                self.right += 1
            else:
                self.right += 1​
  5. Defining the delLeft() method which deletes the left-most element of the Dequeue
        def delLeft(self):
            if self.empty() is True:
                print("Queue is empty")
            else:
                temp = self.queue_ds.pop(self.left)
                self.right -= 1
                if self.empty() is True:
                    self.left = -1
                    self.right = -1
                return temp​
  6. Defining the delRight() method which deletes the right-most element of the Dequeue in Python
        def delRight(self):
            if self.empty() is True:
                print("Queue is empty")
            else:
                temp = self.queue_ds.pop(self.right)
                self.right -= 1
                if self.empty() is True:
                    self.left = -1
                    self.right = -1
                return temp​
  7. Defining the peekLeft() method which returns the left-most element of the Dequeue
        def peekLeft(self):
            if self.empty() is True:
                print("Queue empty")
            return self.queue_ds[self.left]​
  8. Defining the peekRight() method which returns the right-most element of the Dequeue
        def peekRight(self):
            if self.empty() is True:
                print("Queue empty")
            return self.queue_ds[self.right]​
  9. Defining the empty() method which returns whether or not the Dequeue in Python is empty
        def empty(self):
            if len(self.queue_ds) == 0:
                return True
            else:
                return False​
  10. Defining the display() method which presents the Dequeue in a user-comprehendible manner
        def display(self):
            if self.empty() is True:
                print("Queue empty")
                return
            print("The Queue")
            if self.left == self.right:
                print(self.queue_ds[self.left], "<== Front <== Rear")
                return
            print(self.queue_ds[self.left], "<== LEFT")
            i = self.left + 1
            while i < self.right:
                print(self.queue_ds[i])
                i += 1
            print(self.queue_ds[self.right], "<== RIGHT")
            print("The Queue Ends")​
  11. After assembling the entire program, creating an instance of the Dequeue class, implementing its methods, and compiling it
    class Dequeue:
        def __init__(self):
            self.queue_ds = []
            self.left = -1
            self.right = -1
    
        def addLeft(self, val):
            self.queue_ds.insert(0, val)
            if self.left == -1:
                self.left += 1
                self.right += 1
            else:
                self.right += 1
    
        def addRight(self, val):
            self.queue_ds.append(val)
            if self.left == -1:
                self.left += 1
                self.right += 1
            else:
                self.right += 1
    
        def delLeft(self):
            if self.empty() is True:
                print("Queue is empty")
            else:
                temp = self.queue_ds.pop(self.left)
                self.right -= 1
                if self.empty() is True:
                    self.left = -1
                    self.right = -1
                return temp
    
        def delRight(self):
            if self.empty() is True:
                print("Queue is empty")
            else:
                temp = self.queue_ds.pop(self.right)
                self.right -= 1
                if self.empty() is True:
                    self.left = -1
                    self.right = -1
                return temp
    
        def peekLeft(self):
            if self.empty() is True:
                print("Queue empty")
            return self.queue_ds[self.left]
    
        def peekRight(self):
            if self.empty() is True:
                print("Queue empty")
            return self.queue_ds[self.right]
    
        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.left == self.right:
                print(self.queue_ds[self.left], "<== Front <== Rear")
                return
            print(self.queue_ds[self.left], "<== LEFT")
            i = self.left + 1
            while i < self.right:
                print(self.queue_ds[i])
                i += 1
            print(self.queue_ds[self.right], "<== RIGHT")
            print("The Queue Ends")
    
    
    a = Dequeue()
    a.delLeft()
    a.addLeft(1)
    a.addRight(2)
    a.addLeft(-1)
    a.addRight(3)
    a.display()
    print(a.delLeft())
    a.display()
    a.delRight()
    a.display()
    print(a.peekLeft())
    print(a.peekRight())​

    the output of the program is

    Queue is empty
    The Queue
    -1 <== LEFT
    1
    2
    3 <== RIGHT
    The Queue Ends
    -1
    The Queue
    1 <== LEFT
    2
    3 <== RIGHT
    The Queue Ends
    The Queue
    1 <== LEFT
    2 <== RIGHT
    The Queue Ends
    1
    2

Implementing a dequeue using Python Linked Lists

Dequeues can also be implemented using Linked Lists in Python.

The following steps will show how Dequeue in Python can be implemented using Linked Lists:

  1. Defining the Node class which represents each data element in the Dequeue Linked List. The Left and Right variables hold the links and the value field holds the data
    class Node:
        def __init__(self, val):
            self.value = val
            self.Left = None
            self.Right = None​
  2. Define the Dequeue class
    class Dequeue:
  3. Initialize the Dequeue variables; left and right which holds the end data element
        def __init__(self):
            self.left = None
            self.right = None
  4. Define the addLeft() method that adds an element to the left of the Dequeue
        def addLeft(self, val):
            if self.empty() is True:
                self.left = Node(val)
                self.right = self.left
            else:
                self.left.Left = Node(val)
                self.left.Left.Right = self.left
                self.left = self.left.Left
  5. Define the addRight() method that adds an element to the right of the Dequeue
        def addRight(self, val):
            if self.empty() is True:
                self.left = Node(val)
                self.right = self.left
            else:
                self.right.Right = Node(val)
                self.right.Right.Left = self.right
                self.right = self.right.Right
  6. Define the delLeft() method which removes and returns the leftmost element from the Dequeue
        def delLeft(self):
            if self.empty() is True:
                print("Dequeue is empty")
            elif self.left == self.right:
                temp = self.left.value
                self.left = None
                self.right = None
                return temp
            else:
                temp = self.left.value
                self.left = self.left.Right
                self.left.Left = None
                return temp​
  7. Define the delRight() method removes and returns the right-most element from the Dequeue
        def delRight(self):
            if self.empty() is True:
                print("Dequeue is empty")
            elif self.left == self.right:
                temp = self.left.value
                self.left = None
                self.right = None
                return temp
            else:
                temp = self.right.value
                self.right = self.right.Left
                self.right.Right = None
                return temp​
  8. Define the peekLeft() method which returns the leftmost element of the Dequeue
        def peekLeft(self):
            if self.empty() is True:
                print("Dequeue empty")
            else:
                return self.left.value​
  9. Define the peekRight() method which returns the rightmost element of the Dequeue
        def peekRight(self):
            if self.empty() is True:
                print("Dequeue empty")
            else:
                return self.right.value​
  10. Define the empty() function which checks whether the Dequeue is empty or not
        def empty(self):
            if self.left is None:
                return True
            else:
                return False​
  11. Define the display() function which displays the Dequeue in a user-comprehendible format
        def display(self):
            print("Dequeue show")
            if self.empty() is True:
                print("Dequeue is empty")
            elif self.left == self.right:
                print(self.left.value, " <== LEFT RIGHT")
            else:
                print(self.left.value, " <== LEFT")
                i = self.left.Right
                while i is not self.right:
                    print(i.value)
                    i = i.Right
                print(self.right.value, " <== RIGHT")
            print("Dequeue ends")​
  12. After all the sections are assembled and an instance of the Dequeue class is created, and methods used to manipulate the Dequeue called, and compiled
    class Node:
        def __init__(self, val):
            self.value = val
            self.Left = None
            self.Right = None
    
    class Dequeue:
        def __init__(self):
            self.left = None
            self.right = None
    
        def addLeft(self, val):
            if self.empty() is True:
                self.left = Node(val)
                self.right = self.left
            else:
                self.left.Left = Node(val)
                self.left.Left.Right = self.left
                self.left = self.left.Left
    
        def addRight(self, val):
            if self.empty() is True:
                self.left = Node(val)
                self.right = self.left
            else:
                self.right.Right = Node(val)
                self.right.Right.Left = self.right
                self.right = self.right.Right
    
        def delLeft(self):
            if self.empty() is True:
                print("Dequeue is empty")
            elif self.left == self.right:
                temp = self.left.value
                self.left = None
                self.right = None
                return temp
            else:
                temp = self.left.value
                self.left = self.left.Right
                self.left.Left = None
                return temp
    
        def delRight(self):
            if self.empty() is True:
                print("Dequeue is empty")
            elif self.left == self.right:
                temp = self.left.value
                self.left = None
                self.right = None
                return temp
            else:
                temp = self.right.value
                self.right = self.right.Left
                self.right.Right = None
                return temp
    
        def peekLeft(self):
            if self.empty() is True:
                print("Dequeue empty")
            else:
                return self.left.value
    
        def peekRight(self):
            if self.empty() is True:
                print("Dequeue empty")
            else:
                return self.right.value
    
        def empty(self):
            if self.left is None:
                return True
            else:
                return False
    
        def display(self):
            print("Dequeue show")
            if self.empty() is True:
                print("Dequeue is empty")
            elif self.left == self.right:
                print(self.left.value, " <== LEFT RIGHT")
            else:
                print(self.left.value, " <== LEFT")
                i = self.left.Right
                while i is not self.right:
                    print(i.value)
                    i = i.Right
                print(self.right.value, " <== RIGHT")
            print("Dequeue ends")
    
    a = Dequeue()
    a.delLeft()
    a.addLeft(1)
    a.addRight(2)
    a.addLeft(-1)
    a.addRight(3)
    a.display()
    print(a.delLeft())
    a.display()
    a.delRight()
    a.display()
    print(a.peekLeft())
    print(a.peekRight())​

    the output of the code is as follows

    Dequeue is empty
    Dequeue show
    -1  <== LEFT
    1
    2
    3  <== RIGHT
    Dequeue ends
    -1
    Dequeue show
    1  <== LEFT
    2
    3  <== RIGHT
    Dequeue ends
    Dequeue show
    1  <== LEFT
    2  <== RIGHT
    Dequeue ends
    1
    2

Advantages and Disadvantages of Dequeue

Advantages
  • Dequeues are queues that can be increased and decreased from both ends
  • Easy implementation
Disadvantages
  • Takes up memory overhead

Applications of Dequeue

  1. Dequeues can be used to implement both stacks and queue data structures
  2. Dequeues allow both clockwise and anticlockwise rotation which is used in many applications
  3. The A-steal algorithm can be implemented using the Dequeue data structure, which used in multiprocessor task scheduling
0 results
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions