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

0 0 11 minutes read

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 stackNum

pop(stackNum) = pop the top element from the stack numbered stackNum

top(stackNum) = shows the topmost element of the stack stackNum.

Example:

Suppose the given multi stack is [{1, 2}, {4, 6}, {9, 10}]

Input: push(3, 0), top(0)
push(7, 1), top(1)
pop(2), top(2)

Output: 3, 7, 9

Explanation: When 3 is pushed in stack 0, the stack becomes {1, 2, 3}. So the top element is 3.
When 7 is pushed in stack 1, the stack becomes {4, 6, 7}. So the top element is 7.
When topmost element is popped from stack 2, the stack becomes {9}. So the topmost element is 9

Approach: Follow the approach mentioned below to implement the idea.

Store the size and the top index of every stack in arrays sizes[] and topIndex[].
The sizes will be stored in a prefix sum array (using a prefix array sum will help us find the start/size of a stack in O(1) time)
If the size of a stack reaches the maximum reserved capacity, expand the reserved size (multiply by 2)
If the size of a stack gets down to a quarter of the reserved size shrink the reserved size (divide it by 2)
Every time we need to expand/shrink a stack in the data structure, the indexes of other stacks might change so we need to take care of that. That is taken care by incrementing/decrementing value of sizes[] and topIndex[] arrays (we can do that in O(number of stacks) time).

Below is the implementation :

C++

#include <bits/stdc++.h>
using namespace std;
 
template <typename T>
 
// Class to implement multistack
class MultiStack {
    int numberOfStacks;
    vector<T> values;
    vector<int> sizes, topIndex;
 
public:
    // Constructor to create k stacks
    // (by default 1)
    MultiStack(int k = 1)
        : numberOfStacks(k)
    {
        // reserve 2 elements for each stack first
        values = vector<T>(numberOfStacks << 1);
 
        // For each stack store the index
        // of the element on the top
        // and the size (starting point)
        sizes = vector<int>(numberOfStacks);
        topIndex = vector<int>(numberOfStacks);
 
        // Sizes is a prefix sum vector
        for (int size = 2, i = 0; i < numberOfStacks;
             i++, size += 2)
            sizes[i] = size, topIndex[i] = size - 2;
    }
 
    // Push a value in a stack
    void push(int stackNum, T val)
    {
 
        // Check if the stack is full,
        // if so Expand it
        if (isFull(stackNum))
            Expand(stackNum);
 
        // Add the value to the top of the stack
        // and increment the top index
        values[topIndex[stackNum]++] = val;
    }
 
    // Pop the top value and
    // return it from a stack
    T pop(int stackNum)
    {
 
        // If the stack is empty
        // throw an error
        if (empty(stackNum))
            throw("Empty Stack!");
 
        // Save the top value
        T val = values[topIndex[stackNum] - 1];
 
        // Set top value to default data type
        values[--topIndex[stackNum]] = T();
 
        // Shrink the reserved size if needed
        Shrink(stackNum);
 
        // Return the pop-ed value
        return val;
    }
 
    // Return the top value form a stack
    // Same as pop (but without removal)
    T top(int stackNum)
    {
        if (empty(stackNum))
            throw("Empty Stack!");
        return values[topIndex[stackNum] - 1];
    }
 
    // Return the size of a stack
    // (the number of elements in the stack,
    // not the reserved size)
    int size(int stackNum)
    {
        if (!stackNum)
            return topIndex[0];
        return topIndex[stackNum] - sizes[stackNum - 1];
    }
 
    // Check if a stack is empty or not
    // (has no elements)
    bool empty(int stackNum)
    {
        int offset;
        if (!stackNum)
            offset = 0;
        else
            offset = sizes[stackNum - 1];
        int index = topIndex[stackNum];
        return index == offset;
    }
 
    // Helper function to check
    // if a stack size has reached
    // the reserved size of that stack
    bool isFull(int stackNum)
    {
        int offset = sizes[stackNum];
        int index = topIndex[stackNum];
        return index >= offset;
    }
 
    // Function to expand the reserved size
    // of a stack (multiply by 2)
    void Expand(int stackNum)
    {
 
        // Get the reserved_size of the stack()
        int reserved_size = size(stackNum);
 
        // Update the prefix sums (sizes)
        // and the top index of the next stacks
        for (int i = stackNum + 1; i < numberOfStacks; i++)
            sizes[i] += reserved_size,
                topIndex[i] += reserved_size;
 
        // Update the size of the recent stack
        sizes[stackNum] += reserved_size;
 
        // Double the size of the stack by
        // inserting 'reserved_size' elements
        values.insert(values.begin() + topIndex[stackNum],
                      reserved_size, T());
    }
 
    // Function to shrink the reserved size
    // of a stack (divide by2)
    void Shrink(int stackNum)
    {
 
        // Get the reserved size and the current size
        int reserved_size, current_size;
        if (!stackNum)
            reserved_size = sizes[0],
            current_size = topIndex[0];
        else
            reserved_size
                = sizes[stackNum] - sizes[stackNum - 1],
                current_size
                = topIndex[stackNum] - sizes[stackNum - 1];
 
        // Shrink only if the size is
        // lower than a quarter of the
        // reserved size and avoid shrinking
        // if the reserved size is 2
        if (current_size * 4 > reserved_size
            || reserved_size == 2)
            return;
 
        // Divide the size by 2 and update
        // the prefix sums (sizes) and
        // the top index of the next stacks
        int dif = reserved_size / 2;
        for (int i = stackNum + 1; i < numberOfStacks; i++)
            sizes[i] -= dif, topIndex[i] -= dif;
        sizes[stackNum] -= dif;
 
        // Erase half of the reserved size
        values.erase(values.begin() + topIndex[stackNum],
                     values.begin() + topIndex[stackNum]
                         + dif);
    }
};
 
// Driver code
int main()
{
    // create 3 stacks
    MultiStack<int> MStack(3);
 
    // push elements in stack 0:
    MStack.push(0, 21);
    MStack.push(0, 13);
    MStack.push(0, 14);
 
    // Push one element in stack 1:
    MStack.push(1, 15);
 
    // Push two elements in stack 2:
    MStack.push(2, 1);
    MStack.push(2, 2);
    MStack.push(2, 3);
 
    // Print the top elements of the stacks
    cout << MStack.top(0) << '\n';
    cout << MStack.top(1) << '\n';
    cout << MStack.top(2) << '\n';
 
    return 0;
}

Java

// Java implementation for the above approach
 
import java.util.*;
 
class MultiStack<T> {
  private int numberOfStacks;
  private ArrayList<T> values;
  private ArrayList<Integer> sizes, topIndex;
 
  // Constructor for MultiStack
  // Takes the number of stacks (k) as input and initializes the MultiStack object
  public MultiStack(int k) {
     
    // Set the number of stacks
    numberOfStacks = k;
     
    // Initialize the values ArrayList with an initial capacity of k*2
    values = new ArrayList<>(numberOfStacks << 1);
     
    // Initialize the sizes ArrayList with a size of k
    sizes = new ArrayList<>(numberOfStacks);
     
    // Initialize the topIndex ArrayList with a size of k
    topIndex = new ArrayList<>(numberOfStacks);
 
      // Loop through k times
      for (int size = 2, i = 0; i < numberOfStacks; i++, size += 2) {
         
          // Add size to the sizes ArrayList
          sizes.add(size);
         
          // Add size-2 to the topIndex ArrayList
          topIndex.add(size - 2);
      }
  }
 
  // Push a value onto a specified stack
  public void push(int stackNum, T val) {
     
    // If the stack is full, expand it
    if (isFull(stackNum))
        Expand(stackNum);
 
    // Add the value to the ArrayList at the index 
    // specified by the topIndex of the specified stack
    values.add(topIndex.get(stackNum), val);
     
    // Increment the topIndex of the specified stack
    topIndex.set(stackNum, topIndex.get(stackNum) + 1);
  }
 
  // Pop a value off a specified stack
  public T pop(int stackNum) {
     
    // If the stack is empty, throw an exception
    if (empty(stackNum))
        throw new RuntimeException("Empty Stack!");
 
    // Get the value at the top of the specified stack
    T val = values.get(topIndex.get(stackNum) - 1);
     
    // Set the value at the top of the specified stack to null
    values.set(topIndex.get(stackNum) - 1, null);
     
    // Decrement the topIndex of the specified stack
    topIndex.set(stackNum, topIndex.get(stackNum) - 1);
 
    // Shrink the specified stack if necessary
    shrink(stackNum);
 
    // Return the value at the top of the specified stack
    return val;
 
  }
 
  // Returns the element at the top of the specified stack
  public T top(int stackNum) {
     
    if (empty(stackNum))
        throw new RuntimeException("Empty Stack!");
     
    return values.get(topIndex.get(stackNum) - 1);
  }
 
  // Returns the number of elements in the specified stack
  public int size(int stackNum) {
     
  if (stackNum == 0)
      return topIndex.get(0);
     
  return topIndex.get(stackNum) - sizes.get(stackNum - 1);
  }
 
  // Checks if the specified stack is empty
  public boolean empty(int stackNum) {
     
    int offset;
     
    if (stackNum == 0)
        offset = 0;
    else
        offset = sizes.get(stackNum - 1);
     
    int index = topIndex.get(stackNum);
    return index == offset;
  }
 
  // Checks if the specified stack is full
  public boolean isFull(int stackNum) {
     
    int offset = sizes.get(stackNum);
    int index = topIndex.get(stackNum);
    return index >= offset;
  }
 
 
  public void Expand(int stackNum) {
      int reserved_size = size(stackNum);
 
      for (int i = stackNum + 1; i < numberOfStacks; i++) {
          sizes.set(i, sizes.get(i) + reserved_size);
          topIndex.set(i, topIndex.get(i) + reserved_size);
      }
 
      sizes.set(stackNum, sizes.get(stackNum) + reserved_size);
 
      for (int i = 0; i < reserved_size; i++)
          values.add(topIndex.get(stackNum), null);
  }
 
  // Function to shrink the reserved size
  // of a stack (divide by2)
  void shrink(int stackNum) {
 
      // Get the reserved size and the current size
      int reserved_size, current_size;
      if (stackNum == 0) {
        reserved_size = sizes.get(0);
        current_size = topIndex.get(0);
      } else {
 
          reserved_size = sizes.get(stackNum) - sizes.get(stackNum - 1);
          current_size = topIndex.get(stackNum) - sizes.get(stackNum - 1);
      }
 
      // Shrink only if the size is
      // lower than a quarter of the
      // reserved size and avoid shrinking
      // if the reserved size is 2
      if (current_size * 4 > reserved_size || reserved_size == 2) {
          return;
      }
 
      // Divide the size by 2 and update
      // the prefix sums (sizes) and
      // the top index of the next stacks
      int dif = reserved_size / 2;
      for (int i = stackNum + 1; i < numberOfStacks; i++) {
        sizes.set(i, sizes.get(i) - dif);
        topIndex.set(i, topIndex.get(i) - dif);
      }
      sizes.set(stackNum, sizes.get(stackNum) - dif);
 
      // Erase half of the reserved size
      values.subList(topIndex.get(stackNum), topIndex.get(stackNum) + dif).clear();
  }
 
  // Driver code
  public static void main(String[] args) {
     
  // create 3 stacks
  MultiStack<Integer> MStack = new MultiStack<>(3);
     
  // push elements in stack 0:
  MStack.push(0, 21);
  MStack.push(0, 13);
  MStack.push(0, 14);
 
  // Push one element in stack 1:
  MStack.push(1, 15);
 
  // Push two elements in stack 2:
  MStack.push(2, 1);
  MStack.push(2, 2);
  MStack.push(2, 3);
 
  // Print the top elements of the stacks
  System.out.println(MStack.top(0));
  System.out.println(MStack.top(1));
  System.out.println(MStack.top(2));
  }
};
 
// This code is contributed by amit_mangal_

Python3

# Python3 implementation for the above approach
class MultiStack:
   
      def __init__(self, k=1):
       
        # Initializes the MultiStack with k number of stacks.
        self.number_of_stacks = k
         
        # Initializes an array to hold values of all stacks.
        self.values = [None] * (self.number_of_stacks * 2)
         
        # Initializes an array to hold sizes of all stacks.
        self.sizes = [2 + i*2 for i in range(self.number_of_stacks)]
         
        # Initializes an array to hold the top index of each stack.
        self.top_index = [size-2 for size in self.sizes]
 
      def push(self, stack_num, val):
 
          # Pushes a value onto the given stack_num.
          # If the stack is full, expands the stack.
          if self.is_full(stack_num):
              self.expand(stack_num)
 
          self.values[self.top_index[stack_num]] = val
          self.top_index[stack_num] += 1
 
      def pop(self, stack_num):
 
          # Pops the top value off of the given stack_num.
          # If the stack is empty, raises an exception.
          if self.is_empty(stack_num):
              raise Exception("Empty Stack!")
 
          val = self.values[self.top_index[stack_num]-1]
 
          self.values[self.top_index[stack_num]-1] = None
          self.top_index[stack_num] -= 1
          self.shrink(stack_num)
 
          return val
 
      def top(self, stack_num):
 
          # Check if the stack is empty
          if self.is_empty(stack_num):
              raise Exception("Empty Stack!")
 
          # Return the top element of the stack
          return self.values[self.top_index[stack_num]-1]
 
      def size(self, stack_num):
          # If no stack_num specified, return the 
          # total number of elements in all stacks
          if not stack_num:
              return self.top_index[0]
 
          # Calculate the number of elements in the specified stack
          return self.top_index[stack_num] - self.sizes[stack_num-1]
 
      def is_empty(self, stack_num):
 
          # Calculate the index offset for the specified stack
          if not stack_num:
              offset = 0
          else:
              offset = self.sizes[stack_num-1]
 
          # Check if the stack is empty
          index = self.top_index[stack_num]
 
          return index == offset
 
      def is_full(self, stack_num):
 
          # Calculate the index offset for the specified stack
          offset = self.sizes[stack_num]
 
          # Check if the stack is full
          index = self.top_index[stack_num]
 
          return index >= offset
 
      # This method expands a stack by copying its elements 
      # to the next stack(s) and increasing its size
      def expand(self, stack_num):
 
          # Get the reserved size of the stack
          reserved_size = self.size(stack_num)
 
          # Increase the size and top index of all the 
          # stacks after the current stack
          for i in range(stack_num+1, self.number_of_stacks):
              self.sizes[i] += reserved_size
              self.top_index[i] += reserved_size
 
          # Increase the size of the current stack
          self.sizes[stack_num] += reserved_size
 
          # Insert reserved_size None values at the 
          # top of the current stack to expand it
          self.values = (self.values[:self.top_index[stack_num]] +
                         [None] * reserved_size +
                         self.values[self.top_index[stack_num]:])
 
      # This method shrinks a stack by reducing its size 
      # and copying its elements to the next stack(s)
      def shrink(self, stack_num):
 
          # Get the reserved size and current size of the stack
          if not stack_num:
              reserved_size, current_size = self.sizes[0], self.top_index[0]
          else:
              reserved_size = self.sizes[stack_num] - self.sizes[stack_num-1]
              current_size = self.top_index[stack_num] - self.sizes[stack_num-1]
 
          # Check if the stack should be shrunk
          if current_size * 4 > reserved_size or reserved_size == 2:
              return
 
          # Calculate the difference to reduce the stack size
          dif = reserved_size // 2
 
          # Reduce the size and top index of all the stacks after the current stack
          for i in range(stack_num+1, self.number_of_stacks):
              self.sizes[i] -= dif
              self.top_index[i] -= dif
 
          # Reduce the size of the current stack
          self.sizes[stack_num] -= dif
 
          # Remove dif elements from the top of the current stack to shrink it
          self.values = (self.values[:self.top_index[stack_num]-dif] +
                         self.values[self.top_index[stack_num]:])
 
# create 3 stacks
MStack = MultiStack(3)
 
# push elements in stack 0:
MStack.push(0, 21)
MStack.push(0, 13)
MStack.push(0, 14)
 
# Push one element in stack 1:
MStack.push(1, 15)
 
# Push two elements in stack 2:
MStack.push(2, 1)
MStack.push(2, 2)
MStack.push(2, 3)
 
# Print the top elements of the stacks
print(MStack.top(0))
print(MStack.top(1))
print(MStack.top(2))
 
# This code is contributed by amit_mangal_

C#

using System;
using System.Collections.Generic;
 
public class MultiStack<T> {
    private int numberOfStacks; // Number of stacks in the
                                // MultiStack
    private List<T> values; // List to store all the values
                            // of the stacks
    private List<int>
        sizes; // List to store the sizes of each stack
    private List<int> topIndexes; // List to store the top
                                  // indexes of each stack
 
    // Constructor to create a MultiStack with 'k' stacks
    // (default is 1)
    public MultiStack(int k = 1)
    {
        numberOfStacks = k;
        values = new List<T>();
        sizes = new List<int>(new int[k]);
        topIndexes = new List<int>(new int[k]);
    }
 
    // Push a value onto a specific stack
    public void Push(int stackNum, T val)
    {
        if (stackNum < 0 || stackNum >= numberOfStacks) {
            throw new ArgumentOutOfRangeException(
                "Invalid stack number");
        }
 
        // Add the value to the main list
        values.Add(val);
 
        // Increase the size of the stack
        sizes[stackNum]++;
 
        // Update the top index for this stack
        topIndexes[stackNum] = values.Count - 1;
    }
 
    // Pop a value from a specific stack
    public T Pop(int stackNum)
    {
        if (stackNum < 0 || stackNum >= numberOfStacks) {
            throw new ArgumentOutOfRangeException(
                "Invalid stack number");
        }
 
        if (IsEmpty(stackNum)) {
            throw new InvalidOperationException(
                "Stack is empty");
        }
 
        // Get the index of the top element of the stack
        int index = topIndexes[stackNum];
 
        // Get the value at this index
        T val = values[index];
 
        // Remove the value from the main list
        values.RemoveAt(index);
 
        // Decrease the size of the stack
        sizes[stackNum]--;
 
        // Update top indexes for the remaining stacks
        UpdateTopIndexes(stackNum, index);
 
        // Return the popped value
        return val;
    }
 
    // Get the top value of a specific stack
    public T Top(int stackNum)
    {
        if (stackNum < 0 || stackNum >= numberOfStacks) {
            throw new ArgumentOutOfRangeException(
                "Invalid stack number");
        }
 
        if (IsEmpty(stackNum)) {
            throw new InvalidOperationException(
                "Stack is empty");
        }
 
        // Return the value at the top index of this stack
        return values[topIndexes[stackNum]];
    }
 
    // Get the size of a specific stack
    public int Size(int stackNum)
    {
        if (stackNum < 0 || stackNum >= numberOfStacks) {
            throw new ArgumentOutOfRangeException(
                "Invalid stack number");
        }
 
        // Return the size of this stack
        return sizes[stackNum];
    }
 
    // Check if a specific stack is empty
    public bool IsEmpty(int stackNum)
    {
        if (stackNum < 0 || stackNum >= numberOfStacks) {
            throw new ArgumentOutOfRangeException(
                "Invalid stack number");
        }
 
        // Check if the size of this stack is 0
        return sizes[stackNum] == 0;
    }
 
    // Update the top indexes of stacks after a pop
    // operation
    private void UpdateTopIndexes(int stackNum,
                                  int removedIndex)
    {
        for (int i = stackNum; i < numberOfStacks; i++) {
            // Decrement the top index if it's greater than
            // the removed index
            if (topIndexes[i] > removedIndex) {
                topIndexes[i]--;
            }
        }
    }
}
 
class Program {
    static void Main()
    {
        // Create an instance of MultiStack with 3 stacks
        MultiStack<int> MStack = new MultiStack<int>(3);
 
        // Push elements into different stacks
        MStack.Push(0, 21);
        MStack.Push(0, 13);
        MStack.Push(0, 14);
 
        MStack.Push(1, 15);
 
        MStack.Push(2, 1);
        MStack.Push(2, 2);
        MStack.Push(2, 3);
 
        // Print the tops of each stack
        Console.WriteLine("Top of Stack 0: "
                          + MStack.Top(0));
        Console.WriteLine("Top of Stack 1: "
                          + MStack.Top(1));
        Console.WriteLine("Top of Stack 2: "
                          + MStack.Top(2));
    }
}

Output

14
15
3

Time complexities:

O(1) for top() function.
Amortized O(1) for push() and pop() functions.

Auxiliary Space: O(N) where N is the number of stacks

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!