Dequeue | Data structures and algorithms

Dequeue in data structures it is known as a Double Ended Queue in which we can insert and delete the data from both the ends means we can perform operations enqueue and dequeue from both the ends.


we can implement dequeue using an array, linked list, doubly linked list and circular linked list.

first, let's see how we can implement dequeue using array or list in the python programming language.

Program to implement dequeue using array in the python programming language.

class EmptyQueueError(Exception):
    pass

class Deque:

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

    def is_empty(self):
        return self.items == []

    def size(self):
        return len(self.items)

    def insert_front(self, item):
        self.items.insert(0, item)

    def insert_rear(self, item):
        self.items.append(item)

    def delete_front(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is Empty")
        return self.items.pop(0)

    def delete_rear(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is Empty")
        return self.items.pop()

    def first(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is Empty")
        return self.items[0]

    def last(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is Empty")
        return self.items[-1]

    def display(self):
        print(self.items)

#########################################################################
if __name__ == '__main__':
    qu = Deque()

    while True:
        print("1. Insert at the front end")
        print("2. Insert at the rear end")
        print("3. Delete from front end")
        print("4. Delete from rear end")
        print("5. Display first element")
        print("6. Display last element")
        print("7. Display")
        print("8. Size")
        print("9. Quit")

        choice = int(input("Enter your choice : "))

        if choice == 1:
            x = int(input("Enter the element : "))
            qu.insert_front(x)
        elif choice == 2:
             x = int(input("Enter the element : "))
             qu.insert_rear(x)
        elif choice == 3:
            x = qu.delete_front()
            print("Element deleted from front end is ",x)
        elif choice == 4:
            x = qu.delete_rear()
            print("Element deleted from rear end is ",x)
        elif choice == 5:
            print("First element is ",qu.first())
        elif choice == 6:
            print("Last element is ", qu.last())
        elif choice == 7:
            qu.display()
        elif choice == 8:
            print("Size of queue ", qu.size())
        elif choice == 9:
            break        else:
            print("wrong choice ")
        print()

we can also implement dequeue using a doubly-linked list.


to easily implementation of dequeue using the doubly linked list we stored the front and last node's references into the front and rear variables. so we can easily enqueue and dequeue from both ends.

we already know how to insert and delete a node from the first and last position of a circular linked list. if you don't know then refer to these articles given below.

Insertion in the doubly linked list.
Deletion in the doubly linked list.

Program to implement dequeue using doubly linked list in a python programming language.

class EmptyQueueError(Exception):
    pass
class Node:

    def __init__(self, value):
        self.info = value
        self.prev = None        self.next = None
class Deque:

    def __init__(self):
        self.front = None        self.rear = None
    def is_empty(self):
        return self.front == None
    def size(self):
        count = 0        p = self.front
        while p is not None:
            count +=1            p = p.next
        return count

    def insert_front(self, item):
        temp = Node(item)
        if self.is_empty():
            self.front = self.rear = temp
        else:
            temp.next = self.front
            self.front.prev = temp
            self.front = temp

    def insert_rear(self, item):
        temp = Node(item)
        if self.is_empty():
            self.front = self.rear = temp
        else:
            self.rear.next = temp
            temp.prev = self.rear

        self.rear = temp


    def delete_front(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is empty")

        x = self.front.info
        if self.front.next is None:
            self.front = self.rear = None        else:
            self.front = self.front.next
            self.front.prev = None        return x

    def delete_rear(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is empty")

        x = self.rear.info
        if self.front.next is None:
            self.front = self.rear = None        else:
            self.rear = self.rear.prev
            self.rear.next = None        return x

    def first(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is empty")

        return self.front.info

    def last(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is empty")
        return self.rear.info

    def display(self):
        if self.front is None:
            print("List is empty")
            return        print("List is : ")
        p = self.front
        while p is not None:
            print(p.info, " ", end='')
            p = p.next
        print()

################################
if __name__ == '__main__':
    qu = Deque()

    while True:
        print("1. Insert at the front end")
        print("2. Insert at the rear end")
        print("3. Delete from front end")
        print("4. Delete from rear end")
        print("5. Display first element")
        print("6. Display last element")
        print("7. Display")
        print("8. Size")
        print("9 Quit")

        choice = int(input("Enter your choice : "))

        if choice == 1:
            x = int(input("Enter the element : "))
            qu.insert_front(x)
        elif choice == 2:
            x = int(input("Enter the element : "))
            qu.insert_rear(x)
        elif choice == 3:
            x = qu.delete_rear()
            print("Element deleted from front end is ", x)
        elif choice == 4:
            x = qu.delete_rear()
            print("Element deleted from rear end is ", x)
        elif choice == 5:
            print("Last element is ", qu.first())
        elif choice == 6:
            print("Last element is ", qu.last())
        elif choice == 7:
            qu.display()
        elif choice == 8:
            print("size of queue ", qu.size())
        elif choice == 9:
            break        else:
            print("Wrong choice ")
        print()

Program to implement dequeue using doubly linked list in a python programming language. 

class EmptyQueueError(Exception):
    pass
class Deque:

    def __init__(self, default_size=10):
        self.items = [None] * default_size
        self.front = 0        self.count = 0
    def is_empty(self):
        return self.count == 0
    def size(self):
        return self.count

    def insert_front(self, item):
        if self.count == len(self.items):
            self.resize(2*len(self.items))

        i = (self.front + self.count) % len(self.items)
        self.items[i] = item
        self.count += 1
    def insert_rear(self, item):
        if self.count == len(self.items):
            self.resize( 2 * len(self.items))

        i = (self.front + self.count) % len(self.items)
        self.items[i] = item
        self.count +=1
    def delete_front(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is empty")

        x = self.items[self.front]
        self.items[self.front] = None        self.front = (self.front + 1) % len(self.items)
        self.count -= 1        return x

    def delete_rear(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is empty")
        rear = (self.front + self.count - 1) % len(self.items)
        x = self.items[rear]
        self.items[rear] = None        self.count -=1        return x

    def first(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is empty")
        return self.items[self.front]

    def last(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is empty")
        rear = (self.front + self.count - 1) % len(self.items)
        return self.items[rear]

    def display(self):
        print(self.items)

    def resize(self,newsize):
        old_list = self.items
        self.items = [None] * newsize
        i = self.front
        for j in range(self.count):
            self.items[j] = old_list[i]
            i = (1+i)%len(old_list)
        self.front = 0

######################################################################3
if __name__ == '__main__':
    qu = Deque(6)

    while True:
        print("1. Insert at the front end")
        print("2. Insert at the rear end")
        print("3. Delete from front end")
        print("4. Delete from rear end")
        print("5. Display first element")
        print("6. Display last element")
        print("7. Display")
        print("8. Size")
        print("9. Quit")

        choice = int(input("Enter your choice : "))

        if choice == 1:
            x = int(input("Enter the element : "))
            qu.insert_front(x)
        elif choice == 2:
            x = int(input("Enter the element : "))
            qu.insert_rear(x)
        elif choice == 3:
            x = qu.delete_front()
            print("Element deleted from front end is ", x)
        elif choice == 4:
            x = qu.delete_rear()
            print("Element deleted from rear end is ", x)
        elif choice == 5:
            print("First element is ", qu.first())
        elif choice == 6:
            print("Last element is ", qu.last())
        elif choice == 7:
            qu.display()
        elif choice == 8:
            print("Size of queue ", qu.size())
        elif choice == 9:
            break        else:
            print("Wrong choice")
        print()

Also, read these posts

• What are Data Structures and algorithms
• Algorithm design and analysis
• Classification of algorithms
• How to calculate the running time of an algorithm.
• Worst Average and Best-case analysis of the algorithm.
• Big o notation
• Big o notation examples
• Linked List in Data Structures
• Traversing in Linked list
• Operations on the linked list
• Insertion in the linked list
• Deletion in a linked list
• Reversing a linked list
• Sorting a linked list
• Find and remove the loop in the linked list
• Doubly linked list
• Insertion in the doubly linked list
• Deletion in the doubly linked list
• Reversing a doubly linked list
• Circular linked list
• Insertion in the circular linked list
• Deletion in the circular linked list
• Merge two linked list
• Header linked list
• Sorted linked list
• Stack in data structures
• Queue in data structures
• Circular queue
• Priority queue
• Polish notation
• Tree in the data structure
• Binary tree
• Array representation of the binary tree
• linked representation of a binary tree
• Traversing in the binary tree
• Inorder traversal in the binary tree
• Preorder traversal in the binary tree
• Postorder traversal in the binary tree
• Level order traversal in the binary tree
• Binary search tree
• Insertion in the binary search tree
• Deletion in the binary search tree
• Heap in data structures