C++用辅助堆栈进行排序--完整代码.docx

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

1、使用堆栈按升序对元素进行排序，即使最小的元素成为堆栈的顶部元素。例如, 给定堆栈元素(从下到上)：5, 2, 6, 9,对元素进行排序以使堆栈元素成为从 下到上)：9, 6, 5, 2。您可以使用的唯一数据结构是基于数组的堆栈。给定一 个堆栈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 /ztttmpst : push tmp empty () int tmpst_top = tmpst-top ();cout z，tttmpst: get the

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

4、: push tmp empty() int x = tmpst-top ();tmpst-pop ();st. push (x);) 运行结果:-F:workcodesortByStack.exepush the elements 25 10 15 20 30 onto the stack st.(1) the process of sorting elements of stack st is:1 st: pop out 30 = tmpst : push 30st: pop out 20 =tmpst： get the top element 30Since 30 20, tmpst :

5、 pop out 30st: push 30tmpst : push 202 st: pop out 30 =tmpst: get the top element 20 Since 20 tmpst： get the top element 30Since 30 15, tmpst : pop out 30st: push 30tmpst: get the top element 20Since 20 15, tmpst : pop out 20 st: push 20tmpst ： push 153 st: pop out 20 =tmpst： get the top element 15S

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

7、get the top element 10Since 10 tmpst: get the top element 15 Since 15 tmpst:get the topelement10Since 10 tmpst:get the topelement15Since 15 tmpst:get the topelement20Since 20 tmpst:get the topelement30Since 30 25, tmpst : i)op out 30st: push 30tmpst:get the topelement20Since 20 tmpst:get the topelem

8、ent25Since 25 30, exitthelooptmpst:push 30(2) the sorting of stack st endsthe popping sequence of st is : 10 15 20 25 30Process exited after 0. 08071 seconds with return value 0 请按任意键继续.完整代码：#include#include using namespace std;/基于堆栈的升序排序/从小到大，最小的元素在栈顶class Solution public:Solution(/* args */);Solut

9、ion。;static void sort_by_stack(stack &st); static void output (stack &st););Solution:Solution(/* args */) ( )Solution:Solution。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

10、st: pop out tmp =二 empty () tmpst-push(tmp);cout /ztttmpst : push tmp empty () int tmpst_top = tmpst-top();cout get the top element tmpst_top endl;if (tmp 数据栈栈顶元素/辅助栈栈顶元素出栈，压入数据栈tmpst-pop ();cout /ztttSince tmpst_top tmp ， tmpst : pop out tmpst_top endl;st.push (tmpst_top);cout /ztttst: push tmpst_t

11、op tmpst_top) /辅助栈栈顶元篆 数据栈栈顶元素/跳过当前循环，数据栈栈顶元素直接压入辅助栈cout z/tttSince tmpst_top tmp ，exit the loop” push(tmp);cout tttmpst : push tmp empty () int x = tmpst-top();tmpst-pop ();st. push (x);)void Solution:output(stack &st) while (!st. empty()(cout st. top() ；St. pop();cout endl;int main () stack *st =

12、new stack;cout push the elements ;/ int data3=10, 30, 40;/ for(int i = 0; i push(datai);/cout datai ；/ )int data5 = 25, 10, 15, 20, 30);for(int i = 0; i push(datai);cout datai ；cout onto the stack st. endl;cout the process of sorting elements of stack st is: endl;Solution:sort_by_stack(*st);cout the sorting of stack st ends” endl;cout the popping sequence of st is :;Solution:output(*st);return 0 ;