Deque
A deque referred as “Double-Ended Queue”, is a linear collection of data items same like queue data structure. deque has two ends, front end and rear end, deque is the unrestricted type of data structure, data item can be added into it either front or rear and also data item can be removed or deleted from it either front or rear. Thus, it doesn’t follow first in first out rule. So we can say deque is the hybrid linear structure who provides the functionality of queue and stack in a single data structure.
Language Support:-
Operations on Deque:-
returns the data item and it will be modified.
1. By Circular Array
Output:-
2. By Doubly Linked list
Output:-
We can use deque directly in python which will import deque from collections module. For practice purposes, we do possible implementation below of a deque using python list.
In add_front we use the insert() method with position 0. So data item add 0th place of the list and if we want add data item in rear so we need to use append() method so data item can be added to the end of the list. Likely for removing data item from the queue we use pop() method with 0th position for remove data item from the front of list and simple use pop() method for remove data item from the end of the list.
The time complexity of deque operations like add_front(),add_Rear(),delete_front(),delete_Rear() is contant which is o(1) by Circular Array or Doubly Linked List.
In the above example, we have implemented various operations on deque assume as d and currently empty in the table given below:
An interesting problem that can be solved by deque data structure easily is palindrome problem. A Palindrome is a string if we read this string from both ends of it then it would be same like madam, radar etc. we will try to make solution so we can check the string whether it is a palindrome or not.
The solution of this problem we store the characters of string in deque from left to right like ordinary queue so front end will hold the first character of string and rear end will hold the last character of string after that we will remove the characters from front as well as rear end simultaneously and check them if they match to each other continuously then string is palindrome otherwise not.