【CPP】《程序员面试金典》习题(3)——栈和队列

描述如何只用一个数组来实现三个栈。
你应该实现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]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/three-in-one-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public:
    //传统一维数组,74.2%,84ms
    //一维数组实现，采用按照3来划分三个栈，长度是静态的
    //这道题耗时差别很大
    //数组也可以用向量vector来替代，效率接近
    //可以借助循环数组的想法做成大小动态适应的栈，但是代码会复杂很多而且效率也会降低
    int* stack;
    int p[3];
    int stackSize;

    TripleInOne(int stackSize) {
        stack = new int[stackSize * 3];
        this->stackSize = stackSize;
        p[0] = 0;
        p[1] = 1;
        p[2] = 2;
    }

    void push(int stackNum, int value) {
        //栈满时跳出
        if ((p[stackNum] - stackNum + 3) / 3 > stackSize) {
            return;
        }
        stack[p[stackNum]] = value;
        //入栈加数量
        p[stackNum] += 3;
    }

    int pop(int stackNum) {
        //栈空
        if (p[stackNum] - 3 < 0) {
            return -1;
        }
        int ret = stack[p[stackNum] - 3];
        //出栈退数量
        p[stackNum] -= 3;
        return ret;
    }

    int peek(int stackNum) {
        //栈空
        if (p[stackNum] - 3 < 0) {
            return -1;
        }
        return stack[p[stackNum] - 3];
    }

    bool isEmpty(int stackNum) {
        //栈空
        if (p[stackNum] - 3 < 0) {
            return true;
        }
        else {
            return false;
        }
    }

请设计一个栈，除了常规栈支持的pop与push函数以外，
还支持min函数，该函数返回栈元素中的最小值。
执行push、pop和min操作的时间复杂度必须为O(1)。

示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  //使用现有的STL容器vector,6.0%,212ms
  //主要问题是min操作的时间复杂度是O(n)
public:
  MinStack() {
  }

  void push(int x) {
    stack.push_back(x);
  }

  void pop() {
    if (stack.empty()) {
      return;
    }
    stack.pop_back();
  }

  int top() {
    if (stack.empty()) {
      return NULL;
    }
    return stack.back();
  }

  int getMin() {
    //遍历一次栈
    if (stack.empty()) {
      return NULL;
    }
    int min = stack.back();
    for (auto i : stack) {
      if (i < min) {
        min = i;
      }
    }
    return min;
  }

private:
  vector<int> stack;

  //自定义类型使用现有的STL容器vector,93.2%,24ms
  //让每个元素都记录下自己以下的栈的最小值，这样可以在O(1)中得到最小值
public:
  struct StackElement {
    int value;
    //每个子栈的最小值保存在元素内
    int min;
    StackElement(int v, int m) {
      value = v;
      min = m;
    }
  };

  MinStack() {
  }

  void push(int x) {
    if (!stack.empty()) {
      //push时需要判断是否需要更新当前最小值
      if (x <= stack.back()->min) {
        //更新
        stack.push_back(new StackElement(x, x));
      }
      else {
        stack.push_back(new StackElement(x, stack.back()->min));
      }
    }
    else {
      stack.push_back(new StackElement(x, x));
    }

  }

  void pop() {
    if (stack.empty()) {
      return;
    }
    stack.pop_back();
  }

  int top() {
    if (stack.empty()) {
      return NULL;
    }
    return stack.back()->value;
  }

  int getMin() {
    if (stack.empty()) {
      return NULL;
    }
    //可以直接返回最小值
    return stack.back()->min;
  }

private:
  //注意new得到的是指针，所以为了vector方便也只存放指针
  vector<StackElement*> stack;

  //将最小值栈划分开来且直接使用容器stack，93.2%,24ms
  //将最小值用一个另外的栈来保存，节省点内存也避免了新数据结构的定义
public:
  stack<int> s;
  stack<int> buf;//最小值栈

  MinStack() {
    buf.push(INT_MAX);
  }

  void push(int x) {
    //压入时要注意是否需要刷新
    if (x <= buf.top()) {
      buf.push(x);
    }
    s.push(x);
  }

  void pop() {
    //当当前弹出的值等于当前栈的最小值时弹出最小值栈
    //由于两个栈保持着顺序的稳定所以可以这样
    if (s.top() == buf.top())
      buf.pop();
    s.pop();
  }

  int top() {
    return s.top();
  }

  int getMin() {
    return buf.top();
  }

堆盘子。设想有一堆盘子，堆太高可能会倒下来。
因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。
请实现数据结构SetOfStacks，模拟这种行为。
SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。
此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同
（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。 
进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。
当某个栈为空时，应当删除该栈。
当栈中没有元素或不存在该栈时，pop，popAt 应返回 -1.

示例1:
 输入：
["StackOfPlates", "push", "push", "popAt", "pop", "pop"]
[[1], [1], [2], [1], [], []]
 输出：
[null, null, null, 2, 1, -1]

示例2:
 输入：
["StackOfPlates", "push", "push", "push", "popAt", "popAt", "popAt"]
[[2], [1], [2], [3], [0], [0], [0]]
 输出：
[null, null, null, null, 2, 1, 3]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/stack-of-plates-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    //不使用STL，设置空闲链表，93.0%,60ms
    //每个栈都是双向链表方便操作
    //删除空栈时改为将空栈存入空闲链表中
    //申请栈时先尝试从空闲链表分配，加速内存分配
    //可以再给空闲链表增加阈值减少无用内存的占用
private:
    struct PlateStack {
        int* stack;
        //双向链表方便操作
        PlateStack* next = NULL;
        PlateStack* prev = NULL;
        int cur = 0;
        PlateStack(int cap) {
            stack = new int[cap];
        }
    };

    //在用栈表头
    PlateStack* use;
    //栈表尾
    PlateStack* now;
    //空闲栈表
    PlateStack* del;
    int cap;

public:
    StackOfPlates(int cap) {
        this->cap = cap;
        use = new PlateStack(cap);
        now = use;
        del = new PlateStack(cap);
    }

    void push(int val) {
        //特殊情况跳出
        if (cap == 0) {
            return;
        }
        //当指针达到栈尾时申请新栈
        if (now->cur == cap) {
            newNow();
        }
        //存入
        now->stack[now->cur] = val;
        ++now->cur;
    }

    int pop() {
        //当试图出栈一个空栈时
        if (now->cur == 0) {
            //删除并检测是否已经没有元素了
            if (!delStk(now))
                return -1;
        }
        //出栈
        --now->cur;
        int ret = now->stack[now->cur];
        //出栈后若栈空则删除栈
        if (now->cur == 0) {
            delStk(now);
        }
        return ret;
    }

    int popAt(int index) {
        //从头遍历所需序号的栈
        //这部分可以利用双向链表的特性，储存左右两边的栈数量进行加速搜索
        PlateStack* find = use;
        for (int i = 0; i < index; i++) {
            if (find == NULL) {
                return -1;
            }
            find = find->next;
        }

        //找不到栈时报错
        if (find == NULL) {
            return -1;
        }

        //以下类似pop
        if (find->cur == 0) {
            if (!delStk(find))
                return -1;
        }
        --find->cur;
        int ret = find->stack[find->cur];
        if (find->cur == 0) {
            delStk(find);
        }
        return ret;
    }

    //新建栈
    void newNow() {
        //当空闲链表非空时
        if (del != NULL) {
            //将空闲链表头取一个作为新栈
            now->next = del;
            del->prev = now;
            del = del->next;
            now = now->next;
            now->next = NULL;
        }
        else {
            //否则新建
            now->next = new PlateStack(cap);
            now->next->prev = now;
            now = now->next;
            now->next = NULL;
        }
    }

    bool delStk(PlateStack* tar) {
        //当目标栈是唯一栈时，表示全空
        if (!tar || tar->next == NULL && tar->prev == NULL) {
            return false;
        }

        //存在下一个栈时
        if (tar->next) {
            //存在上一个栈时
            if (tar->prev) {
                //通过指针重指跳过当前栈
                tar->prev->next = tar->next;
                tar->next->prev = tar->prev;
            }
            else {
                //只有下一个栈时，此时必然是use栈，也即是栈表头
                //更改链表的同时需要改变use的位置
                tar->next->prev = NULL;
                use = tar->next;
            }
        }
        else {
            //没有下一个栈时，此时必然是now栈，也即是栈表尾
            //更改链表的同时需要改变now的位置
            tar->prev->next = NULL;
            now = tar->prev;
        }

        //重整完链表后，类似new操作将腾出来的栈放到空闲链表头
        if (del != NULL) {
            tar->next = del;
            del->prev = tar;
            del = del->prev;
            del->prev = NULL;
        }
        else {
            del = tar;
            del->prev = NULL;
            del->next = NULL;
        }

        return true;
    }

    //样例的使用STL的方法，94.6%,56ms
    //使用已经写好的容器能简化代码
public:
    StackOfPlates(int cap) {
        len = cap;
    }

    void push(int val) {
        if (len == 0) {
            return;
        }
        //栈表空或当前到达栈尾时
        if (rec.size() == 0 || rec[rec.size() - 1].size() == len) {
            //新建栈并压入数据再压入链表
            stack<int> s;
            s.push(val);
            rec.push_back(s);
        }
        else {
            //直接压入
            rec[rec.size() - 1].push(val);
        }
    }

    int pop() {
        //栈表非空时
        if (rec.size() != 0) {
            int r = rec[rec.size() - 1].top();
            rec[rec.size() - 1].pop();
            //若当前栈空，则弹出栈
            if (rec[rec.size() - 1].empty()) {
                rec.pop_back();
            }
            return r;
        }
        return -1;
    }

    int popAt(int index) {
        //检测是否序号在链表中
        if (index < rec.size()) {
            //直接用下标访问
            int r = rec[index].top();
            rec[index].pop();
            if (rec[index].empty()) {
                rec.erase(rec.begin() + index);
            }
            return r;
        }
        return -1;
    }
private:
    //栈向量嵌套容器
    vector<stack<int>> rec;
    int len = 0;

实现一个MyQueue类，该类用两个栈来实现一个队列。

示例：
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明：
你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  //传统的双栈，进行了状态位优化，100%，0ms
  //状态位是用来加速连续的pop和push的
private:
  stack<int> stk;
  stack<int> lin;
  bool pushing;

public:
  /** Initialize your data structure here. */
  MyQueue() {
    //初始是push状态
    pushing = true;
  }

  /** Push element x to the back of queue. */
  void push(int x) {
    //当当前不是push状态时需要反转一次
    //用状态位防止多余的反转
    if (!pushing) {
      pushing = true;
      //将二号栈的内容全部转移到一号栈
      //这样使得内容方向反转
      while (!lin.empty()) {
        stk.push(lin.top());
        lin.pop();
      }
    }
    //压入
    stk.push(x);
  }

  /** Removes the element from in front of queue and returns that element. */
  int pop() {
    //类似push
    if (pushing) {
      pushing = false;
      while (!stk.empty()) {
        lin.push(stk.top());
        stk.pop();
      }
    }
    int ret = lin.top();
    lin.pop();
    return ret;
  }

  /** Get the front element. */
  int peek() {
    //类似pop
    if (pushing) {
      pushing = false;
      while (!stk.empty()) {
        lin.push(stk.top());
        stk.pop();
      }
    }
    return lin.top();
  }

  /** Returns whether the queue is empty. */
  bool empty() {
    //利用状态位来读取对应栈的信息
    //虽然有两个栈但是它们只有一个会有内容
    if (pushing) {
      return stk.empty();
    }
    else {
      return lin.empty();
    }
  }

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。

示例1:

 输入：
["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]
 输出：
[null,null,null,1,null,2]
示例2:

 输入：
["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]
 输出：
[null,null,null,null,null,true]
说明:

栈中的元素数目在[0, 5000]范围内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-of-stacks-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    //传统的缓冲栈写法,48.5%,144ms
    //本质上是进行了动态的插入排序，很慢
private:
    stack<int> stk;
    stack<int> tmp;

public:
    SortedStack() {

    }

    void push(int val) {
        if (stk.empty()) {
            stk.push(val);
        }
        else {
            if (stk.top() >= val) {
                stk.push(val);
            }
            else {
                //找到正好可以放入新元素的位置
                //遍历过的元素放入缓冲区
                while (!stk.empty()) {
                    tmp.push(stk.top());
                    stk.pop();
                    if (!stk.empty() && stk.top() >= val) {
                        break;
                    }
                }
                //压入
                stk.push(val);
                //从缓冲区中把暂存的元素放回
                while (!tmp.empty()) {
                    stk.push(tmp.top());
                    tmp.pop();
                }
            }
        }
    }

    //余下操作正常
    void pop() {
        if (stk.empty()) {
            return;
        }
        stk.pop();
    }

    int peek() {
        if (stk.empty()) {
            return -1;
        }
        return stk.top();
    }

    bool isEmpty() {
        return stk.empty();
    }

    //优化的写法,91.4%,20ms
    //主要是利用滑动两个栈来减少出入栈的次数
public:
    SortedStack() {
    }

    //在两个栈中互相抛接，相当于把目标排列滑动到符合val的中间值
    //s2是小于val的栈，s1是大于val的栈
    void push(int val) {
        //将s2中所有大于val都压入s1
        while (!s2.empty() && s2.top() > val) {
            //emplace，C11新特性
            //类似于push，但是emplace可以直接自动构造对象，功能比push多
            //push只能在构造完对象后复制进去
            //所以对于需要构造对象的场合用emplace更省内存
            //见：https://blog.csdn.net/Kprogram/article/details/82055673
            s1.emplace(s2.top());
            s2.pop();
        }
        //将s1中所有小于val的都压入s2
        while (!s1.empty() && s1.top() < val) {
            s2.emplace(s1.top());
            s1.pop();
        }
        //剩下的位置是等于val的，压入s1
        //初始也是压入s1
        s1.emplace(val);
    }

    void pop() {
        //将s2(小于val)的元素全部压到s1中
        while (!s2.empty()) {
            s1.emplace(s2.top());
            s2.pop();
        }
        if (!s1.empty()) s1.pop();
    }

    //同pop
    int peek() {
        while (!s2.empty()) {
            s1.emplace(s2.top());
            s2.pop();
        }
        return s1.empty() ? -1 : s1.top();
    }

    //两个栈都空时才空，因为完整的数据是由两个栈一起保存的
    bool isEmpty() {
        return s1.empty() && s2.empty();
    }
private:
    //双栈
    stack<int> s1, s2;

有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。
在收养该收容所的动物时，
收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，
或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。
换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，
实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat。
允许使用Java内置的LinkedList数据结构。

enqueue方法有一个animal参数，animal[0]代表动物编号，animal[1]代表动物种类，其中 0 代表猫，1 代表狗。
dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。

示例1:
 输入：
["AnimalShelf", "enqueue", "enqueue", "dequeueCat", "dequeueDog", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [], [], []]
 输出：
[null,null,null,[0,0],[-1,-1],[1,0]]

示例2:
 输入：
["AnimalShelf", "enqueue", "enqueue", "enqueue", "dequeueDog", "dequeueCat", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [[2, 1]], [], [], []]
 输出：
[null,null,null,null,[2,1],[0,0],[1,0]]

说明:
收纳所的最大容量为20000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/animal-shelter-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    //记录了时间的队列，操作复杂因此很慢,28.9%,256ms
    //加速的关键在于询问考官从而知道编号是自增的，本来就无需记录时间
public:
    AnimalShelf() {
        time = 0;
    }

    //将编号和时间一起压入
    void enqueue(vector<int> animal) {
        if (animal[1] == 0) {
            Cat.push({ animal[0],time });
            ++time;
        }
        else {
            Dog.push({ animal[0],time });
            ++time;
        }
    }

    vector<int> dequeueAny() {
        //要注意队列是使用front得到队列头的
        if (Cat.empty() && Dog.empty()) {
            return { -1,-1 };
        }
        if (Cat.empty() && !Dog.empty()) {
            vector<int> ret = { Dog.front()[0],1 };
            Dog.pop();
            return ret;
        }
        if (Dog.empty() && !Cat.empty()) {
            vector<int> ret = { Cat.front()[0],0 };
            Cat.pop();
            return ret;
        }

        if (Cat.front()[1] < Dog.front()[1]) {
            vector<int> ret = { Cat.front()[0],0 };
            Cat.pop();
            return ret;
        }
        else {
            vector<int> ret = { Dog.front()[0],1 };
            Dog.pop();
            return ret;
        }
    }

    vector<int> dequeueDog() {
        if (Dog.empty()) {
            return { -1,-1 };
        }
        vector<int> ret = { Dog.front()[0],1 };
        Dog.pop();
        return ret;
    }

    vector<int> dequeueCat() {
        if (Cat.empty()) {
            return { -1,-1 };
        }
        vector<int> ret = { Cat.front()[0],0 };
        Cat.pop();
        return ret;
    }

private:
    queue<vector<int>> Dog;
    queue<vector<int>> Cat;
    int time;

    //由于编号自增，只保存了编号的版本,120ms
public:
    AnimalShelf() {

    }

    void enqueue(vector<int> animal) {
        int type = animal[1];
        int num = animal[0];
        if (type == 1)dogs.push(num);
        else cats.push(num);
    }

    vector<int> dequeueAny() {
        //写得花哨其实判断量没有变少
        vector<int> res(2, -1);
        if (!dogs.empty()) {
            res[0] = dogs.front(), res[1] = 1;
        }
        if (!cats.empty() && (res[0] == -1 || cats.front() < res[0]))
            res[0] = cats.front(), res[1] = 0;
        if (res[1] == 0)cats.pop();
        else if (res[1] == 1) dogs.pop();
        return res;

    }

    vector<int> dequeueDog() {
        vector<int> res(2, -1);
        if (!dogs.empty())res[0] = dogs.front(), dogs.pop(), res[1] = 1;
        return res;
    }

    vector<int> dequeueCat() {
        vector<int> res(2, -1);
        if (!cats.empty())res[0] = cats.front(), cats.pop(), res[1] = 0;
        return res;
    }
private:
    queue<int> dogs;
    queue<int> cats;