面试金典0301 三合一

题目：

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

  你应该实现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]
  
  # 提示：
  0 <= stackNum <= 2

解题方法：

1. 模拟：用数组模拟栈的后进先出(LIFO)的模式，用一个大小为3的数组作为指针来记录每个栈顶的位置（注意这里栈顶指的是存储元素的后一位）

   • 时间复杂度\(O(n)\)，n为输入指令数量
   • 额外的空间复杂度为\(O(stackSize)\)，stackSize为一个栈的大小

解法一：模拟

• vector可以一开始初始定长的，然后用下标去访问即可，当作定长数组来用
• 栈的边界处理技巧：将栈顶的指针指向顶部元素的再往上一个元素，方便处理边界条件

class TripleInOne {
private:
    vector<int> Nstacks; // 用vector来模拟栈
    int stacksize = 0; // 记录栈的大小
    int stacktop[3] = {0, 0, 0}; // 记录栈顶元素的后一位的地址
public:
    TripleInOne(int stackSize) {
        stacksize = stackSize;
        Nstacks = vector<int>(stacksize*3, 0);
        stacktop[1] = stacksize;
        stacktop[2] = stacksize*2;
    }
    
    void push(int stackNum, int value) {
        if(stacktop[stackNum] < stacksize*(stackNum+1))
        {
            Nstacks[stacktop[stackNum]++] = value; // 难点就在于判断边界条件以及top指针的变化
        }
    }
    
    int pop(int stackNum) {
        int rst = -1;
        if(stacktop[stackNum] > stacksize*(stackNum))
        {
            rst = Nstacks[--stacktop[stackNum]]; // 弹出时应返回top所指的上一位，并且top移动到这里
        }
        return rst;
    }
    
    int peek(int stackNum) {
        int rst = -1;
        if(stacktop[stackNum] > stacksize*(stackNum))
        {
            rst = Nstacks[stacktop[stackNum]-1]; // peek时应返回top所指的上一位，但top所指位置不变
        }
        return rst;

    }
    
    bool isEmpty(int stackNum) {
        return stacktop[stackNum] == stacksize*stackNum;
    }
};

/**
 * 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);
 */