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 multistackclass 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 codeint 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 approachimport 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 approachclass 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 stacksMStack = 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 stacksprint(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
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
