How to efficiently implement K Stacks in a single Array?

Last Updated on September 13, 2022 by Gokul Kannan

Our task is to Implement K stacks that should use only one array. The K stacks must support these functions

1. push(int x, int sn): pushes element x to stack number ‘sn’ where sn ranges from 0 to k-1.
2. pop(int sn): pops an element from stack number ‘sn’ where sn ranges from 0 to k-1.

Method 1:

Divide the array into sections of (n/k) size:-
A simple way to implement k stacks is to divide the array into k sections of size (n/k) each and these (n/k) sections are for different stacks.

In the above example, we have constructed two stacks using a single array but the problem is that this approach is not using array spaces efficiently. Because in this example we still have free spaces in the first stack but still we cannot use those free spaces for stack 2.

Method 2:

1. This method is space efficient, and the idea is to use two extra arrays for efficient implementation of k stacks in an array. In this approach, we are going to use two extra arrays named top and next.
2. The top array is used to store the index of the top element of the stack. Its size will be equal to the number of stacks.
3. The next array is an array of size N. This next array is used to keep track of two things:-
   a. the next (lower) element of the stack. For example, let’s say ith index of arr i.e arr[i] stores the actual elements of the stack then next[i] stores the index of the next (lower) element in the stack.
   b. the next free space available in the array. If arr[i] is a free (i.e no element is stored there), then next[i] stores the index of the next free slot available in the array.

Input:
S = Number of stacks, N = Size of array

Algorithm:

1. Create an array arr of size S, Array that will store the content of the stacks.
2. Create an array top of size N, and initialize all the indices with -1. This will store the top element of every stack.
3. Create an array next of size S.
4. Initially, the complete array arr belongs to the free list i.e (No element is pushed yet). So, for every index ‘i’ in next, set next[i] = i + 1.
5. Set the last pointer of the free list to -1, i.e. next[S-1] = -1.
6. Create a variable to store the starting index of the free list. i.e free = 0.

Push Operation:

1. If free= – 1, means array is full. So, we cannot insert a new element.
2. Otherwise,
   a. Store the index of the first free slot in a temporary variable, say index, i.e. index = free.
   b. Update the starting index of the free list as, free = next[freeStart].
   c. Store the new element in the free slot as arr[index] = X.
   d. Update the next pointer of the new element as next[index] = top[M-1].
   e. Add the element to the stack by updating the head/top of the stack list as top[M-1] = index.
   f. Return true.

Pop Operation:

1. If top[M-1] = – 1, the Mth stack is empty. So, just return -1.
2. Otherwise,
   a. Find the index of the top element of the stack and store it in a variable say index, i.e. index = top[M-1].
   b. Remove the element from the stack by updating the head/top of the stack list as top[M-1] = next[index].
   c. Add the free slot to the free list as next[index] = free.
   d. Update the starting index of the free list as, free = index.
   e. Return the popped element.

Code Implementation:

#include<bits/stdc++.h>
using namespace std;
  
// class kStacks
class kStacks{
    // Array of size n to store elements i.e elements that will be pushed in stack
    int *arr;   
    // top array store indexes of top elements of stacks
    int *top;   
    int *next;  
    // Array of size n to store next entry in all stacks and free list
    int n, k;
    // store beginning index of free list
    int free; 
public:
    //constructor 
    kStacks(int k1, int n1){
    // Initialize n and k, and allocate memory for all arrays
    k = k1, n = n1;
    arr = new int[n];
    top = new int[k];
    next = new int[n];
  
    // Initialize all stacks as empty with -1
    for (int i = 0; i < k; i++)
        top[i] = -1;
  
    // Initialize all spaces as free
    free = 0;
    for (int i=0; i<n-1; i++)
        next[i] = i+1;
    next[n-1] = -1;  // -1 is used to indicate end of free list
    }
  
    //function checks if there is space available
    bool isFull(){
      return (free == -1);
    }
  
    // push an item in stack number 'sn' is stack number
    void push(int item, int sn){
    // Overflow check
    if (isFull()){
        cout << "Stack Overflow NO free spaces\n";
        return;
    }

    // Store index of first free space
    int i = free;   
  
    // Update index of free slot to index of next slot in free list
    free = next[i];
  
    // Update next of top and then top for stack number 'sn'
    next[i] = top[sn];
    top[sn] = i;
  
    // Put the item in array
    arr[i] = item;
    }
  
    // pop from stack number 'sn'
    int pop(int sn){
    // check if stack is already empty
    if (isEmpty(sn)){
         cout << "\nStack is Empty\n";
         return INT_MAX;
    }
  
  
    // Find index of top item in stack number 'sn'
    int i = top[sn];
   // Change top to store next of previous top
    top[sn] = next[i];  
  
    // Attach the previous top to the beginning of free list
    next[i] = free;
    free = i;
  
    // Return the previous top item
    return arr[i];
    }
  
    // check stack number 'sn' is empty or not?
    bool isEmpty(int sn){
      return (top[sn] == -1); 
    }
};
  
int main(){
    // creating 3 stacks in array of size 10
    int k = 3, n = 10;
    kStacks kStk(k, n);
    

    // pushing elements in stack 0
    kStk.push(11, 0);

    // pushing elements in stack 2
    kStk.push(15, 2);
    kStk.push(45, 2);

    // pushing elements in stack 1
    kStk.push(17, 1);
    kStk.push(49, 1);
    kStk.push(39, 1);

    cout << "Pop from stack 0: " << kStk.pop(0) << endl;
    cout << "Pop from stack 2: " << kStk.pop(2) << endl;
    cout << "Pop from stack 1: " << kStk.pop(1) << endl;
}

Output:
Pop from stack 0: 11
Pop from stack 2: 45
Pop from stack 1: 39

Time complexity of operations push() and pop() is O(1).
Time Complexity: O(N), Although push() and pop() functions are still O(1) but we have traversed N times for initializing all stacks.
Auxiliary Space: O(N), Since, we have used extra spaces for the stack.

This article tried to discuss How to efficiently implement K Stacks in a single Array?
Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.