Stack Using Deque

Easy
0/40
Average time to solve is 15m
profile
Contributed by
47 upvotes
Asked in company
Walmart

Problem statement

Design a data structure to implement a stack, using only deque (double-ended queue). It should support the following operations :

push(X): Pushes an element X into the stack. Returns true if the element is pushed into the stack, otherwise false.

pop(): Pops the top element from the stack. Returns -1 if the stack is empty, otherwise, returns the popped element.

top(): Returns the topmost element of the stack. In case the stack is empty, it returns -1.

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

size(): Returns the number of elements currently present in the stack.

Following type of queries denote these operations :

Type 1 : for push(X) operation.

Type 2 : for pop() operation.

Type 3 : for top() operation.

Type 4 : for isEmpty() operation.

Type 5 : for size() operation.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘Q’ number of queries to be performed. 

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, the integer ‘P’ is equal to 1, and it is followed by a single integer ‘X’ denoting the element on which operation is to be performed.

For the queries of type 2 to 5, 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 <= Q <= 10^5 
1 <= P <= 5
1 <= X <= 10^5

Time Limit: 1 sec
Sample Input 1 :
6
4
1 10
1 20
5
2
3
Sample Output 1 :
True 
True
True
2
20
10
Explanation 1 :
For the given input, we have the number of queries, Q = 6.
Operations performed on the stack are as follows:

isEmpty() : Stack is initially empty. So, this returns true.
push(10) : Push element ‘10’ into the stack. This returns true.
push(20) : Push element ‘20’ into the stack. This returns true.
size() : Stack has two elements in it. So, this returns 2.
pop() : Pop the top element from the stack. This returns 20.
top() : Return the topmost element of the stack i.e 10.

The following image shows the snapshots of the stack (implement using deque) after each operation:

Sample Testcase 1

Sample Input 2 :
5
1 15
1 25
4
1 30
5
Sample Output 2 :
True
True
False
True
3
Hint

Try using the operations of deque such that it works like a stack.

Approaches (1)
Approach 1
  • The idea is to use the operations of deque such that it works like a stack.
  • Now, deque supports push and pop operations from both the ends whereas stack follows a LIFO (Last In First Out) order. So the push and pop operations in a stack occur from the same end.
  • Hence, in order to implement the push and pop operations of a stack, we must restrict deque to perform the push and pop operations only from one of its end.
  • The topmost element will be the first element from that end.
  • Other operations, i.e. isEmpty() and size(), will be the same as those of deque.


Algorithm:

 

  • Push(X) Operation:
    • Insert ‘X’ to the end of the deque.
  • Pop() Operation:
    • If the stack is empty, then return -1.
    • Otherwise, pop the last element from the deque.
    • Return the popped element.
  • Top() Operation:
    • Return the last element of the deque.
  • isEmpty() Operation:
    • If deque is empty, return true.
    • Otherwise, return false.
  • Size() Operation:
    • Return the number of elements currently present in the deque.

 

Note:

 

Here we have restricted deque to perform operations from its tail/end. We can also perform the operations from its head/front.  But the idea will remain the same.

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 maximum number of elements in the stack.

 

O(N) extra space is required for storing the elements in the deque.

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