一、使用一个附加的栈来模拟插入排序。将原栈中的数据依次出栈与附加栈中的栈顶元素比较, 如果附加栈为空,则直接将数据压栈。否则, 如果附加栈的栈顶元素大于从原栈中弹出的元素,则将附加栈的栈顶元素压入原栈。 一直这样查找直到附加栈为空或栈顶元素已经不大于该元素, 则将该元素压入附加栈。
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; }
二、使用一个优先队列来为出栈的元素排序,原栈中的元素不断出栈然后插入优先队列, 直到原栈为空。然后再将优先队列中的元素不断压回原栈,这样操作后, 栈中的元素便有序化了。
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(); } }
主程序测试时可以随机产生一系列数入栈,调用程序。。