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

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
- 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
0 Comments