# Two Stacks

Posted: 23 Dec, 2020

Difficulty: Moderate

#### 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.

- Let the array used by both the stacks is
- 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.

- Check if
- 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.

- Check if

- push1(num):
- 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].

- First, we check if the
- 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].

- First, we check if the

- pop1():
- This way we can utilise the total empty space of the array available at any instant of time.

SIMILAR PROBLEMS

# Two Sum II - Input Array Is Sorted

Posted: 4 Mar, 2022

Difficulty: Moderate

# Ninja And Matrix

Posted: 12 Apr, 2022

Difficulty: Easy

# Ninja In Interview

Posted: 13 Apr, 2022

Difficulty: Easy

# Missing Number

Posted: 17 Apr, 2022

Difficulty: Easy

# Min Heap

Posted: 5 May, 2022

Difficulty: Moderate