Open In App

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

Last Updated : 26 Jul, 2025
Suggest changes
Share
4 Likes
Like
Report

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));  } }
JavaScript 
class MultiStack {  constructor(k = 1) {  this.numberOfStacks = k;  this.values = new Array(k * 2).fill(0);  this.sizes = new Array(k).fill(0);  this.topIndex = new Array(k).fill(0);  // Sizes is a prefix sum array  for (let size = 2, i = 0; i < this.numberOfStacks; i++, size += 2) {  this.sizes[i] = size;  this.topIndex[i] = size - 2;  }  }  push(stackNum, val) {  if (this.isFull(stackNum)) {  this.expand(stackNum);  }  this.values[this.topIndex[stackNum]++] = val;  }  pop(stackNum) {  if (this.empty(stackNum)) {  throw new Error("Empty Stack!");  }  const val = this.values[this.topIndex[stackNum] - 1];  this.values[--this.topIndex[stackNum]] = 0;  this.shrink(stackNum);  return val;  }  top(stackNum) {  if (this.empty(stackNum)) {  throw new Error("Empty Stack!");  }  return this.values[this.topIndex[stackNum] - 1];  }  size(stackNum) {  if (!stackNum) {  return this.topIndex[0];  }  return this.topIndex[stackNum] - this.sizes[stackNum - 1];  }  empty(stackNum) {  const offset = !stackNum ? 0 : this.sizes[stackNum - 1];  const index = this.topIndex[stackNum];  return index === offset;  }  isFull(stackNum) {  const offset = this.sizes[stackNum];  const index = this.topIndex[stackNum];  return index >= offset;  }  expand(stackNum) {  const reservedSize = this.size(stackNum);  for (let i = stackNum + 1; i < this.numberOfStacks; i++) {  this.sizes[i] += reservedSize;  this.topIndex[i] += reservedSize;  }  this.sizes[stackNum] += reservedSize;  const reservedArray = new Array(reservedSize).fill(0);  this.values.splice(this.topIndex[stackNum], 0, ...reservedArray);  }  shrink(stackNum) {  let reservedSize, currentSize;  if (!stackNum) {  reservedSize = this.sizes[0];  currentSize = this.topIndex[0];  } else {  reservedSize = this.sizes[stackNum] - this.sizes[stackNum - 1];  currentSize = this.topIndex[stackNum] - this.sizes[stackNum - 1];  }  if (currentSize * 4 > reservedSize || reservedSize === 2) {  return;  }  const difference = reservedSize / 2;  for (let i = stackNum + 1; i < this.numberOfStacks; i++) {  this.sizes[i] -= difference;  this.topIndex[i] -= difference;  }  this.sizes[stackNum] -= difference;  this.values.splice(  this.topIndex[stackNum],  difference,  );  } } // Driver code const MStack = new MultiStack(3); 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); console.log(MStack.top(0)); console.log(MStack.top(1)); console.log(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


D
davidgatea21
Article Tags :

Explore

Lightbox