This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is the interview question 03.01 on LeetCode.

Triad. Describes how to implement three stacks using only one array.

You should implement push(stackNum, Value), pop(stackNum), isEmpty(stackNum), peek(stackNum) methods.

StackNum represents the stack subscript and value represents the value pushed in.

The constructor passes in a stackSize argument that represents the size of each stack.

Example 1:

Input: [" TripleInOne ", "push" and "push" and "pop", "pop", "pop", "isEmpty"] [[1], [0, 1], [0, 2], [0], [0], [0], [0]] output: [NULL, null, NULL, 1, -1, -1, true] Description: pop, peek returns -1 when the stack is empty, and push does not push elements when the stack is full.Copy the code

Example 2:

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]Copy the code

Two dimensional array solution

We are only asked to use “an array” to implement the stack, and there is no restriction on the dimensions of the array.

So a simple way to do this is to create a two-dimensional array called datadatadata.

A two-dimensional array of each line represents a stack, at the same time the use of a locationslocationslocations record each subscript stack “insert”.

Code:

class TripleInOne {
    int N = 3;
    // An array of 3 * n, each row representing a stack
    int[][] data; 
    // Record the "insert" position of each stack
    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; }}Copy the code
  • Time complexity: All operations are O(1)O(1)O(1).
  • Space complexity: O(k∗n)O(K * n)O(K ∗n). K is the number of stacks we need to implement, and n is the stack capacity.

One-dimensional array solution

Of course, we could do it with a one-dimensional array.

A length of 3 ∗ stackSize3 * stackSize3 ∗ stackSize array, and the three stacks of “insert” stored in locationslocationslocations array.

Code:

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) {
        returnlocations[stackNum] == stackNum * size; }}Copy the code
  • Time complexity: All operations are O(1)O(1)O(1).
  • Space complexity: O(k∗n)O(K * n)O(K ∗n). K is the number of stacks we need to implement, and n is the stack capacity.

The last

This is the No.* of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.