N Stacks In An Array in Java
Implementing N stacks in an array involves using a single array to represent multiple stacks. Each stack has its own section of the array, with elements pushed and popped according to stack-specific rules.
Example:
Input:
2 6 3 1 15 1 1 25 2 2 1
Output:
True True 15
Explanation:
Number of stacks: 2
Size of the array: 6
Number of operations: 3
Push 15 into the 1st stack: Returns “True”
Push 25 into the 2nd stack: Returns “True”
Pop from the 1st stack: Returns “15”
Approach: Fixed Division Method
Algorithm
Step 1: Divide the array into equal sections, one for each stack.
Step 2: Track the top index for each stack using an auxiliary array.
Step 3: Check if the stack is within range and has space.
Step 4: Increment the top index.
Step 5: Place the element at the appropriate position in the array.
Step 6: Check if the stack is within range and not empty.
Step 7: Retrieve the top element.
Step 8: Decrement the top index.
FileName: NStacksArray.java
class FixedDivisionNStacks { private int[] array; // Array to store stack elements private int[] top; // Array to store the top index of each stack private int stackSize; // Size of each stack private int numberOfStacks; // Number of stacks // Constructor to initialize the stacks public FixedDivisionNStacks(int numberOfStacks, int stackSize) { this.numberOfStacks = numberOfStacks; this.stackSize = stackSize; array = new int[numberOfStacks * stackSize]; top = new int[numberOfStacks]; for (int i = 0; i < numberOfStacks; i++) { top[i] = -1; } } // Method to push an element onto a stack public boolean push(int stackNumber, int value) { if (stackNumber < 0 || stackNumber >= numberOfStacks || top[stackNumber] + 1 >= stackSize) { return false; } top[stackNumber]++; // Increment the top index for the stack array[stackNumber * stackSize + top[stackNumber]] = value; return true; } // Method to pop an element from a stack public int pop(int stackNumber) { if (stackNumber < 0 || stackNumber >= numberOfStacks || top[stackNumber] == -1) { throw new IllegalStateException("Stack is empty"); // Throw an exception if the stack is empty } int value = array[stackNumber * stackSize + top[stackNumber]]; // Retrieve the value top[stackNumber]--; return value; } } public class NStacksArray { public static void main(String[] args) { FixedDivisionNStacks stacks = new FixedDivisionNStacks(2, 3); // 2 stacks, each of size 3 System.out.println(stacks.push(0, 15)); System.out.println(stacks.push(1, 25)); System.out.println(stacks.pop(0)); } }
Output:
true true 15
Complexity Analysis:
Time Complexity: O(1) for both push and pop operations.
Space Complexity: O(N * S) where N is the number of stacks and S is the stack size.
Approach: Flexible Division with Extra Space
Algorithm
Step 1: Create an array to store stack elements and manage free spaces.
Step 2: Track the top index for each stack.
Step 3: Maintain a next available index list and a free index pointer.
Step 4: Check if there is a free slot.
Step 5: Insert the element at the free index.
Step 6: Update the top index and next available index list.
Step 7: Move the free pointer to the next available slot.
Step 8: Check if the stack is not empty.
Step 9: Retrieve the element at the top index.
Step 10: Update the top index and next available index list.
Step 11: Return the used slot to the free list.
FileName: NStacksArray1.java
class FixedDivisionNStacks { private int[] array; // Array to store stack elements private int[] top; // Array to store the top index of each stack private int stackSize; // Size of each stack private int numberOfStacks; // Number of stacks // Constructor to initialize the stacks public FixedDivisionNStacks(int numberOfStacks, int stackSize) { this.numberOfStacks = numberOfStacks; this.stackSize = stackSize; array = new int[numberOfStacks * stackSize]; top = new int[numberOfStacks]; for (int i = 0; i < numberOfStacks; i++) { top[i] = -1; } } // Method to push an element onto a stack public boolean push(int stackNumber, int value) { if (stackNumber < 0 || stackNumber >= numberOfStacks || top[stackNumber] + 1 >= stackSize) { return false; } top[stackNumber]++; // Increment the top index for the stack array[stackNumber * stackSize + top[stackNumber]] = value; return true; } // Method to pop an element from a stack public int pop(int stackNumber) { if (stackNumber < 0 || stackNumber >= numberOfStacks || top[stackNumber] == -1) { throw new IllegalStateException("Stack is empty"); // Throw an exception if the stack is empty } int value = array[stackNumber * stackSize + top[stackNumber]]; // Retrieve the value top[stackNumber]--; return value; } } public class NStacksArray1{ public static void main(String[] args) { FixedDivisionNStacks stacks = new FixedDivisionNStacks(2, 3); // 2 stacks, each of size 3 System.out.println(stacks.push(0, 15)); System.out.println(stacks.push(1, 25)); System.out.println(stacks.pop(0)); } }
Output:
true true 15
Complexity Analysis:
Time Complexity: O(1) for both push and pop operations.
Space Complexity: O(S + N) where S is the total array size and N is the number of stacks.