How to efficiently implement k stacks in a single array?

Last Updated : 24 May, 2023

We have discussed space-efficient implementation of 2 stacks in a single array. In this post, a general solution for k stacks is discussed. Following is the detailed problem statement. Create a data structure kStacks that represents k stacks. Implementation of kStacks should use only one array, i.e., k stacks should use the same array for storing elements.

The following functions must be supported by k Stacks. push(int x, int sn) –> pushes x to stack number ‘sn’ where sn is from 0 to k-1 pop(int sn) –> pops an element from stack number ‘sn’ where sn is from 0 to k-1

Method 1 (Divide the array in slots of size n/k) A simple way to implement k stacks is to divide the array in k slots of size n/k each, and fix the slots for different stacks, i.e., use arr[0] to arr[n/k-1] for first stack, and arr[n/k] to arr[2n/k-1] for stack2 where arr[] is the array to be used to implement two 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[]. For example, say the k is 2 and array size (n) is 6 and we push 3 elements to first and do not push anything to second stack. When we push 4th element to first, there will be overflow even if we have space for 3 more elements in array.

Method 2 (A space-efficient implementation) The idea is to use two extra arrays for efficient implementation of k stacks in an array. This may not make much sense for integer stacks, but stack items can be large for example stacks of employees, students, etc where every item is of hundreds of bytes. For such large stacks, the extra space used is comparatively very less as we use two integer arrays as extra space.

Following are the two extra arrays are used:

1) top[]: This is of size k 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 k stacks. Together with k 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.

Algorithm:

Initialize an array of size k to keep track of the top element of each stack.

Initialize an array next of size n, where n is the total size of the array that will hold the k stacks. Set the value of next[i] to i+1 for all 0 ? i < n-1, and next[n-1] to -1. This array will be used to keep track of the next element in the stack.

Initialize an array top of size k to store the index of the top element of each stack. Set the value of top[i] to -1 for all 0 ? i < k.

To push an element onto the i-th stack, do the following:

Check if the array is full by checking if next[0] is -1. If it is, return an error message indicating that the stack is full.

Set the value of next[0] to top[i].

Set the value of top[i] to 0.

Set the value of next[top[i]] to the new element’s index.

Increment the value of top[i] by the block size.

To pop an element from the i-th stack, do the following:

Check if the stack is empty by checking if top[i] is -1. If it is, return an error message indicating that the stack is empty.

Decrement the value of top[i] by the block size.

Set the value of next[top[i]] to -1.

Return the element at the index top[i] + block size – 1.

Following is the implementation of the above idea.

C++

// A C++ program to demonstrate implementation of k stacks in a single 
// array in time and space efficient way
#include<bits/stdc++.h>
using namespace std;
 
// A C++ class to represent k stacks in a single array of size n
class kStacks
{
    int *arr;   // Array of size n to store actual content to be stored in stacks
    int *top;   // Array of size k to store indexes of top elements of stacks
    int *next;  // Array of size n to store next entry in all stacks
                // and free list
    int n, k;
    int free; // To store beginning index of free list
public:
    //constructor to create k stacks in an array of size n
    kStacks(int k, int n);
 
    // A utility function to check if there is space available
    bool isFull()   {  return (free == -1);  }
 
    // To push an item in stack number 'sn' where sn is from 0 to k-1
    void push(int item, int sn);
 
    // To pop an from stack number 'sn' where sn is from 0 to k-1
    int pop(int sn);
 
    // To check whether stack number 'sn' is empty or not
    bool isEmpty(int sn)  {  return (top[sn] == -1); }
};
 
//constructor to create k stacks in an array of size n
kStacks::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
    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
}
 
// To push an item in stack number 'sn' where sn is from 0 to k-1
void kStacks::push(int item, int sn)
{
    // Overflow check
    if (isFull())
    {
        cout << "\nStack Overflow\n";
        return;
    }
 
    int i = free;      // Store index of first free slot
 
    // 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;
}
 
// To pop an element from stack number 'sn' where sn is from 0 to k-1
int kStacks::pop(int sn)
{
    // Underflow check
    if (isEmpty(sn))
    {
         cout << "\nStack Underflow\n";
         return INT_MAX;
    }
 
 
    // Find index of top item in stack number 'sn'
    int i = top[sn];
 
    top[sn] = next[i];  // Change top to store next of previous top
 
    // Attach the previous top to the beginning of free list
    next[i] = free;
    free = i;
 
    // Return the previous top item
    return arr[i];
}
 
/* Driver program to test twoStacks class */
int main()
{
    // Let us create 3 stacks in an array of size 10
    int k = 3, n = 10;
    kStacks ks(k, n);
 
    // Let us put some items in stack number 2
    ks.push(15, 2);
    ks.push(45, 2);
 
    // Let us put some items in stack number 1
    ks.push(17, 1);
    ks.push(49, 1);
    ks.push(39, 1);
 
    // Let us put some items in stack number 0
    ks.push(11, 0);
    ks.push(9, 0);
    ks.push(7, 0);
 
    cout << "Popped element from stack 2 is " << ks.pop(2) << endl;
    cout << "Popped element from stack 1 is " << ks.pop(1) << endl;
    cout << "Popped element from stack 0 is " << ks.pop(0) << endl;
 
    return 0;
}

Java

// Java program to demonstrate implementation of k stacks in a single 
// array in time and space efficient way
 
public class GFG 
{
    // A Java class to represent k stacks in a single array of size n
    static class KStack 
    {
        int arr[];   // Array of size n to store actual content to be stored in stacks
        int top[];   // Array of size k to store indexes of top elements of stacks
        int next[];  // Array of size n to store next entry in all stacks
                     // and free list
        int n, k;
        int free; // To store beginning index of free list
 
        //constructor to create k stacks in an array of size n
        KStack(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
            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
        }
 
        // A utility function to check if there is space available
        boolean isFull() 
        {
            return (free == -1);
        }
 
        // To push an item in stack number 'sn' where sn is from 0 to k-1
        void push(int item, int sn) 
        {
            // Overflow check
            if (isFull()) 
            {
                System.out.println("Stack Overflow");
                return;
            }
 
            int i = free; // Store index of first free slot
 
            // 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;
        }
 
        // To pop an element from stack number 'sn' where sn is from 0 to k-1
        int pop(int sn) 
        {
            // Underflow check
            if (isEmpty(sn)) 
            {
                System.out.println("Stack Underflow");
                return Integer.MAX_VALUE;
            }
 
            // Find index of top item in stack number 'sn'
            int i = top[sn];
 
            top[sn] = next[i]; // Change top to store next of previous top
 
            // Attach the previous top to the beginning of free list
            next[i] = free;
            free = i;
 
            // Return the previous top item
            return arr[i];
        }
 
        // To check whether stack number 'sn' is empty or not
        boolean isEmpty(int sn) 
        {
            return (top[sn] == -1);
        }
 
    }
 
    // Driver program
    public static void main(String[] args) 
    {
        // Let us create 3 stacks in an array of size 10
        int k = 3, n = 10;
         
        KStack ks = new KStack(k, n);
 
        ks.push(15, 2);
        ks.push(45, 2);
 
        // Let us put some items in stack number 1
        ks.push(17, 1);
        ks.push(49, 1);
        ks.push(39, 1);
 
        // Let us put some items in stack number 0
        ks.push(11, 0);
        ks.push(9, 0);
        ks.push(7, 0);
 
        System.out.println("Popped element from stack 2 is " + ks.pop(2));
        System.out.println("Popped element from stack 1 is " + ks.pop(1));
        System.out.println("Popped element from stack 0 is " + ks.pop(0));
    }
}
// This code is Contributed by Sumit Ghosh

Python3

# Python 3 program to demonstrate implementation 
# of k stacks in a single array in time and space 
# efficient way 
class KStacks:
     
    def __init__(self, k, n):
        self.k = k # Number of stacks.
        self.n = n # Total size of array holding 
                   # all the 'k' stacks.
 
        # Array which holds 'k' stacks.
        self.arr = [0] * self.n
 
        # All stacks are empty to begin with 
        # (-1 denotes stack is empty).
        self.top = [-1] * self.k
 
        # Top of the free stack.
        self.free = 0
 
        # Points to the next element in either
        # 1. One of the 'k' stacks or,
        # 2. The 'free' stack.
        self.next = [i + 1 for i in range(self.n)]
        self.next[self.n - 1] = -1
 
    # Check whether given stack is empty.
    def isEmpty(self, sn):
        return self.top[sn] == -1
 
    # Check whether there is space left for 
    # pushing new elements or not.
    def isFull(self):
        return self.free == -1
 
    # Push 'item' onto given stack number 'sn'.
    def push(self, item, sn):
        if self.isFull():
            print("Stack Overflow")
            return
 
        # Get the first free position 
        # to insert at.
        insert_at = self.free
 
        # Adjust the free position.
        self.free = self.next[self.free]
 
        # Insert the item at the free 
        # position we obtained above.
        self.arr[insert_at] = item
 
        # Adjust next to point to the old
        # top of stack element.
        self.next[insert_at] = self.top[sn]
 
        # Set the new top of the stack.
        self.top[sn] = insert_at
 
    # Pop item from given stack number 'sn'.
    def pop(self, sn):
        if self.isEmpty(sn):
            return None
 
        # Get the item at the top of the stack.
        top_of_stack = self.top[sn]
 
        # Set new top of stack.
        self.top[sn] = self.next[self.top[sn]]
 
        # Push the old top_of_stack to 
        # the 'free' stack.
        self.next[top_of_stack] = self.free
        self.free = top_of_stack
 
        return self.arr[top_of_stack]
 
    def printstack(self, sn):
        top_index = self.top[sn]
        while (top_index != -1):
            print(self.arr[top_index])
            top_index = self.next[top_index]
 
# Driver Code
if __name__ == "__main__":
     
    # Create 3 stacks using an 
    # array of size 10.
    kstacks = KStacks(3, 10)
 
    # Push some items onto stack number 2.
    kstacks.push(15, 2)
    kstacks.push(45, 2)
 
    # Push some items onto stack number 1.
    kstacks.push(17, 1)
    kstacks.push(49, 1)
    kstacks.push(39, 1)
 
    # Push some items onto stack number 0.
    kstacks.push(11, 0)
    kstacks.push(9, 0)
    kstacks.push(7, 0)
 
    print("Popped element from stack 2 is " +
                         str(kstacks.pop(2)))
    print("Popped element from stack 1 is " +
                         str(kstacks.pop(1)))
    print("Popped element from stack 0 is " +
                         str(kstacks.pop(0)))
 
    kstacks.printstack(0)
 
# This code is contributed by Varun Patil

C#

using System;
 
// C# program to demonstrate implementation of k stacks in a single  
// array in time and space efficient way 
 
public class GFG
{
    // A c# class to represent k stacks in a single array of size n 
    public class KStack
    {
        public int[] arr; // Array of size n to store actual content to be stored in stacks
        public int[] top; // Array of size k to store indexes of top elements of stacks
        public int[] next; // Array of size n to store next entry in all stacks
                     // and free list 
        public int n, k;
        public int free; // To store beginning index of free list
 
        //constructor to create k stacks in an array of size n 
        public KStack(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 
            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
        }
 
        // A utility function to check if there is space available 
        public virtual bool Full
        {
            get
            {
                return (free == -1);
            }
        }
 
        // To push an item in stack number 'sn' where sn is from 0 to k-1 
        public virtual void push(int item, int sn)
        {
            // Overflow check 
            if (Full)
            {
                Console.WriteLine("Stack Overflow");
                return;
            }
 
            int i = free; // Store index of first free slot
 
            // 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;
        }
 
        // To pop an element from stack number 'sn' where sn is from 0 to k-1 
        public virtual int pop(int sn)
        {
            // Underflow check 
            if (isEmpty(sn))
            {
                Console.WriteLine("Stack Underflow");
                return int.MaxValue;
            }
 
            // Find index of top item in stack number 'sn' 
            int i = top[sn];
 
            top[sn] = next[i]; // Change top to store next of previous top
 
            // Attach the previous top to the beginning of free list 
            next[i] = free;
            free = i;
 
            // Return the previous top item 
            return arr[i];
        }
 
        // To check whether stack number 'sn' is empty or not 
        public virtual bool isEmpty(int sn)
        {
            return (top[sn] == -1);
        }
 
    }
 
    // Driver program 
    public static void Main(string[] args)
    {
        // Let us create 3 stacks in an array of size 10 
        int k = 3, n = 10;
 
        KStack ks = new KStack(k, n);
 
        ks.push(15, 2);
        ks.push(45, 2);
 
        // Let us put some items in stack number 1 
        ks.push(17, 1);
        ks.push(49, 1);
        ks.push(39, 1);
 
        // Let us put some items in stack number 0 
        ks.push(11, 0);
        ks.push(9, 0);
        ks.push(7, 0);
 
        Console.WriteLine("Popped element from stack 2 is " + ks.pop(2));
        Console.WriteLine("Popped element from stack 1 is " + ks.pop(1));
        Console.WriteLine("Popped element from stack 0 is " + ks.pop(0));
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
// javascript program to demonstrate implementation of k stacks in a single 
// array in time and space efficient way
 
    // A javascript class to represent k stacks in a single array of size n
     class KStack {
     
        // constructor to create k stacks in an array of size n
        constructor(k1 , n1) 
        {
         
            // Initialize n and k, and allocate memory for all arrays
            this.k = k1;
            this.n = n1;
            this.arr = Array(n).fill(0);
            this.top = Array(k).fill(-1);
            this.next = Array(n).fill(0);
 
         
            // Initialize all spaces as free
            this.free = 0;
            for (var i = 0; i < n - 1; i++)
                this.next[i] = i + 1;
            this.next[n - 1] = -1; // -1 is used to indicate end of free list
        }
 
        // A utility function to check if there is space available
         isFull() {
            return (this.free == -1);
        }
 
        // To push an item in stack number 'sn' where sn is from 0 to k-1
         push(item , sn)
         {
          
            // Overflow check
            if (this.isFull()) {
                document.write("Stack Overflow");
                return;
            }
 
            var i = this.free; // Store index of first free slot
 
            // Update index of free slot to index of next slot in free list
            this.free = this.next[i];
 
            // Update next of top and then top for stack number 'sn'
            this.next[i] = this.top[sn];
            this.top[sn] = i;
 
            // Put the item in array
            this.arr[i] = item;
        }
 
        // To pop an element from stack number 'sn' where sn is from 0 to k-1
         pop(sn)
         {
          
            // Underflow check
            if (this.isEmpty(sn)) {
                document.write("Stack Underflow");
                return Number.MAX_VALUE;
            }
 
            // Find index of top item in stack number 'sn'
            var i = this.top[sn];
 
            this.top[sn] = this.next[i]; // Change top to store next of previous top
 
            // Attach the previous top to the beginning of free list
            this.next[i] = this.free;
            this.free = i;
 
            // Return the previous top item
            return this.arr[i];
        }
 
        // To check whether stack number 'sn' is empty or not
         isEmpty(sn) {
            return (this.top[sn] == -1);
        }
 
    }
 
    // Driver program
     
        // Let us create 3 stacks in an array of size 10
        var k = 3;
        n = 10;
 
        var ks = new KStack(k, n);
 
        ks.push(15, 2);
        ks.push(45, 2);
 
        // Let us put some items in stack number 1
        ks.push(17, 1);
        ks.push(49, 1);
        ks.push(39, 1);
 
        // Let us put some items in stack number 0
        ks.push(11, 0);
        ks.push(9, 0);
        ks.push(7, 0);
 
        document.write("Popped element from stack 2 is " + ks.pop(2));
        document.write("<br/>Popped element from stack 1 is " + ks.pop(1));
        document.write("<br/>Popped element from stack 0 is " + ks.pop(0));
 
// This code is contributed by gauravrajput1
</script>

Output

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

Time complexities of operations push() and pop() is O(1). The best part of above implementation is, if there is a slot available in stack, then an item can be pushed in any of the stacks, i.e., no wastage of space.

Time Complexity of top() operation is also O(1)

Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(N), as we are using extra space for the stack.

S

Sachin

Improve

Previous Article

Implement Stack using Queues

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

Similar Reads

How to efficiently implement k Queues in a single array?

Introduction : One efficient way to implement k queues in a single array is to use a technique called "circular array implementation of k queues." This approach uses a single array to store elements for all k queues, and it divides the array into k segments, one for each queue. To implement this approach, we need to keep track of two pointers for e

Implement two Stacks in an Array

Create a data structure twoStacks that represent two stacks. Implementation of twoStacks should use only one array, i.e., both stacks should use the same array for storing elements. Following functions must be supported by twoStacks. push1(int x) --> pushes x to first stack push2(int x) --> pushes x to second stackpop1() --> pops an elemen

Implement Dynamic Multi Stack (K stacks) using only one Data Structure

In this article, we will see how to create a data structure that can handle multiple stacks with growable size. The data structure needs to handle three operations: push(x, stackNum) = pushes value x to the stack numbered stackNumpop(stackNum) = pop the top element from the stack numbered stackNumtop(stackNum) = shows the topmost element of the sta

Sorting array using Stacks

Given an array of elements, the task is to sort these elements using a stack. Prerequisites: Stacks Examples: Input : 8 5 7 1 9 12 10 Output : 1 5 7 8 9 10 12 Explanation : Output is sorted element set Input : 7 4 10 20 2 5 9 1 Output : 1 2 4 5 7 9 10 20 We basically use Sort a stack using a temporary stack. Then we put sorted stack elements back t

Implement a stack using single queue

We are given queue data structure, the task is to implement stack using only given queue data structure.We have discussed a solution that uses two queues. In this article, a new solution is discussed that uses only one queue. This solution assumes that we can find size of queue at any point. The idea is to keep newly inserted element always at fron

C Program for efficiently print all prime factors of a given number

Given a number n, write an efficient function to print all prime factors of n. For example, if the input number is 12, then output should be "2 2 3". And if the input number is 315, then output should be "3 3 5 7". First Approach: Following are the steps to find all prime factors. 1) While n is divisible by 2, print 2 and divide n by 2. 2) After st

Java Program for efficiently print all prime factors of a given number

Given a number n, write an efficient function to print all prime factors of n. For example, if the input number is 12, then output should be "2 2 3". And if the input number is 315, then output should be "3 3 5 7". Following are the steps to find all prime factors. 1) While n is divisible by 2, print 2 and divide n by 2. 2) After step 1, n must be

Finding the Parity of a number Efficiently

Given an integer N. The task is to write a program to find the parity of the given number. Note: Parity of a number is used to define if the total number of set-bits(1-bit in binary representation) in a number is even or odd. If the total number of set-bits in the binary representation of a number is even then the number is said to have even parity

Compute maximum of the function efficiently over all sub-arrays

Given an array, arr[] and a function F(i, j). The task is to compute max{F(i, j)} over all sub-arrays [i..j].The function F() is defined as: [Tex]F(l, r) = \sum_{i = l}^{r - 1} |arr[i] - arr[i+1]|.(-1)^{i-l}[/Tex] Examples: Input : arr[] = { 1, 5, 4, 7 } Output : 6 Values of F(i, j) for all the sub-arrays: { 1, 5 } = |1 - 5| * (1) = 4 { 1, 5, 4 } =

How to store a Sparse Vector efficiently?

A sparse vector is a vector that has a large number of zeros so it takes unwanted space to store these zeroes.The task is to store a given sparse vector efficiently without storing the zeros. Examples: Input: vector = { 2, 0, 0, 0, 0, 3, 0, 4, 0, 0, 0, 1, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 1, 0, 0, 0, 0, 5 }

Article Tags :

DSA
Stack

Practice Tags :

Stack