# CCI题目：3-6：Stack Sort

By | 2012 年 11 月 20 日

1.逐个从st中pop元素，先pop到一个临时变量，如果pop出来的元素比临时变量小，则直接进入buffer，否则，把临时变量顶入buffer，st新pop到临时变量。

2.将buffer中的元素全部倒回st
3.重复1，2两步，直到1中第一种情况不出现为止。

《CCI》上的解法更效率一些（在阶上没有提升），就是在st到buffer中处理的过程中，允许中途将buffer中的元素倒回一部分到st，直到临时变量找到位置，然后继续将st向buffer倒。直到st为空。

Write a program to sort a stack in ascending order. You should not make any assump- tions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

Code

<

pre>

//
// main.cpp
// CCI.3.6.Sort a Stack
//
// Created by Qiu Xiangyu on 12-11-20.
//

# include

using namespace std;
void sortStack(stack &st) {
stack buffer;
bool bubble = true;
int rnd = 1;
while (bubble) {
cout<<“round “<<rnd++<<endl;
bubble = false;
//1.dump numbers from st to buffer and change the order of them
int middle = st.top();
st.pop();
while (st.size()) {
if (middle > st.top()) {
//if st.top is less than the one pop before, then pop to buffer
buffer.push(st.top());
bubble = true;
} else {
//if st.top is ge the one pop before, then push the middle to buffer ,then pop to middle
buffer.push(middle);
middle = st.top();
}
st.pop();
}
buffer.push(middle);
//2.dump buffer to st
while (buffer.size()) {
st.push(buffer.top());
buffer.pop();
}
}
}
int main(int argc, const char * argv[])
{
std::cout << “Hello, World!\n”;
stack st;
srand((unsigned int)clock());
for (int i = 0; i < 100; ++i) {
st.push(rand() % 10);
}
sortStack(st);
while (st.size()) {
cout<<st.top()<<endl;
st.pop();
}
return 0;
}