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.

Deque in Data Structure

Sub types of Deque

  • An input-restricted deque is the queue where deletion of data item can be done from both ends, but insertion can be done at one end only.
  • An output-restricted deque is the queue where insertion can be done at both end, but deletion can be done from one end only.

Language Support:-

  • In C++ provides implemention of deque as std::deque .
    • In java provides deque interface in collections module.
    • In python we can import deque from collections module.

Operations on Deque:-

  • Deque() creates a new deque that is empty. It doesn’t take any parameters and it returns an empty deque.
  • add_Front(data) adds a new data item in to the front of deque. We give data item as parameter and it returns nothing.
  • delete_Front() removes the data item from the front of the deque, returns the data item and it will be modified.
  • add_Rear(data) adds a new data item in to the end of deque, needs to take data as parameter and returns nothing.
  • delete_Rear() removes the data item from the end of deque,

returns the data item and it will be modified.

  • is_Empty() checks to see if the deque is empty and return boolean value.
  • Size() returns the number of items in the deque and return an integer.

Implementation of Deque in C langauge

1. By Circular Array

Output:-

Deque in Data Structure

2. By Doubly Linked list

Output:-

Deque in Data Structure
Deque in Data Structure

Deque implementation in python:-

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.

Time Complexity of Deque Operations

 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:

  Deque Operation              Deque Contents                            Retrun Value
    d.is_Empty                                                                     []                                True
    d.add_front(“cat”)                   [“cat”]               
    d.add_Rear(2)                   [“cat”, 2] 
    d.delete_Front()                   [2]                                “cat”
    d.add_Rear(“dog”)                   [2, ”dog”] 
    d.add_Front(“tiger”)                   [“tiger”, 2 ,”dog”] 
    d.size()                   [“tiger” ,2, ”dog”]                                    3
    d.is_Empty()                   [“tiger” ,2, ”dog”]                                 False
    d.delete_Rear()                   [“tiger”, 2]                                 “dog”
    d.add_Front(10)                   [10, ”tiger”, 2]      
    d.delete_Front()                   [ ”tiger”, 2]                                        10
    d.size()                   [“tiger”, 2]                                    2

Applications of Deque

  • In the internet browser’s history we use deque for recently visited URL’s as to the front of the queue.
  • In computer application undo operation uses deque for storing application’s list.
  • As deque supports both stack and queue operation, so it can be used as both.

Standard problem on Deque

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.

Pin It on Pinterest

Share This