day14：栈排序

问题描述： 

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：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]

说明:

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

解决方案：

1、分析题目：用两个栈（主栈+辅助栈）实现排序算法，返回主栈

2、栈顶元素比较：主栈 始终为较大的值，辅助栈 始终为小值

注：辅助栈中始终为降序出栈（先大后小）

3、循环判断：如果 主栈 中栈顶元素 < 待输入值（val），该元素归入 辅助栈里。

例：1，3，2

（1）1--> 主栈

（2）1<3：1-->辅助栈，3-->主栈，1-->主栈 

（3）1<2：同上，结果：主栈（3）辅助栈（1）

                   第二次判断：3>2 ：2 直接放入 主栈，合并辅助栈，即主栈（1，2，3）

函数代码：

class SortedStack {
public:stack<int> num;stack<int> tmp;SortedStack() {}void push(int val) {while(!num.empty() && num.top()<val){tmp.push(num.top());num.pop();}num.push(val);while(!tmp.empty()){num.push(tmp.top());tmp.pop();}}void pop() {if(!num.empty())    num.pop();}int peek() {if(num.empty()) return -1;return num.top();}bool isEmpty() {return num.empty();}
};