Two Stacks

Posted: 23 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Design a data structure, which represents two stacks using only one array common for both stacks. The data structure should support the following operations:

push1(NUM) - Push ‘NUM’ into stack1.
push2(NUM) - Push ‘NUM’ into stack2.
pop1() - Pop out a top element from stack1 and return popped element, in case of underflow return -1.
pop2() - Pop out a top element from stack2 and return popped element, in case of underflow return -1.

There are 2 types of queries in the input

Type 1 - These queries correspond to Push operation.
Type 2 - These queries correspond to Pop operation.

Note:

1. You are given the size of the array.

2. You need to perform push and pop operations in such a way that we are able to push elements in the stack until there is some empty space available in the array.

3. While performing Push operations, do nothing in the situation of the overflow of the stack.
Input format:
The first line of the input contains two space-separated integers 'S' and 'Q', denoting the size of the array and number of operations to be performed respectively.

The next 'Q' lines contain operations, one per line. Each line begins with two integers ‘type’ and ‘stackNo’, denoting the type of query as mentioned above and the stack number on which this operation is going to be performed.

If the ‘type’ is 1 then it will be followed by one more integer ‘NUM’ denoting the element needed to be pushed to stack ‘stackNo’.
Output format:
For each operation of Type 2, print an integer on a single line - popped element from the stack, if the stack is already empty print -1.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
0 <= S <= 10^5
1 <= Q <= 5*10^5
1 <= type, stackNo <= 2
0 <= NUM <= 10^9

Time Limit: 1 sec.   
Approach 1
  • To utilise the array space optimally, we start the top of both stacks from the extreme of the array.
    • Let the array used by both the stacks is Arr, having size equals to ‘s’.
    • Let’s say top1 and top2 points to the top of the stacks, stack1 and stack2 respectively.
    • As the size of the array is ‘s’, we assign -1 to top1 and  ‘s’ to top2 (keeping 0 based indexing in mind) which denotes both stacks are currently empty.
  • In order to complete push operations (or operation of Type 1) we do as follows:
    • push1(num):
      • Check if Arr has enough space to push an integer or not. For this, we check top1 + 1 < top2, if this is the case then we have enough space then, we increment top1 by 1 and assign num to Arr[top1].
      • If there is insufficient space for pushing another element, which will happen in case top1 + 1 == top2. So we do nothing and just return.
    • push2(num):
      • Check if Arr has enough space to push an integer or not. For this we check top2 - 1 > top1, if this is the case then we have enough space then, we decrement top2 by 1 and assign num to Arr[top2].
      • If there is insufficient space for pushing another element, which will happen in case top2 - 1 == top1. So we do nothing and just return.
  • In order to complete pop operations (or operations of Type 2) we do as follows:
    • pop1():
      • First, we check if the stack1 is empty or not, for which we just need to check if top1 is -1 or not, it is equal to -1 then it is the condition of underflow, so we just return -1.
      • If stack1 is not empty, then we decrement top1 by 1 and return the value of Arr[top1+1].
    • pop2():
      • First, we check if the stack2 is empty or not, for which we just need to check if top2 is equal to 's' or not, it is equal to ‘s’ then, it is the condition of underflow, so we just return -1.
      • If stack2 is not empty, then we increment top2 by 1 and return the value of Arr[top2-1].
  • This way we can utilise the total empty space of the array available at any instant of time.
Try Problem