C++使用辅助堆栈进行排序.docx

《C++使用辅助堆栈进行排序.docx》由会员分享，可在线阅读，更多相关《C++使用辅助堆栈进行排序.docx（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、使用堆栈按升序对元素进行排序，即使最小的元素成为堆栈的顶部元素。例如, 给定堆栈元素(从下到上)：5, 2, 6, 9,对元素进行排序以使堆栈元素成为(从 下到上)：9, 6, 5, 2O您可以使用的唯一数据结构是基于数组的堆栈。给定一 个堆栈st,使用一个额外的堆栈tmpst来存储临时数据。a.编写一个C+程序，以升序对基于数组的堆栈中的元素进行排序。b.演示给定输入编号25.10, 15, 2030的排序过程。算法：pop将st输出到一个变量tmp,直到它完成所有元素。而tmpst不为空如果tmpst的顶部元素小于tmp,弹出tmpst并将该元素推送到st上将tmp推到tmpst上核心代码

2、：void Solution:sort_by_stack(stack &st) 一 一stack *tmpst = new stack;int index = 0;/数据栈不为空while(!st. empty() /获取数据栈栈顶元素int tmp = st. top ();/栈顶元素弹出St. pop();index+;cout t index st: pop out tmp = empty () tmpst-push(tmp);cout zztttmpst : push tmp empty() int tmpst_top = tmpst-top();cout z，tttmpst: get

3、 the top element tmpst_top endl;if (tmp 数据栈栈顶元素/辅助栈栈顶元素出栈，压入数据栈tmpst-pop ();cout z/tttSince tmpst_top tmp ，tmpst : pop out tmpst_top endl;st.push(tmpst_top);cout /ztttst: push tmpst_top tmpst_top) /辅助栈栈顶元萋 数据栈栈顶元素/跳过当前循环，数据栈栈顶元素直接压入辅助栈cout /ztttSince tmpst_top tmp ，exit the loop” push(tmp);cout /ztt

4、tmpst : push tmp empty() int x = tmpst-top();tmpst-pop();st. push(x);)运行结果: F:workcodesortByStack.exe1St :2st:303st:4st:30205st:6st:7st:tmpst：30pop outtmpst:20pop outtmpst：15pop out8st:9st:element 15looploop10loop11tmpst:12element 2030, exit the loop(1) push the elements 25 10 15 20 30 onto the stac

5、k st.(2) the process of sorting elements of stack st is:element 3015, tmpst : pop outelement 1015, exit the loopSince 15 Since 30 Since 20 (tmpst:10 15 20 25 30Since lo Since 20 tmpst : push 30pop out 20 =tmpst: get the top element 30Since 30 20, tmpst : pop out st: push 30tmpst : push 20 pop out 30

6、 =tmpst： get the topSince 20 tmpst： get the top Since 30 st: push 30tmpst: get the top element 20Since 20 15, tmpst : pop out st: push 20 tmpst : push 15 pop out 20 = tmpst： get the top element 15Since 15 tmpst: get the top element 20Since 20 get the top element 30Since 30 10, tmpst : st: push 30get

7、 the top element 20 Since 20 10, tmpst ： st: push 20get the top element 15 Since 15 10, tmpst : st: push 15tmpst : push 10pop out 15 =tmpst: get the top Since 10 8 st: pop out 15 =tmpst: get the top15, exit thetmpst : push lo9 st: pop out 20 =tmpst: get the topelement lo20, exit thetmpst : push 20st

8、: pop out 30 =tmpst: get the topelement 2030, exit thetmpst : push 30st： pop outget the topelement 30st ： push 3025, tmpst : pop out 30get the topelement 20tmpst : push 2o25, exit the loopst: pop out 30 =tmpst： get the topelement 2otmpst : push 3030, exit the loop(3) the sorting of stack st ends(4) the popping sequence of st is :Process exited after 0.080/1 seconds with return value 0清接任意键继续.tmpst： get the top