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

使用堆栈按升序对元素进行排序，即使最小的元素成为堆栈的顶部元素。例如, 给定堆栈元素(从下到上)：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上核心代码：void Solution:sort_by_stack(stack<int> &st) stack<int> *tmpst = new stack<int>int index = 0;/数据栈不为空while(!st. empty() /获取数据栈栈顶元素int tmp = st. top ();/栈顶元素弹出st. pop();index+;cout << t << index << st: pop out << tmp << => << endl;/辅助栈为空，直接入栈if(tmpst->empty () tmpst-push(tmp);cout << /ztttmpst : push << tmp << endl; continue;)/辅助栈不为空，while(!tmpst->empty () int tmpst_top = tmpst->top ();cout << z，tttmpst: get the top element << tmpst_top << endl;if (tmp < tmpst_top) /辅助栈栈顶元素 > 数据栈栈顶元素/辅助栈栈顶元素出栈，压入数据栈tmpst->pop ();cout << tttSince << tmpst_top << > << tmp <<，tmpst : pop out << tmpst_top << endl;st.push(tmpst_top);cout << z/tttst: push << tmpst_top << endl; 一else if (tmp > tmpst_top) /辅助栈栈顶元素 < 数据栈栈顶元素/跳过当前循环，数据栈栈顶元素直接压入辅助栈cout << /ztttSince << tmpst_top << < << tmp << ，exit the loop” << endl;break;)/数据栈栈顶元素压入辅助栈tmpst->push(tmp);cout << /ztttmpst : push << tmp << endl;)/将数据从辅助栈依次放入数据栈while(!tmpst->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 : pop out 30st: push 30tmpst : push 202 st: pop out 30 =>tmpst: get the top element 20 Since 20 < 30, exit the looptmpst : push 30st: pop out 15 =>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 15Since 15 < 20, exit the looptmpst : push 204 st: pop out 30 =>tmpst： get the top element 20 Since 20 < 30, exit the looptmpst : push 30st: pop out 10 =>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： get the top element 10Since 10 < 15, exit the looptmpst : push 156 st: pop out 20 =>tmpst: get the top element 15 Since 15 < 20, exit the looptmpst : push 208 st： pop out 15 =>tmpst:get the topelement10Since 10 <15, exitthelooptmpst:push 159 ；st: pop out20 =>tmpst:get the topelement15Since 15 <20, exitthelooptmpst:push 2010st: pop out30 =>tmpst:get the topelement20Since 20 <30, exitthelooptmpst:push 3011st: pop out25 =>tmpst:get the topelement30Since 30 >25, tmpst : i)op out 30st: push 30tmpst:get the topelement20Since 20 <25, exitthelooptmpst:push 2512st: pop out30 =>tmpst:get the topelement25Since 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<iostream>#include<stack> using namespace std;/基于堆栈的升序排序/从小到大，最小的元素在栈顶class Solution public:Solution(/* args */);Solution。;static void sort_by_stack(stack<int> &st); static void output (stack<int> &st););Solution:Solution(/* args */) ( )Solution:Solution。void Solution:sort_by stack(stack<int> &st) (stack<int> *tmpst = new stack<int>int index = 0;/数据栈不为空while(!st. empty() /获取数据栈栈顶元素int tmp = st. top ();/栈顶元素弹出st. pop();index+;cout << t << index << st: pop out << tmp << =二 << endl;/辅助栈为空，直接入栈if (tmpst->empty () tmpst->push(tmp);cout << /ztttmpst : push << tmp << endl;continue;/辅助栈不为空，while(!tmpst->empty () int tmpst_top = tmpst->top();cout <<get the top element << tmpst_top <<endl;if (tmp < tmpst_top) /辅助栈鹿顶元素 > 数据栈栈顶元素/辅助栈栈顶元素出栈，压入数据栈tmpst->pop ();cout << /ztttSince << tmpst_top << > << tmp << ， tmpst : pop out << tmpst_top << endl;st.push (tmpst_top);cout << /ztttst: push << tmpst_top << endl;)else if (tmp > tmpst_top) /辅助栈栈顶元篆 < 数据栈栈顶元素/跳过当前循环，数据栈栈顶元素直接压入辅助栈cout << z/tttSince << tmpst_top << < << tmp << ，exit the loop” << endl;break;)/数据栈栈顶元素压入辅助栈tmpst->push(tmp);cout << tttmpst : push << tmp << endl;)/将数据从辅助栈依次放入数据栈while(!tmpst->empty () int x = tmpst->top();tmpst->pop ();st. push (x);)void Solution:output(stack<int> &st) while (!st. empty()(cout << st. top() << ；St. pop();cout << endl;int main () stack<int> *st = new stack<int>cout << push the elements ;/ int data3=10, 30, 40;/ for(int i = 0; i < 3; i+) /st->push(datai);/cout << datai << ；/ )int data5 = 25, 10, 15, 20, 30);for(int i = 0; i < 5; i+) st->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 ;