DOUBLELY ENDED QUEUE (DEQUE)


A double-ended queue is a queue where insertion and deletion can be performed at both ends.

Double-ended queue implements FIFO( First In First Out), LILO( Last In Last Out), FILO( First In Last Out), LIFO( Last In First Out).

  • An input restricted deque is one where deletion can be performed on both ends, but insertion can be made at one end only.

  • An output restricted deque is one where insertion can be performed on both ends, but deletion can be made at one end only.

Array Implemention of dequeue

Fundamental operations :

  1. insertFront( x ) : inserts the element ' x ' at the front end of the queue.

  2. insertRear( x ) : inserts the element ' x ' at the rear end of the queue.

  3. size( ) : returns the size of the queue.

  4. deleteFront( ) : deletes the front element of the queue.

  5. deleteRear( ) : deletes the rear element of the queue.

  6. frontElement( ) : returns the front element of the queue.

  7. rearElement( ) : returns the rear element of the queue.

  8. isEmpty( ) : checks whether the queue is empty or not.

  9. isFull( ) : checks whether the queue is full or not.

Code for array implemention of dequeue:

Output:No space in front
size of the queue is 5
overflow
No space in rear
front element 15
rear element 30

Explanation of code

1.Initially the queue is empty so front =-1 and rear=-1

2. insertFront(5) so, 5 is inserted in the deque and front =0 and rear=0 now

3.insertRear(25) now deque has 5, 25 and front=0 and rear =1

4.insertFront(30) since front ==0 no room for front insertion

5.insertRear(30) insertRear(25) insertRear(18) now deque becomes 5,25,30,25,18 front=0 and rear=4

6.insertFront(43) since size=rear-front+1=5 queue is full ->overflow condition

7.deleteFront() now dequeue has __ 25 30 25 18 front=1 rear=4

8.insertRear(34) since rear ==4 (MAX-1) No room for rear insertion

9. deleteFront() now deque is __ __ 30 25 18 front =2 and rear=4

10. insertFront(15) now deque is __ 15 30 25 18 front=1 rear=4

11.deleteRear() deleteRear() now deque has __ 15 30 __ __ front =1 and rear =2

12. deleteFront()deleteFront() now deque becomes empty

Time complexity

The time complexity of all the above operations is O(1).

Applications of Deque Data Structure

  1. In undo operations on software.

  2. To store history in browsers.

  3. For implementing both stacks and queues

Very famous question on deque

https://www.hackerearth.com/practice/data-structures/arrays/1-d/practice-problems/algorithm/maximum-of-k-size-subarrays-deque/


Happy Coding 😊

By Programmers Army

Contributed by: Ravi Teja Chidurala