题目描述
栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
示例：
输入：
["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]
输出：
[null,null,null,1,null,2]
输入：
["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]
输出：
[null,null,null,null,null,true]
说明：
- 栈中的元素数目在[0, 5000]范围内。
题目链接： https://leetcode-cn.com/problems/sort-of-stacks-lcci/
思路
使用两个栈，一个栈 s 用来存储数据，另一个栈是辅助栈 help；
入栈：
- 如果 val > s.top()，那么将 s 的栈顶元素出栈并压入 help 直到 val 不大于 s.top()；
- 将 val 压入 s.top()；
- 将 help 中的元素出栈并压入 s；
入栈类似于最小栈的做法；
出栈：
- 如果 s 不为空，则 s.pop();
获取栈顶元素：
- 如果 s 不为空，返回 s.top()；
- 否则 返回 -1；
代码如下：
class SortedStack {
stack<int> s;
stack<int> help;
public:
SortedStack() {
}
void push(int val) {
while(!s.empty() && val>s.top()){
help.push(s.top()); s.pop();
}
s.push(val);
while(!help.empty()){
s.push(help.top());
help.pop();
}
}
void pop() {
if(!s.empty()) s.pop();
}
int peek() {
if(!s.empty()) return s.top();
else return -1;
}
bool isEmpty() {
return s.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();
*/