【设计数据结构】使用一个数组实现三个栈

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

这是 LeetCode 上的面试题 03.01. 三合一，难度为 Easy。

三合一。描述如何只用一个数组来实现三个栈。

你应该实现 push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum) 方法。

stackNum表示栈下标，value表示压入的值。

构造函数会传入一个stackSize参数，代表每个栈的大小。

示例1:

输入：
["TripleInOne", "push", "push", "pop", "pop", "pop", "isEmpty"]
[[1], [0, 1], [0, 2], [0], [0], [0], [0]]

输出：
[null, null, null, 1, -1, -1, true]
说明：当栈为空时`pop, peek`返回-1，当栈满时`push`不压入元素。
复制代码

示例2:

输入：
["TripleInOne", "push", "push", "push", "pop", "pop", "pop", "peek"]
[[2], [0, 1], [0, 2], [0, 3], [0], [0], [0], [0]]

输出：
[null, null, null, null, 2, 1, -1, -1]
复制代码

二维数组解法

题目只要求我们使用「一个数组」来实现栈，并没有限制我们使用数组的维度。

因此一个简单的做法是，建立一个二维数组 $data$ 来做。

二维数组的每一行代表一个栈，同时使用一个 $locations$ 记录每个栈「待插入」的下标。

代码：

class TripleInOne {
    int N = 3;
    // 3 * n 的数组，每一行代表一个栈
    int[][] data; 
    // 记录每个栈「待插入」位置
    int[] locations; 

    public TripleInOne(int stackSize) {
        data = new int[N][stackSize];
        locations = new int[N];
    }
    
    public void push(int stackNum, int value) {
        int[] stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc < stk.length) {
            stk[loc] = value;
            locations[stackNum]++;
        }
    }
    
    public int pop(int stackNum) {
        int[] stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc > 0) {
            int val = stk[loc - 1];
            locations[stackNum]--;
            return val;
        } else {
            return -1;
        }
    }
    
    public int peek(int stackNum) {
        int[] stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc > 0) {
            return stk[loc - 1];
        } else {
            return -1;
        }
    }
    
    public boolean isEmpty(int stackNum) {
        return locations[stackNum] == 0;
    }
}
复制代码

时间复杂度：所有的操作均为 $O(1)$ 。
空间复杂度： $O(k * n)$ 。k 为我们需要实现的栈的个数，n 为栈的容量。

一维数组解法

当然了，我们也能使用一个一维数组来做。

建立一个长度为 $3 * stackSize$ 的数组，并将 3 个栈的「待插入」存储在 $locations$ 数组。

代码：

class TripleInOne {
    int N = 3;
    int[] data;
    int[] locations;
    int size;
    public TripleInOne(int stackSize) {
        size = stackSize;
        data = new int[size * N];
        locations = new int[N];
        for (int i = 0; i < N; i++) {
            locations[i] = i * size;
        }
    }
    
    public void push(int stackNum, int value) {
        int idx = locations[stackNum];
        if (idx < (stackNum + 1) * size) {
            data[idx] = value;
            locations[stackNum]++;
        }
    }
    
    public int pop(int stackNum) {
        int idx = locations[stackNum];
        if (idx > stackNum * size) {
            locations[stackNum]--;
            return data[idx - 1];
        } else {
            return -1;
        }
    }
    
    public int peek(int stackNum) {
        int idx = locations[stackNum];
        if (idx > stackNum * size) {
            return data[idx - 1];
        } else {
            return -1;
        }
    }
    
    public boolean isEmpty(int stackNum) {
        return locations[stackNum] == stackNum * size;
    }
}
复制代码