Lecture 156:- N Stacks In An Array

Implementing multiple stacks in a single array is a common problem. This can be achieved by dividing the array into segments, where each segment represents a separate stack. You need to keep track of the top of each stack within the array.

Here's an example implementation of N stacks in a single array using C++:

cppCopy code

#include <iostream> #include <vector> class NStacks { private: int n; // Number of stacks int capacity; // Total capacity of the array std::vector<int> data; // Array to store elements std::vector<int> tops; // Array to store top indices of stacks public: NStacks(int numStacks, int totalCapacity) : n(numStacks), capacity(totalCapacity) { data.resize(capacity); tops.resize(n, -1); // Initialize top indices to -1 (empty stacks) } bool isFull(int stackIndex) const { return tops[stackIndex] == capacity / n - 1; } bool isEmpty(int stackIndex) const { return tops[stackIndex] == -1; } void push(int stackIndex, int value) { if (isFull(stackIndex)) { std::cout << "Stack " << stackIndex << " is full. Cannot push " << value << std::endl; return; } tops[stackIndex]++; data[stackIndex * (capacity / n) + tops[stackIndex]] = value; } int pop(int stackIndex) { if (isEmpty(stackIndex)) { std::cout << "Stack " << stackIndex << " is empty." << std::endl; return -1; // Return a special value to indicate underflow } int value = data[stackIndex * (capacity / n) + tops[stackIndex]]; tops[stackIndex]--; return value; } int peek(int stackIndex) const { if (isEmpty(stackIndex)) { std::cout << "Stack " << stackIndex << " is empty." << std::endl; return -1; // Return a special value to indicate underflow } return data[stackIndex * (capacity / n) + tops[stackIndex]]; } }; int main() { NStacks stacks(3, 9); stacks.push(0, 1); stacks.push(1, 2); stacks.push(2, 3); stacks.push(0, 4); stacks.push(1, 5); std::cout << "Peek Stack 0: " << stacks.peek(0) << std::endl; std::cout << "Peek Stack 1: " << stacks.peek(1) << std::endl; std::cout << "Peek Stack 2: " << stacks.peek(2) << std::endl; std::cout << "Popping elements from Stack 0: "; while (!stacks.isEmpty(0)) { std::cout << stacks.pop(0) << " "; } std::cout << std::endl; return 0; }

In this implementation, the NStacks class allows you to create and manage multiple stacks within a single array. You can customize the number of stacks and the total capacity of the array based on your requirements. The isFull, isEmpty, push, pop, and peek methods provide the basic stack operations for each stack.

Please note that this implementation uses a linear array divided into segments for each stack. There are other approaches that use a more flexible allocation strategy if the sizes of the stacks are not fixed.