03.01. Three in One

Description

Describe how you could use a single array to implement three stacks.

Yout should implement push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum) methods. stackNum is the index of the stack. value is the value that pushed to the stack.

The constructor requires a stackSize parameter, which represents the size of each stack.

Example1:


 Input:

["TripleInOne", "push", "push", "pop", "pop", "pop", "isEmpty"]

[[1], [0, 1], [0, 2], [0], [0], [0], [0]]

 Output:

[null, null, null, 1, -1, -1, true]

Explanation: When the stack is empty, `pop, peek` return -1. When the stack is full, `push` does nothing.

Example2:


 Input:

["TripleInOne", "push", "push", "push", "pop", "pop", "pop", "peek"]

[[2], [0, 1], [0, 2], [0, 3], [0], [0], [0], [0]]

 Output:

[null, null, null, null, 2, 1, -1, -1]

Solutions

Solution 1: Array Simulation

We use a variable $cap$ to represent the size of each stack, and use an array $stk$ of length $3 \times \textit{cap} + 3$ to simulate three stacks. The first $3 \times \textit{cap}$ elements of the array are used to store the elements of the stack, and the last three elements are used to store the number of elements in each stack.

For the push operation, we first check whether the stack is full. If it is not full, we push the element into the stack and update the number of elements in the stack.

For the pop operation, we first check whether the stack is empty. If it is not empty, we update the number of elements in the stack and return the top element of the stack.

For the peek operation, we first check whether the stack is empty. If it is not empty, we return the top element of the stack.

For the isEmpty operation, we directly check whether the stack is empty. For stack $i$, we only need to check whether $stk[\textit{cap} \times 3 + i]$ is $0$.

In terms of time complexity, the time complexity of each operation is $O(1)$. The space complexity is $O(\textit{cap})$, where $\textit{cap}$ is the size of the stack.