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()