完整题目描述

题目： 用一个数组实现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

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

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

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

码小课网站中有更多相关内容分享给大家学习，包括算法解析、数据结构详解以及实战项目经验分享，欢迎大家访问学习。