面试题 03.01

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

1. straight forward

class TripleInOne {
public:
    vector<int> nums;
    int indexes[3] = {0, 1, 2};
    TripleInOne(int stackSize) : nums(stackSize * 3) {
    }

    void push(int stackNum, int value) {
        if (indexes[stackNum] < nums.size()) {
            nums[indexes[stackNum]] = value;
            indexes[stackNum] += 3;
        }
    }

    int pop(int stackNum) {
        if (!isEmpty(stackNum)) {
            indexes[stackNum] -= 3;
            return nums[indexes[stackNum]];
        }
        else
            return -1;
    }

    int peek(int stackNum) {
        if (!isEmpty(stackNum)) {
            return nums[indexes[stackNum] - 3];
        }
        else
            return -1;
    }

    bool isEmpty(int stackNum) {
        return indexes[stackNum] < 3;
    }
};

/**
 * Your TripleInOne object will be instantiated and called as such:
 * TripleInOne* obj = new TripleInOne(stackSize);
 * obj->push(stackNum,value);
 * int param_2 = obj->pop(stackNum);
 * int param_3 = obj->peek(stackNum);
 * bool param_4 = obj->isEmpty(stackNum);
 */