# Implement A PlatesStack

Posted: 23 Feb, 2021

Difficulty: Moderate

#### You are given an infinite number of stacks which are arranged in a row. All the stacks have the same maximum capacity.

#### You are supposed to implement the PlatesStack class that can perform the following operations efficiently:

```
PlatesStack(int N) - Constructor to initialize the object where N denotes the maximum capacity of each stack.
push(int value) - This function inserts the integer "value" in the leftmost stack which is not filled up to the maximum capacity.
pop() - This function returns the value at the top of the rightmost stack which is not empty and removes it from that stack or returns -1 if all the stacks are empty.
popAtStack(int index) - This function returns the value at the top of the stack with the given index and removes it from that stack and returns -1 if that stack is empty.
```

#### You have to answer multiple queries, each query will correspond to one of the above-mentioned operations.

```
TYPE 1 corresponds to the push operation.
TYPE 2 corresponds to the pop operation.
TYPE 3 corresponds to the popAtStack operation.
```

##### Input Format :

```
The first line contains a single integer T denoting the number of test cases. The test cases follow.
The first line of each test case contains an integer N denoting the maximum capacity of the stacks.
The second line of each test case contains an integer Q denoting the number of queries to be answered.
The next Q lines contain two integers TYPE and X separated by a single space. The integer TYPE denotes the type of the query and X denotes the value or the index of the stack on which the operation is to be performed.
For TYPE-2 query, value of X is always -1. You can ignore this integer.
```

##### Output Format :

```
For each query of type 2 print the value at the top of the rightmost stack or print -1 if all the stacks are empty.
For each query of type 3 print the value at the top of the stack with the given index or print -1 if the stack at the given index is empty.
Print the answer for query in a separate line.
```

##### Note :

```
You do not need to print anything. It has already been taken care of. Just implement the given class.
```

##### Constraints :

```
1 <= T <= 5
1 <= N <= 10
1 <= Q <= 1000
1 <= TYPE <= 3
1 <= value <= 10^9
Where "value" is the integer to be inserted into the stack or the index of the stack depending on the type of the query.
Time Limit: 1 sec
```

Approach 1

The idea is to maintain **pointers** to keep track of where to push or to pop an element. And whenever push or pop is called, update the pointers accordingly. For keeping track of stack pointers let’s define a HashMap in which the key will be an integer and the value will be a stack of integers.

#### The algorithm is as follows -

- Maintain two-pointers
**current**and**last**to keep track of the leftmost stack push and the rightmost stack pop operations. - Declare the
**count**variable to store the number of elements. - The push(value) function can be implemented as follows :
- Keep incrementing the
**current**pointer, if the stack corresponding to the**current**pointer has a size equal to the maximum**capacity**. - Now, the stack corresponding to the
**current**pointer has a size less than the maximum**capacity**. - Now push the
**value**to the stack, corresponding to the**current**pointer. - Since the last pointer should be the rightmost, update the
**last**pointer with last = max(last, current). - Increment the
**count**variable by 1.

- Keep incrementing the
- The pop() function can be implemented as follows :
- If the
**count**is 0, then all the stacks are empty, so return**-1**. - Keep decrementing the
**last**pointer, if the stack corresponding to the last pointer is empty. - Save the
**top**element of the stack, corresponding to the**last**pointer, and pop it. - Decrement the
**count**variable by 1. - Since the current pointer should be the leftmost, update the
**current**pointer with current = min(current, last). - Return the
**top**element.

- If the
- The popAtStack(index) function can be implemented as follows :
- Return
**-1,**If the**index**is not present in the map or stack corresponding to that index is empty. - Save the
**top**element of the stack, corresponding to the**index**pointer, and pop it. - Decrement the
**count**variable by 1. - Since the current pointer should be the leftmost, update the
**current**pointer with current = min(current, index). - Return the
**top**element.

- Return