Implement 3 stacks in a single array
Given a sequence of queries of insertion and deletion from 3 stacks, you need to implement three stacks using a single array such that the size of the array doesn’t exceed the number of queries.

In each query, the input is of two types :

Id 0: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 0 means we have to pop a top element from the stack.

Id 1 ele: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 1 means we have to push ‘ele’ element on top of the stack.

After each pop operation, you have to print the element which is removed.

Note: If a pop operation is used in an empty stack nothing happens to the stack, but you have to print -1.

Input Format :

The first line of the input contains ‘T’ denoting the number of test cases. The first line of each test case contains ‘Q’ denoting the number of queries. In the next Q lines input is either of the types : Id 0: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 0 means we have to pop a top element from the stack. Id 1 ele: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 1 means we have to push ‘ele’ element on top of the stack.

Output Format :

For each query of type 0, If the stack is non-empty print the removed element. If a stack is empty print -1. Print each element in the new line.

Constraints :

1

Question

Implement 3 stacks in a single array

Given a sequence of queries of insertion and deletion from 3 stacks, you need to implement three stacks using a single array such that the size of the array doesn’t exceed the number of queries.

In each query, the input is of two types :

Id 0: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 0 means we have to pop a top element from the stack.

Id 1 ele: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 1 means we have to push ‘ele’ element on top of the stack.

After each pop operation, you have to print the element which is removed.

Note: If a pop operation is used in an empty stack nothing happens to the stack, but you have to print -1.

Input Format :

The first line of the input contains ‘T’ denoting the number of test cases.

The first line of each test case contains ‘Q’ denoting the number of queries.

In the next Q lines input is either of the types :

    Id 0: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 0 means we have to pop a top element from the stack. 

    Id 1 ele: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 1 means we have to push ‘ele’ element on top of the stack.

Output Format :

For each query of type 0, If the stack is non-empty print the removed element.

If a stack is empty print -1.

Print each element in the new line.

Constraints :

1 <= T <= 3
0 <= Q, ele  <= 10^5
0 <= id <= 2  , denoting one of the three stack

Time Limit : 1 sec

Accepted Answer

One method could be to divide the array in slots of size n/3. A simple way to implement 3 stacks is to divide the array in 3 slots of size n/3 each, and fix the slots for different stacks, i.e., use arr[0] to arr[n/3-1] for first stack, and arr[n/3] to arr[2n/3-1] for stack2 where arr[] is the array to be used to implement 3 stacks and size of array be n. The problem with this method is inefficient use of array space. A stack push operation may result in stack overflow even if there is space available in arr[].

A space efficient implementation : The idea is to use two extra arrays for efficient implementation of 3 stacks in an array.
Following are the two extra arrays are used :
1) top[]: This is of size 3 and stores indexes of top elements in all stacks.
2) next[]: This is of size n and stores indexes of next item for the items in array arr[]. Here arr[] is actual array that stores 3 stacks.
Together with 3 stacks, a stack of free slots in arr[] is also maintained. The top of this stack is stored in a variable ‘free’.
All entries in top[] are initialized as -1 to indicate that all stacks are empty. All entries next[i] are initialized as i+1 because all slots are free initially and pointing to next slot. Top of free stack, ‘free’ is initialized as 0.

Accepted Answer

Brute

You will create an array ‘arr’ of size Q which will keep all the elements pushed in three arrays. Since we are using 3 stacks in a single array, we need to have a way of finding the position of the top of the stack (tos) in the array, for which we will store the tos position of all 3 stacks. You also need an array ‘prev’ of size Q, where prev[i] tells what is the index of the prev element in the current stack.

Eg: if the input is

1

7

0 1 5

0 1 1

1 1 6

2 1 8

0 1 4

1 1 2

0 1 6

Then our arrays will be like this:

tos= {6 , 4, 3} , // tos stores position of top of stack

Prev[1] =0, because in stack 0 if we pop the element at position 1, the tos will be 5 which is at position 0.

Algo for pop operation:

If tos of the stack is -1, then it means the stack is empty, print -1.
If tos is not -1, then print the element at position tos, mark the current position in ‘arr’ array as -1 representing its empty and change the

tos[stack_id]= prev[ tos[ stack_id ] ].

Algo for push operation:

Find an empty index in the array, say emp_id.
Then change prev[ emp_id ] = tos[stack_id], to link the next element that is to be pushed.
Update tos as tos[ stack_id] =emp_id, and update value at position emp_id in array ‘arr’.

Space Complexity: O(n)Explanation:

We are only using arrays of the size of Q, thus space complexity is O(Q)

Time Complexity: O(n^2)Explanation:

There are Q queries and in each query, the most expensive job is finding an empty index in the array where we have pushed an element. This is done in O(Q) thus net time complexity is O(Q^2).

Java (SE 1.8)

/*

    Time Complexity: O(Q^2)

    Space Complexity: O(Q)

    where Q is number of Queries

*/



import java.util.Arrays;



public class Solution {



    public static int findEmptyIndex(int q, int[] arr) {

        for (int i = 0; i < q; i++) {

            if (arr[i] == -1) {

                return i;

            }

        }

        return -1;

    }



    public static void solve(int q, int[][] queries) {

        int[] tos = { -1, -1, -1 }; // denotes position of top of stack of 3 stacks



        int[] arr = new int[q];

        int[] prev = new int[q];

        Arrays.fill(arr, -1);



        for (int i = 0; i < q; i++) {

            prev[i] = i - 1;

        }



        for (int i = 0; i < q; i++) {

            int id = queries[i][0], t = queries[i][1];

            if (t == 0) { // pop



                if (tos[id] == -1) {

                    System.out.print("-1
");

                } else {

                    int cur = tos[id];

                    System.out.println(arr[cur]);

                    arr[cur] = -1;

                    tos[id] = prev[cur];

                }



            } else { // push

                int nxt = findEmptyIndex(q, arr);

                int cur = tos[id];



                prev[nxt] = cur;

                tos[id] = nxt;

                arr[nxt] = queries[i][2];

            }

        }



    }

}

Python (3.5)

"""
    Time Complexity: O(Q^2)
    Space Complexity: O(Q)
    where Q is number of Queries
"""
def findEmptyIndex(q,arr):
    for i in range(q):
        if(arr[i]==-1):
            return i
    return -1

def solve(q,query):
    tos=[-1,-1,-1]

    
    prev=[]

    arr=[-1]*q

    for i in range (q):
        prev.append(i-1)

    for x in query:
        id=x[0]
        t=x[1]
        if t==0:
            if tos[id]==-1:
                print(-1)
            else:
                cur=tos[id]
                print(arr[cur])
                arr[cur]=-1
                tos[id]=prev[cur]
        else:
            # push
            nxt=findEmptyIndex(q,arr)
            cur=tos[id]
            prev[nxt]=cur
            tos[id]=nxt
            arr[nxt]=x[2]

C++ (g++ 5.4)

/*
    Time Complexity: O(Q^2)
    Space Complexity: O(Q)
    where Q is number of Queries
*/

int findEmptyIndex(int q,int *arr){	
	for(int i=0;i		if( arr[i] == -1 ){
			return i;
		}
	}
	return -1;
}

void solve( int q, vector> query ) {
	
	int tos[3]= {-1,-1,-1}; // denotes position of top of stack of 3 stacks
	int arr[q] , prev[q];
	fill(arr,arr+q,-1);
	
	for(int i=0;i	
	for(auto x:query){
		int id= x[0] ,t= x[1];
		if(t==0){	// pop
			
			if(tos[id]==-1){
				cout<<"-1
";
			}
			else{
				int cur= tos[id];
				cout<< arr[cur] <<"
";
				arr[cur]=-1;
				tos[id]= prev[cur];
			}
			
		}else{	// push
			int nxt = findEmptyIndex(q, arr); 
			int cur= tos[id];
			
			prev[nxt]= cur;
			tos[id]=nxt;
			arr[nxt]= x[2];
		}
	}
	
	
}

Accepted Answer

Optimal

The approach is mostly the same as brute force, the only difference is instead of doing findEmptyIndex() in O(Q), we will do it in O( log(Q) ) using set or priority queue.

Or we can also do it in O(1) using unordered_set