Last Updated: 11 Feb, 2021
N Stacks In An Array
Hard
Asked in companies
Design a data structure to implement ‘N’ stacks using a single array of size ‘S’. It should support the following operations:
push(X, M): Pushes an element X into the Mth stack. Returns true if the element is pushed into the stack, otherwise false.
pop(M): Pops the top element from Mth Stack. Returns -1 if the stack is empty, otherwise, returns the popped element.
Two types of queries denote these operations :
Type 1: for push(X, M) operation.
Type 2: for pop(M) operation.
Input format :
The first line of input contains three space-separated integers ‘N’, ‘S’ and ‘Q’ denoting the number of stacks, the size of the array and number of queries, respectively.
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 query of type 1, the integer ‘P’ is equal to 1 and it is followed by two space-separated integers ‘X’ and ‘M’ denoting the element and stack on which operation is to be performed, respectively.
For query of type 2, the integer ‘P’ is equal to 2 and it is followed by a single integer ‘M’ denoting the stack on which operation is to be performed.
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 <= N <= S <= 1000
1 <= Q <= 10^5
1 <= P <= 2
1 <= X <= 10^5
Time Limit: 1 sec
Where ‘S’ represents the size of the array, ‘N’ represents the number of stacks, ‘Q’ represents the number of queries, ‘P’ represents the type of operation and ‘X’ represents the element.
Approaches
Note: This approach will give wrong answer on test cases.
- A brute approach could be to divide the array of size S, into N parts of size S/N each.
- We use these parts to implement the N number of stacks.
- For example, if we have an array of size S:
- The first stack will use the subarray Array[0, S/N - 1].
- The second stack will use the subarray Array[S/N, 2*S/N - 1].
- And so one till the Nth stack which will use the subarray Array[(N-1)*S/N, S-1]
- An important point to note here is that every stack has a maximum size of S/N. Hence, if there are more than S/N push operations for any particular stack it will result in an overflow even if there is space available in the array. So, this approach may not work for all the test cases.
Algorithm:
- Create an array arr of size S, which will be used to implement the stacks.
- Create another array top of size N, which will be used to keep track of the indices of the top elements of every stack.
- For every index ‘i’ (0 to N-1) in top, initialise top[i] with one less than the starting index of the subarray which is used for the ith stack i.e, top[i] = i * S / N - 1.
Algorithm for Push Operation:
- If top[m-1] >= ((m * s) / n - 1), then the Mth stack is full. Hence, we cannot insert the element. So, return false.
- Otherwise,
- Update the index of the new top element by incrementing top[m-1].
- Insert X at index top[m-1] in the array.
- Return true.
Algorithm for Pop Operation:
- If top[m-1] < ((m - 1) * (s / n)), then the Mth stack is empty. So, just return -1.
- Otherwise,
- Store the top element of Mth stack, i.e. arr[top[m - 1]], in a temporary variable say, element.
- Update the index of the new top element by decrementing top[m-1].
- Return element.
- The brute force approach does not use the array space efficiently.
- For an efficient implementation of N-stacks, instead of dividing the array equally among the N stacks, we use two extra arrays.
- The extra arrays used are top and next.
- The top array is similar to the one used in the previous approach. It is used to keep track of the indices of the top elements of every stack.
- The next array is an array of size N which is used to keep track of the next (lower) element of the stack and also the next free space available in the array.
- For any index ‘i’ in the array, if arr[i] stores an element of a stack, then next[i] stores the index of the next (lower) element in the stack.
- Otherwise, if arr[i] is a free slot (i.e. doesn’t store any element), then next[i] stores the index of the next free slot available in the array.
- The idea is similar to maintaining a linked list for every stack. But instead of dynamically allocating the memory, we maintain the linked list inside the array itself.
- The head (or starting index) of the linked list (for every stack) is stored in the array top and the next pointers/indices are maintained using the next array.
- We also maintain a list of free slots present in the array. This is done in a similar manner by storing the starting index of the free list in a variable, say freeStart, and storing the next pointers/indices in the next array.
- So, whenever a new element is to be pushed into a stack, we choose a free slot from the free list, store the element in the free slot and add it to the list of the corresponding stack.
- And whenever an element is popped from a stack, we remove the top slot from the stack’s list, add it to the free list and return the element which was stored at that slot.
Algorithm:
- Create an array arr of size S, which will be used to implement the stacks.
- Create an array top of size N, and initialise all the indices to -1.
- Create another array next of size S.
- Initially, the complete array belongs to the free list. So, for every index ‘i’ in next, set next[i] = i + 1.
- Set the last pointer of the free list to -1, i.e. next[S-1] = -1.
- Store the starting index of the free list in a variable, say freeStart, i.e. freeStart = 0.
Algorithm for Push Operation:
- If freeStart = - 1, the array is full. Hence, we cannot insert the element. So, return false.
- Otherwise,
- Store the index of the first free slot in a temporary variable, say index, i.e. index = freeStart.
- Update the starting index of the free list as, freeStart = next[freeStart].
- Store the new element in the free slot as arr[index] = X.
- Update the next pointer of the new element as next[index] = top[M-1].
- Add the element to the stack by updating the head/top of the stack list as top[M-1] = index.
- Return true.
Algorithm for Pop Operation:
- If top[M-1] = - 1, the Mth stack is empty. So, just return -1.
- Otherwise,
- Find the index of the top element of the stack and store it in a variable say index, i.e. index = top[M-1].
- Remove the element from the stack by updating the head/top of the stack list as top[M-1] = next[index].
- Add the free slot to the free list as next[index] = freeStart.
- Update the starting index of the free list as, freeStart = index.
- Return the popped element.