当前位置： 面试刷题>> 用一个数组实现3个栈 (经典算法题500道)
### 完整题目描述
**题目**： 用一个数组实现3个栈（Stack in One Array）
**题目要求**：
设计一个数据结构，使用单个数组来模拟实现三个栈的功能。这三个栈应该独立工作，即每个栈的push和pop操作应当互不干扰。要求提供实现这个数据结构的类，并至少实现以下功能：
1. `push(stackNum, value)`：向编号为`stackNum`的栈中添加一个元素`value`。栈编号从0到2，共有3个栈。
2. `pop(stackNum)`：从编号为`stackNum`的栈中移除栈顶元素，并返回该元素。如果栈为空，则返回特定的错误值（如`null`或`-1`等，具体取决于实现）。
3. `isEmpty(stackNum)`：检查编号为`stackNum`的栈是否为空。
**注意**：
- 使用单个数组来存储所有栈的元素，并且需要高效地管理每个栈的边界，以确保每个栈的独立性。
- 你可以假设栈的操作是合法的，即不会进行如向空栈中pop等非法操作。
### 示例代码
#### PHP
```php
class ThreeStacksInOneArray {
private $array;
private $top;
private $stackSizes = [0, 0, 0];
public function __construct() {
$this->array = [];
$this->top = -1;
}
public function push($stackNum, $value) {
if ($stackNum < 0 || $stackNum > 2) {
throw new Exception("Invalid stack number");
}
$this->top++;
$this->array[$this->top] = $value;
$this->stackSizes[$stackNum]++;
}
public function pop($stackNum) {
if ($stackNum < 0 || $stackNum > 2 || $this->stackSizes[$stackNum] == 0) {
return null; // 假设返回null表示栈空
}
$popValue = $this->array[$this->top - $this->stackSizes[$stackNum] + 1];
$this->stackSizes[$stackNum]--;
// 不实际移除元素以节省空间，但逻辑上视为已移除
return $popValue;
}
public function isEmpty($stackNum) {
return $this->stackSizes[$stackNum] == 0;
}
}
// 使用示例
$stacks = new ThreeStacksInOneArray();
$stacks->push(0, 1);
$stacks->push(1, 2);
$stacks->push(2, 3);
echo $stacks->pop(1); // 输出: 2
echo $stacks->isEmpty(0) ? "true" : "false"; // 输出: false
```
#### Python
```python
class ThreeStacksInOneArray:
def __init__(self):
self.array = []
self.stack_sizes = [0, 0, 0]
def push(self, stack_num, value):
if not 0 <= stack_num <= 2:
raise Exception("Invalid stack number")
self.array.append(value)
self.stack_sizes[stack_num] += 1
def pop(self, stack_num):
if not 0 <= stack_num <= 2 or self.stack_sizes[stack_num] == 0:
return None # 假设返回None表示栈空
pop_index = len(self.array) - self.stack_sizes[stack_num]
pop_value = self.array.pop(pop_index)
self.stack_sizes[stack_num] -= 1
return pop_value
def is_empty(self, stack_num):
return self.stack_sizes[stack_num] == 0
# 使用示例
stacks = ThreeStacksInOneArray()
stacks.push(0, 1)
stacks.push(1, 2)
stacks.push(2, 3)
print(stacks.pop(1)) # 输出: 2
print(stacks.is_empty(0)) # 输出: False
```
#### JavaScript
```javascript
class ThreeStacksInOneArray {
constructor() {
this.array = [];
this.stackSizes = [0, 0, 0];
}
push(stackNum, value) {
if (stackNum < 0 || stackNum > 2) {
throw new Error("Invalid stack number");
}
this.array.push(value);
this.stackSizes[stackNum]++;
}
pop(stackNum) {
if (stackNum < 0 || stackNum > 2 || this.stackSizes[stackNum] === 0) {
return null; // 假设返回null表示栈空
}
const popIndex = this.array.length - this.stackSizes[stackNum];
const popValue = this.array.splice(popIndex, 1)[0];
this.stackSizes[stackNum]--;
return popValue;
}
isEmpty(stackNum) {
return this.stackSizes[stackNum] === 0;
}
}
// 使用示例
const stacks = new ThreeStacksInOneArray();
stacks.push(0, 1);
stacks.push(1, 2);
stacks.push(2, 3);
console.log(stacks.pop(1)); // 输出: 2
console.log(stacks.isEmpty(0)); // 输出: false
```
**码小课网站中有更多相关内容分享给大家学习**，包括算法解析、数据结构详解以及实战项目经验分享，欢迎大家访问学习。