Dequeue in Data structure
In Data Structure Dequeue is known as a Double Ended Queue in which we can insert and delete the data from both ends means we can perform operations enqueue and dequeue from both 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 an array or list in the Python programming language.
Program to implement dequeue using array in Python.
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 implement of dequeue using the doubly linked list in the data structure. we stored the front and last node’s references in 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 the articles given below.
Insertion in the doubly linked list
Deletion in the doubly linked list
Program to implement dequeue using a doubly linked list in Python.
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 a doubly linked list in Python.
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()
