题目
原文：
Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.
译文：
写程序将一个栈按升序排序。对这个栈是如何实现的，你不应该做任何特殊的假设。 程序中能用到的栈操作有：push | pop | peek | isEmpty。
解答
方案1：
使用一个附加的栈来模拟插入排序。将原栈中的数据依次出栈与附加栈中的栈顶元素比较， 如果附加栈为空，则直接将数据压栈。否则， 如果附加栈的栈顶元素大于从原栈中弹出的元素，则将附加栈的栈顶元素压入原栈。 一直这样查找直到附加栈为空或栈顶元素已经不大于该元素， 则将该元素压入附加栈。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
stack<int> Ssort(stack<int> s){
stack<int> t;
while(!s.empty()){
int data = s.top();
s.pop();
while(!t.empty() && t.top()>data){
s.push(t.top());
t.pop();
}
t.push(data);
}
return t;
}
方案2：
使用一个优先队列来为出栈的元素排序，原栈中的元素不断出栈然后插入优先队列， 直到原栈为空。然后再将优先队列中的元素不断压回原栈，这样操作后， 栈中的元素便有序化了。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
void Qsort(stack<int> &s){
priority_queue< int,vector<int>,greater<int> > q;
while(!s.empty()){
q.push(s.top());
s.pop();
}
while(!q.empty()){
s.push(q.top());
q.pop();
}
}
完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstdlib>
#include <stack>
#include <queue>
using namespace std;
void Qsort(stack<int> &s){
priority_queue< int,vector<int>,greater<int> > q;
while(!s.empty()){
q.push(s.top());
s.pop();
}
while(!q.empty()){
s.push(q.top());
q.pop();
}
}
stack<int> Ssort(stack<int> s){
stack<int> t;
while(!s.empty()){
int data = s.top();
s.pop();
while(!t.empty() && t.top()>data){
s.push(t.top());
t.pop();
}
t.push(data);
}
return t;
}
int main(){
srand((unsigned)time(0));
stack<int> s;
for(int i=0; i<10; ++i)
s.push((rand()%100));
//s = Ssort(s);
Qsort(s);
while(!s.empty()){
cout<<s.top()<<" ";
s.pop();
}
return 0;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2012/12/23/3.6/
