题目
栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：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]范围内。
分析
栈是先进后出，对栈进行排序，将这个栈命名为数据栈A，使最小元素位于数据栈的栈顶，也就意味着栈底是最大的元素，先放进去的是最大的元素，然后按顺序递减到最小元素。
题目说可以使用一个辅助栈来实现，命名为辅助栈B，那么辅助栈内的元素存储数据的时候，数据大小顺序应该是反过来，也就是最大元素位于辅助栈B的栈顶。 这样从辅助栈B迁移数据到数据栈A的时候，刚好满足题目需求。
排序的时候，使用前后堆叠的方式进行即可，比如说，以一组排好顺序的数据作为一组，如果比这组数据最大的大，就放在大的一端，比这组数据的最小的数据小，就放在小的一端。
比如类似数据如下：
data_stackA: 8 9 2 3 1 7 5
sort_stackB: - 为了使数据栈A最小元素位于栈顶，则必须让数据A中小的元素放在辅助栈B的栈底。 从数据栈A取出 5 放入辅助栈B
data_stackA: 8 9 2 3 1 7
sort_stackB: 5 - 继续比较 数据栈A的数据 7 比 辅助栈B的栈顶5还大，将大的数据 7 放入 辅助栈B。
data_stackA: 8 9 2 3 1
sort_stackB: 5 7- 继续比较 数据栈A，发现 1 比辅助栈B栈顶7小，则说明当前不是合适的存放位置，将 1 存放入临时变量data_tmp中，然后将数据栈A的1释放掉
data_stackA: 8 9 2 3
data_tmp: 1
sort_stackB: 5 7- 再将辅助栈B数据重新依次和临时变量data_tmp进行比较，如果辅助栈B栈顶数据大于临时变量data_tmp，就重新压回数据栈A中，如果小于，则将临时变量data_tmp压入辅助栈B，然后清空辅助变量data_tmp。
data_stackA: 8 9 2 3 7 5
data_tmp:
sort_stackB: 1- 然后可以将
5 7重新压回辅助栈B， 这时候相当于辅助栈B的5 7数据作为了一组有序数据进行了移动，后续循环进行2~4进行数据分组堆叠操作操作即可完成辅助栈排序。
data_stackA: 8 9 2 3
data_tmp:
sort_stackB: 1 5 7- 完成辅助栈B的排序后，将辅助栈数据B重新压入数据栈A即可得到结果
data_stackA:
data_tmp:
sort_stackB: 1 2 3 5 7 8 9 只用一个栈的代码规则汇总
- 构建临时变量data_tmp和辅助栈B
- 如果临时变量data_tmp没有数据，则遍历数据栈A，如果数据栈A栈顶比辅助栈B顶大，则将数据栈A数据压入辅助栈B，同时释放数据栈A这个数据，否则放入临时变量data_tmp，同时释放数据栈A的这个数据。
- 如果临时变量data_tmp有数据，则比较临时变量data_tmp是否大于辅助栈B栈顶，如果大于，则将临时变量data_tmp放入辅助栈B栈顶，否则将辅助栈B栈顶数据压入数据栈A中。
- 重复操作2和3，直到数据栈A数据清零，且临时变量data_tmp中没有数据，然后重新将辅助栈B数据压入数据栈A，得到的即为要求结果。
使用共两个栈保存数据
如果能使用两个栈进行数据保存的话，那么只需要维护两个栈，一个栈总是顺序排序，另一个栈总是逆序排序，
在插入数据的时候动态调整插入数据位置，就能减少在push操作中重复传递数据的次数，进而能提高性能。
通过例子来说明， 现有数据data 8 9 2 3 1 7 5 ：
data: 8 9 2 3 1 7 5
data_stackA:
data_tmp: - 始终保证 数据栈 data_stackA 的数据比 辅助栈 data_tmp 的大，并将data_stackA作为最小栈，data_tmp 作为最大栈。先添加 5 入数据栈 data_stackA
data: 8 9 2 3 1 7
data_stackA: 5
data_tmp: - 继续添加 7 ， 因为 7 比 data_stackA 栈顶数据5大，又因为 data_stackA 数据需要大于 data_tmp ，因此要将 data_stackA 数据压入data_tmp，然后再继续把 7 压入 data_stackA。
data: 8 9 2 3 1
data_stackA: 7
data_tmp: 5- 继续重复 1~2 操作，直到存入所有数据
- 在peek取出数据或pop操作的时候，要将临时最大栈data_tmp 数据压入数据最小栈data_stackA，因为data_stackA数据始终比data_tmp大，因此最后data_stackA 数据为最小栈。
两个栈编码规则
- push操作中，如果插入数据data始终比最小栈data_stackA大，则将data_stackA数据压入data_tmp，然后将data压入data_stackA。
- push操作中，如果插入数据data比最小栈data_stackA小，但是比最大栈data_tmp大，则直接将data压入data_stackA。
- push操作中，如果插入数据data始终比最大栈data_tmp小，则将data_tmp数据压入data_stackA，然后将data压入data_stackA。
- seek或pop操作中，如果最大栈data_tmp中存在数据，则将data_tmp数据压入data_stackA。
- 将数据最小栈data_stackA 定义为
m_min_stack, 将辅助最大栈data_tmp定义为m_max_stack。
代码
只用一个栈排序的代码
#include <stack>
class SortedStack {
public:
SortedStack()
{
}
void push(int val)
{
if (val < 0)
return;
m_data.push(val);
this->sort();
}
void pop()
{
if (m_data.empty())
return;
m_data.pop();
}
int peek()
{
if (m_data.empty())
return -1;
return m_data.top();
}
bool isEmpty()
{
return m_data.empty();
}
private:
void sort()
{
// sort
int tmp_data = -1;
std::stack<int> stackB;
while (!m_data.empty() || tmp_data >= 0) {
if (tmp_data >= 0) {
while (!stackB.empty() && tmp_data <= stackB.top()) {
m_data.push(stackB.top());
stackB.pop();
}
stackB.push(tmp_data);
tmp_data = -1;
continue;
}
if (stackB.empty() || m_data.top() >= stackB.top()) {
stackB.push(m_data.top());
} else {
tmp_data = m_data.top();
}
m_data.pop();
}
while (!stackB.empty()) {
m_data.push(stackB.top());
stackB.pop();
}
}
std::stack<int> m_data;
};
数据栈+辅助栈排序代码
#include <stack>
class SortedStack {
public:
SortedStack()
{
}
void push(int val)
{
if (m_min_stack.empty()) {
m_min_stack.push(val);
return;
}
if (val >= m_min_stack.top()) {
while (!m_min_stack.empty() && val >= m_min_stack.top()) {
m_max_stack.push(m_min_stack.top());
m_min_stack.pop();
}
m_min_stack.push(val);
return;
}
// val < min_stack.top
if (m_max_stack.empty()) {
m_min_stack.push(val);
return;
}
// val < min_stack.top
if (val >= m_max_stack.top()) {
m_min_stack.push(val);
return;
}
// val < max_stack.top < min_stack.top
while (!m_max_stack.empty() && val <= m_max_stack.top()) {
m_min_stack.push(m_max_stack.top());
m_max_stack.pop();
}
m_min_stack.push(val);
}
void pop()
{
if (this->isEmpty())
return;
while (!m_max_stack.empty()) {
m_min_stack.push(m_max_stack.top());
m_max_stack.pop();
}
m_min_stack.pop();
}
int peek()
{
if (this->isEmpty())
return -1;
while (!m_max_stack.empty()) {
m_min_stack.push(m_max_stack.top());
m_max_stack.pop();
}
return m_min_stack.top();
}
bool isEmpty()
{
return m_min_stack.empty() && m_max_stack.empty();
}
private:
std::stack<int> m_min_stack;
std::stack<int> m_max_stack;
};
#ifdef __TEST__
#include <iostream>
int main(int argc, char* argv[])
{
SortedStack* p_s = new SortedStack;
p_s->push(8);
p_s->push(9);
p_s->push(2);
p_s->push(3);
p_s->push(1);
p_s->push(7);
p_s->push(5);
int t = p_s->peek();
std::cout << "top: 1 == " << t << "\n";
p_s->pop();
t = p_s->peek();
std::cout << "top: 2 == " << t << "\n";
p_s->pop();
t = p_s->peek();
std::cout << "top: 3 == " << t << "\n";
p_s->pop();
t = p_s->peek();
std::cout << "top: 5 == " << t << "\n";
p_s->pop();
t = p_s->peek();
std::cout << "top: 7 == " << t << "\n";
p_s->pop();
t = p_s->peek();
std::cout << "top: 8 == " << t << "\n";
p_s->pop();
t = p_s->peek();
std::cout << "top: 9 == " << t << "\n";
p_s->pop();
delete p_s;
return 0;
}
#endif //__TEST__