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 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 :
insertFront( x ) : inserts the element ' x ' at the front end of the queue.
insertRear( x ) : inserts the element ' x ' at the rear end of the queue.
size( ) : returns the size of the queue.
deleteFront( ) : deletes the front element of the queue.
deleteRear( ) : deletes the rear element of the queue.
frontElement( ) : returns the front element of the queue.
rearElement( ) : returns the rear element of the queue.
isEmpty( ) : checks whether the queue is empty or not.
isFull( ) : checks whether the queue is full or not.
Output:No space in front
size of the queue is 5
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 emptyTime complexity
The time complexity of all the above operations is O(1).Applications of Deque Data Structure
In undo operations on software.
To store history in browsers.
For implementing both stacks and queues
Very famous question on deque
Happy Coding 😊
By Programmers Army
Contributed by: Ravi Teja Chidurala