# 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. 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

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