Three Stacks Using One Array | Amazon Interview Question

Anonymous User

872

Write code to implement 3 stacks using a single static array.
You cannot use a Stack or an array of arrays.

TripleStack tripleStack = new TripleStack();
// push(stackId, value)
tripleStack.push(1, 50); 
tripleStack.push(2, 100);
tripleStack.push(1, 100); 
tripleStack.push(3, 150);
// peek(stackId)
tripleStack.peek(1);  // returns 100 
tripleStack.peek(2);  // returns 100
tripleStack.peek(3); // returns 150
// pop(stackId)
tripleStack.pop(1); // returns 100 
tripleStack.pop(1); // returns 50
tripleStack.pop(2); // returns 100
tripleStack.pop(3); // returns 150

Here's a solution to implement three stacks using a single static array without using a Stack or an array of arrays. The key idea is to divide the array into three parts and simulate the behavior of three stacks within that single array.

Approach:

- Use a single static array to store elements for all three stacks.
- Maintain three different top pointers to manage each of the stacks.
- Each stack will have its own segment of the array to grow into.

Code Implementation:

class TripleStack:
    def __init__(self, stack_size=100):
        self.stack_size = stack_size
        self.stack_array = [0] * (stack_size * 3)  # Static array to hold all 3 stacks
        self.stack_tops = [-1, -1, -1]  # Top pointers for all 3 stacks (initially -1)

    def push(self, stack_id, value):
        if stack_id < 1 or stack_id > 3:
            raise IndexError("Stack ID must be between 1 and 3.")
        
        # Determine the index in the static array where the next element will go
        stack_num = stack_id - 1
        if self.stack_tops[stack_num] >= self.stack_size - 1:
            raise OverflowError(f"Stack {stack_id} is full.")
        
        # Increment the top pointer for the selected stack and place the value
        self.stack_tops[stack_num] += 1
        self.stack_array[self.stack_size * stack_num + self.stack_tops[stack_num]] = value

    def pop(self, stack_id):
        if stack_id < 1 or stack_id > 3:
            raise IndexError("Stack ID must be between 1 and 3.")
        
        stack_num = stack_id - 1
        if self.stack_tops[stack_num] == -1:
            raise IndexError(f"Stack {stack_id} is empty.")
        
        # Retrieve the top value and decrement the top pointer
        value = self.stack_array[self.stack_size * stack_num + self.stack_tops[stack_num]]
        self.stack_tops[stack_num] -= 1
        return value

    def peek(self, stack_id):
        if stack_id < 1 or stack_id > 3:
            raise IndexError("Stack ID must be between 1 and 3.")
        
        stack_num = stack_id - 1
        if self.stack_tops[stack_num] == -1:
            raise IndexError(f"Stack {stack_id} is empty.")
        
        # Return the top value without modifying the stack
        return self.stack_array[self.stack_size * stack_num + self.stack_tops[stack_num]]

    def is_empty(self, stack_id):
        if stack_id < 1 or stack_id > 3:
            raise IndexError("Stack ID must be between 1 and 3.")
        
        stack_num = stack_id - 1
        return self.stack_ttops[stack_num] == -1


# Example Usage:
tripleStack = TripleStack()

tripleStack.push(1, 50) 
tripleStack.push(2, 100)
tripleStack.push(1, 100) 
tripleStack.push(3, 150)

print(tripleStack.peek(1))  # 100
print(tripleStack.peek(2))  # 100
print(tripleStack.peek(3))  # 150

print(tripleStack.pop(1))  # 100
print(tripleStack.pop(1))  # 50
print(tripleStack.pop(2))  # 100
print(tripleStack.pop(3))  # 150

Explanation:

Array Structure: The stack_array is a flat list, but logically it’s split into three segments for the three stacks. Each stack has a fixed size of stack_size.
Stack Pointers: stack_tops keeps track of the top index for each stack. Initially, all stack tops are -1, indicating they are empty.
Index Calculation: When pushing or popping an element from a stack, we calculate the correct index in the flat array using the formula self.stack_size * stack_num + self.stack_tops[stack_num], where stack_num is stack_id - 1.
Error Handling: The code checks for overflows (when a stack is full) and underflows (when trying to pop or peek from an empty stack).

Time Complexity:

Push, Pop, Peek: Each of these operations runs in constant time (O(1)) because they involve simple arithmetic operations on the array and stack pointers.
Space Complexity: The space complexity is (O(n)), where (n) is the size of the entire static array allocated to hold elements for the three stacks.

Comments (2)