C++使用一个栈实现另一个栈的排序算法示例
本文实例讲述了C++用一个栈实现另一个栈的排序算法。分享给大家供大家参考,具体如下:
题目:
一个栈中元素类型为整型,现在想将该栈从顶到底按从小到大的顺序排序,只许申请一个辅助栈。
除此之外,可以申请新的变量,但不能申请额外的数据结构。如何完成排序?
算法C++代码:
classSolution { public: //借助一个临时栈排序源栈 staticvoidsortStackByStack(stack&s) { stack *sTemp=newstack ; while(!s.empty()) { intcur=s.top(); s.pop(); //当源栈中栈顶元素大于临时栈栈顶元素时,将临时栈中栈顶元素放回源栈 //保证临时栈中元素自底向上从大到小 while(!sTemp->empty()&&cur>sTemp->top()) { inttemp=sTemp->top(); sTemp->pop(); s.push(temp); } sTemp->push(cur); } //将临时栈中的元素从栈顶依次放入源栈中 while(!sTemp->empty()) { intx=sTemp->top(); sTemp->pop(); s.push(x); } } };
测试用例程序:
#include#include usingnamespacestd; classSolution { public: //借助一个临时栈排序源栈 staticvoidsortStackByStack(stack &s) { stack *sTemp=newstack ; while(!s.empty()) { intcur=s.top(); s.pop(); //当源栈中栈顶元素大于临时栈栈顶元素时,将临时栈中栈顶元素放回源栈 //保证临时栈中元素自底向上从大到小 while(!sTemp->empty()&&cur>sTemp->top()) { inttemp=sTemp->top(); sTemp->pop(); s.push(temp); } sTemp->push(cur); } //将临时栈中的元素从栈顶依次放入源栈中 while(!sTemp->empty()) { intx=sTemp->top(); sTemp->pop(); s.push(x); } } }; voidprintStack(stack s) { while(!s.empty()) { cout< *s=newstack ; s->push(5); s->push(7); s->push(6); s->push(8); s->push(4); s->push(9); s->push(2); cout<<"排序前的栈:"< 运行结果:
排序前的栈: 2948675 排序后的栈: 9876542希望本文所述对大家C++程序设计有所帮助。