Design N-Stack Using a Fixed-Size Array
Implement N independent stacks using one fixed-size array. The stacks must share the available array space efficiently.
Each stack follows last-in, first-out order. Stack numbers are one-based, from 1 through numberOfStacks.
Class Definition
NStack(int numberOfStacks, int capacity)
- Creates
numberOfStacks empty stacks.
- The stacks share a single array that can store at most
capacity values in total.
Method Signatures
Push a Value
boolean push(int value, int stackNumber)
- Pushes
value onto the stack identified by stackNumber.
- Returns
true when the value is added successfully.
- Returns
false when the shared array is full.
Pop a Value
int pop(int stackNumber)
- Removes and returns the top value from the stack identified by
stackNumber.
- Returns
-1 when the selected stack is empty.
Requirements
- All stacks must use the same fixed-size array for storage.
- Empty space left by one stack must remain available to the other stacks.
- Pushing or popping from one stack must not change the order of values in another stack.
- Each stack must preserve last-in, first-out order.
Constraints
1 ≤ numberOfStacks ≤ 100,0001 ≤ capacity ≤ 1,000,0001 ≤ stackNumber ≤ numberOfStacks0 ≤ value ≤ 1,000,000,000- At most
1,000,000 calls will be made to push and pop.
Examples
Example 1
NStack(numberOfStacks = 3, capacity = 5)
push(value = 14, stackNumber = 1) returns true.
push(value = 28, stackNumber = 2) returns true.
push(value = 35, stackNumber = 1) returns true.
pop(stackNumber = 1) returns 35.
pop(stackNumber = 2) returns 28.
Example 2
NStack(numberOfStacks = 2, capacity = 3)
push(value = 7, stackNumber = 1) returns true.
push(value = 9, stackNumber = 2) returns true.
push(value = 11, stackNumber = 2) returns true.
push(value = 13, stackNumber = 1) returns false because the shared array is full.
pop(stackNumber = 2) returns 11.
push(value = 13, stackNumber = 1) now returns true because one array position became available.
Example 3
NStack(numberOfStacks = 4, capacity = 6)
pop(stackNumber = 3) returns -1 because the selected stack is empty.