Implement Deque

Easy
0/40
Average time to solve is 15m
profile
Contributed by
148 upvotes
Asked in companies
AdobeGoldman SachsGeeksforGeeks

Problem statement

Design a data structure to implement deque of size ‘N’. It should support the following operations:

pushFront(X): Inserts an element X in the front of the deque. Returns true if the element is inserted, otherwise false.

pushRear(X): Inserts an element X in the back of the deque. Returns true if the element is inserted, otherwise false.

popFront(): Pops an element from the front of the deque. Returns -1 if the deque is empty, otherwise returns the popped element.

popRear(): Pops an element from the back of the deque. Returns -1 if the deque is empty, otherwise returns the popped element.

getFront(): Returns the first element of the deque. If the deque is empty, it returns -1.

getRear(): Returns the last element of the deque. If the deque is empty, it returns -1.

isEmpty(): Returns true if the deque is empty, otherwise false.

isFull(): Returns true if the deque is full, otherwise false.

Following types of queries denote these operations:

Type 1: for pushFront(X) operation.
Type 2: for pushRear(X) operation.
Type 3: for popFront() operation.
Type 4: for popRear() operation.
Type 5: for getFront() operation.
Type 6: for getRear() operation.
Type 7: for isEmpty() operation.
Type 8: for isFull() operation.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains two space-separated integers ‘N’ and ‘Q’ denoting the size of the deque and the number of queries to be performed, respectively. 

The next ‘Q’ lines specify the type of operation/query to be performed on the data structure.

Each query contains an integer ‘P’ denoting the type of query.

For the query of type 1 and 2, the integer ‘P’ is followed by a single integer ‘X’ denoting the element on which operation is to be performed.

For the queries of type 3 to 8, a single integer ‘P’ is given, denoting the type of query.
Output format: 
For each query, print the output returned after performing the corresponding operation on the data structure.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given functions.
Constraints: 
1 <= N <= 1000
1 <= Q <= 10^5 
1 <= P <= 8
1 <= X <= 10^5

Time Limit: 1 sec

Where ‘N’ represents the size of the deque, ‘Q’ represents the number of queries, ‘P’ represents the type of operation and ‘X’ represents the element.
Sample Input 1:
5 7
7
1 10
1 20
2 30
5
4
4
Sample Output 1:
True 
True 
True
True
20
30
10
Explanation 1:
For the given input, we have the number of queries, Q = 7.
Operations performed on the deque are as follows:

isEmpty(): Deque is initially empty. So, this returns true.
pushFront(10): Insert the element ‘10’ in the front of the deque. This returns true.
pushFront(20): Insert the element ‘20’ in the front of the deque. This returns true.
pushRear(30): Insert the element ‘30’ in the back of the deque. This returns true.
getFront(): Returns the front element of the deque i.e. 20
popRear(): Pop an element from the back of the deque. This returns 30.
popRear(): Pop an element from the back of the deque. This returns 10.

The following image shows the snapshots of the deque after each operation:

Deque Snapshot

Sample Input 2:
2 5
1 15
2 25
1 20
8
6
Sample Output 2:
True
True
False
True
25
Hint

Try using a circular array to implement the deque.

Approaches (1)
Approach 1
  • A deque (double-ended queue) is a generalized form queue, which supports insert and delete operation from both ends of the queue.
  • We can easily implement deque with the help of a circular array.
  • We can think of a circular array as an array in which 0th position occurs after (N - 1)th position and/or (N - 1)th position occurs before 0th position, resulting in the two ends of the array wrap up to make a circle.
  • As the insertion and deletion can occur at both ends in a deque, we maintain two pointers - front and rear, to keep track of the first and the last filled positions in the array.

 

Algorithm:

 

  • Create an array of size ‘N’. This will be used to implement the deque.
  • Initialize two pointers, front and rear, to -1.
  • PushFront(X) Operation:
    • If the deque is full, return false.
    • Otherwise, if the deque is empty, initialize front and rear to 0.
    • Otherwise, if the deque is NOT empty, we decrement front by 1 (if the front is equal to 0, it becomes N-1 as the array is circular).
    • Insert the element at the front of the queue, i.e. at position front.
    • Return true.
  • PushRear(X) Operation:
    • If the deque is full, return false.
    • Otherwise, if the deque is empty, initialize front and rear to 0.
    • Otherwise, if the deque is NOT empty, we increment rear by 1 (if the rear is equal to N-1, it becomes 0 as the array is circular).
    • Insert the element at the back of the queue, i.e. at position rear.
    • Return true.
  • PopFront Operation:
    • If the deque is empty, return -1.
    • Get the first element of the deque and store it in a variable say item.
    • If front = rear, then deque has only one element and on removing it deque becomes empty. So, set front and rear to -1.
    • Otherwise, delete the element from the front by incrementing the front by 1 (if the front is equal to N-1, it becomes 0 as the array is circular).
    • Return item.
  • PopRear Operation:
    • If the deque is empty, return -1.
    • Get the last element and store it in a variable say item.
    • If front = rear, then deque has only one element and on removing it deque becomes empty. So, set front and rear to -1.
    • Otherwise, delete the element from the back by decrementing rear by 1 (if the rear is equal to 0, it becomes N-1 as the array is circular).
    • Return item.
  • GetFront Operation:
    • If the deque is empty, return -1.
    • Otherwise return the first element of the deque, i.e., value at front.
  • GetRear Operation:
    • If the deque is empty, return -1.
    • Otherwise return the last element of the deque, i.e., value at the rear.
  • isEmpty Operation:
    • If front = -1, deque is empty. So, return true.
    • Otherwise, return false.
  • isFull Operation:
    • Deque is full when all the positions of the array are occupied, i.e., when the array becomes full. This can happen in two situations: when the front is 0 and rear is N - 1, or when the front is equal to (rear + 1).
    • Hence, if (front = 0 AND rear = N - 1) OR (front = rear + 1), deque is full. So, return true.
    • Otherwise, return false.

 

The following image shows the snapshots of the deque on performing some of the operations. Here green cell represents the position pointed by front, the red cell represents the position pointed by the rear, and the yellow cell represents the position which is pointed by both front and rear pointers:

 

Time Complexity

O(1) for every operation.

 

In the worst case, all the operations can be performed in a constant time.

Space Complexity

O(N) where N is the size of the deque.

 

O(N) extra space is required for the array.

Code Solution
(100% EXP penalty)
Implement Deque
Full screen
Console