Home » Technical Interview Questions » Stack Interview Questions » How to Efficiently Implement k Stacks in a Single Array?

How to Efficiently Implement k Stacks in a Single Array?


Difficulty Level Medium
Frequently asked in Amazon
Array Fourkites Stack

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.
READ  Iterative Tower of Hanoi

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.

READ  Design a stack that supports getMin() in O(1) time and O(1) extra space

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

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup