How to Efficiently Implement k Stacks in a Single Array?

Difficulty Level Medium
Frequently asked in Amazon Fourkites
Array StackViews 1993

Design and implement a new data structure that Implement k Stacks in a Single Array. The new data structure must support these two operations –

  • push (element, stack_number): that pushes the element in a given number of the stack.
  • pop (stack_number): that pop out the top element from a given number of the stack.

How to Efficiently Implement k Stacks in a Single Array?

Example

Input 

push(15, 2)
push(45, 2)
push(17, 1)
push(49, 1)
push(39, 1)
push(11, 0)
push(9, 0)
push(7, 0)
pop(2)
pop(1)
pop(0)

Output

Popped element from stack 2 : 45
Popped element from stack 1 : 39
Popped element from stack 0 : 7

Input 

push(100, 1)
push(200, 0)
push(300, 0)
pop(1)
pop(0)

Output 

Popped element from stack 1 : 100
Popped element from stack 0 : 300

Algorithm to efficiently implement k stacks in a single array

  1. Create array arr[ ] to store the elements of the stacks, top[ ] to store the index of top elements of all the stacks, and next[ ] to keep the update of the next element of all stacks.
  2. Create a variable free to store the starting index of the free list.
  3. Traverse and set all values of top[ ] as -1 and values of next[ ] as index + 1.
  4. Create function push() that accepts element and stack number as a parameter and check if a stack of the given number is full print “Stack Overflow” and return.
  5. Else Initialise a variable say i and update it as free. Update free as next(i), next(i) as the top of the stack of given number, top of the stack of a given number as i and at last push the element in the array at index i.
  6. Create function pop() that accepts stack number as a parameter and check if the stack of a given number is empty print “Stack Underflow” and return.
  7. Else Initialise a variable say i and update it as the top of the stack of a given number. Update top of the stack of a given number as next(i), next(i) as free, free as I, and at last return the element in the array at index I.

C++ Program to efficiently implement k stacks in a single array

#include<bits/stdc++.h> 
using namespace std; 
  
class newStack{ 
    int *arr;   
    int *top;   
    int *next;  
    
    int n, k; 
    int free; 
public: 
    
    newStack(int k, int n); 
  
    bool isFull(){  
        return(free == -1);  
    } 
  
    void push(int item, int sn); 
  
    int pop(int sn); 
  
    bool isEmpty(int sn){  
        return (top[sn] == -1); 
    } 
}; 
  
newStack::newStack(int k1, int n1){ 
    
    k = k1, n = n1; 
    arr = new int[n]; 
    top = new int[k]; 
    next = new int[n]; 
  
    for(int i = 0; i < k; i++) 
        top[i] = -1; 
  
    free = 0; 
    for(int i=0; i<n-1; i++) 
        next[i] = i+1; 
    next[n-1] = -1; 
} 
  
void newStack::push(int item, int sn){ 
    
    if(isFull()){ 
        cout << "\nStack Overflow\n"; 
        return; 
    } 
  
    int i = free;     
  
    free = next[i]; 
  
    next[i] = top[sn]; 
    top[sn] = i; 
  
    arr[i] = item; 
} 
  
int newStack::pop(int sn){ 
    
    if(isEmpty(sn)){ 
         cout<<"\nStack Underflow\n"; 
         return INT_MAX; 
    } 
  
    int i = top[sn]; 
  
    top[sn] = next[i];  
  
    next[i] = free; 
    free = i; 
  
    return arr[i]; 
} 
  
int main(){ 
    
    int k = 3, n = 10; 
    newStack ks(k, n); 
  
    ks.push(15, 2); 
    ks.push(45, 2); 
  
    ks.push(17, 1); 
    ks.push(49, 1); 
    ks.push(39, 1); 
  
    ks.push(11, 0); 
    ks.push(9, 0); 
    ks.push(7, 0); 
  
    cout << "Popped element from stack 2 : " << ks.pop(2) << endl; 
    cout << "Popped element from stack 1 : " << ks.pop(1) << endl; 
    cout << "Popped element from stack 0 : " << ks.pop(0) << endl; 
  
    return 0; 
}
Popped element from stack 2 : 45
Popped element from stack 1 : 39
Popped element from stack 0 : 7

Java Program to efficiently implement k stacks in a single array

class kstack{ 
    
    static class newStack{ 
        int arr[];   
        int top[];   
        int next[];  
        
        int n, k; 
        int free; 
  
        newStack(int k1, int n1){ 
            
            k = k1; 
            n = n1; 
            arr = new int[n]; 
            top = new int[k]; 
            next = new int[n]; 
  
            for(int i = 0; i < k; i++) 
                top[i] = -1; 
  
            free = 0; 
            for(int i = 0; i < n - 1; i++) 
                next[i] = i + 1; 
            next[n - 1] = -1;
        } 
  
        boolean isFull(){ 
            return (free == -1); 
        } 
  
        void push(int item, int sn){ 
            
            if(isFull()){ 
                System.out.println("Stack Overflow"); 
                return; 
            } 
  
            int i = free; 
  
            free = next[i]; 
  
            next[i] = top[sn]; 
            top[sn] = i; 
  
            arr[i] = item; 
        } 
  
        int pop(int sn){ 
            
            if(isEmpty(sn)){ 
                System.out.println("Stack Underflow"); 
                return Integer.MAX_VALUE; 
            } 
  
            int i = top[sn]; 
  
            top[sn] = next[i]; 
  
            next[i] = free; 
            free = i; 
  
            return arr[i]; 
        } 
  
        boolean isEmpty(int sn){ 
            return (top[sn] == -1); 
        } 
  
    } 
  
    public static void main(String[] args){ 
        
        int k = 3, n = 10; 
          
        newStack ks = new newStack(k, n); 
  
        ks.push(15, 2); 
        ks.push(45, 2); 
  
        ks.push(17, 1); 
        ks.push(49, 1); 
        ks.push(39, 1); 
  
        ks.push(11, 0); 
        ks.push(9, 0); 
        ks.push(7, 0); 
  
        System.out.println("Popped element from stack 2 : " + ks.pop(2)); 
        System.out.println("Popped element from stack 1 : " + ks.pop(1)); 
        System.out.println("Popped element from stack 0 : " + ks.pop(0)); 
    } 
}
Popped element from stack 2 : 45
Popped element from stack 1 : 39
Popped element from stack 0 : 7

Complexity Analysis

Time Complexity: push() and pop() uses constant time i.e. O(1). Maintaining top and next will require O(k) and O(n) time respectively.

Space Complexity: O(n) where n is elements are stored.

References

Translate »