请编写一个程序,按升序对栈进行排序(即最大元素位于栈顶),要求最多只能使用一个额外的栈存放临时数据,但不得将元素复制到别的数据结构中。
除了原栈外,需要借助一个栈help。用某种规则使得原栈的元素进入help栈,且help栈是排好序的而且栈顶最小,这样从help中搬运元素回原栈时,原栈才是排好序的,且栈顶最大。
整个过程中,想象两个栈是两支试管口对口横着放:
每次取出栈顶元素t,
情况1: 若help为空或t小于help栈顶,则压入help中
情况2:若help不为空且t大于help栈顶,则从help中弹出元素压入原栈内,直至到达情况1为止。然后将t压入help中。
情况1比较容易理解,要想栈排序使得栈顶最小,那么新元素小于栈顶,就可以直接压栈。
情况2中,为了达到1的情况,所以从help中弹出元素,直到发生情况1为止。整个过程有点像插入排序,更形象来说,像是算盘拨珠子的过程。
因为元素不能扔掉,所以help弹出来的都压入了原栈内。这些元素不必刻意处理,在后续过程会回到合适位置的。
CODE
void StackSort(stack<int> &s){
stack<int> help;
while(!s.empty()){
int t=s.top();
s.pop();
while(!help.empty() && help.top()>t){ //因为短路求值的特性,不会抛出异常
int uu=help.top();
help.pop();
s.push(uu);
}
help.push(t);
}
s=help;
}