leetcode 链接：栈排序
《程序员面试代码指南》by 左程云 中相同题目：★☆☆☆用一个栈实现另一个栈的排序

题目

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

示例：

  1.  输入：
  2. ["SortedStack", "push", "push", "peek", "pop", "peek"]
  3. [[], [1], [2], [], [], []]
  4.  输出：
  5. [null,null,null,1,null,2]
 输入： 
["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]
 输出：
[null,null,null,null,null,true]

解答 & 代码

设置一个辅助栈 stackTemp 来帮助数据栈 stackData 排序

  • push(val)：
    • 先将数据栈 stackData 中小于 val 的元素都弹出压入到辅助栈 stackTemp
    • 再将 val 压入到数据栈 stackData
    • 最后将辅助栈 stackTemp 的元素全部重新弹出压回数据栈 stackData

  • pop：stackData 栈若不为空，则弹出一个元素 ```cpp class SortedStack { stack stackData; stack stackTemp; public: SortedStack() { }

    void push(int val) {

      // 先将data栈中小于val的元素都压入temp栈
  while(!stackData.empty() && stackData.top() < val)
  {
      stackTemp.push(stackData.top());
      stackData.pop();
  }
  // 将val押入data栈
  stackData.push(val);
  // 将temp栈中元素重新压回data栈
  while(!stackTemp.empty())
  {
      stackData.push(stackTemp.top());
      stackTemp.pop();
  }

    }

    void pop() {

      if(!stackData.empty())
      stackData.pop();

    }

    int peek() {

      return stackData.empty() ? -1 : stackData.top();

    }

    bool isEmpty() {

      return stackData.empty();

    } };

/**

  • Your SortedStack object will be instantiated and called as such:
  • SortedStack* obj = new SortedStack();
  • obj->push(val);
  • obj->pop();
  • int param_3 = obj->peek();
  • bool param_4 = obj->isEmpty(); */
    执行结果：
    执行结果：通过

执行用时：232 ms, 在所有 C++ 提交中击败了 36.3% 的用户 内存消耗：45.7 MB, 在所有 C++ 提交中击败了 36.6% 的用户 ```