【栈】用一个栈实现对另一个栈的排序

题目：

一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈，除此之外可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

题解：

需要用到辅助栈。stack执行pop操作，弹出元素记为cur；

如果cur小于或等于assist的栈顶元素，则将cur直接压入assist；

如果cur大于assist的栈顶元素，则将assist的元素逐一弹出并压入stack，知道cur小于或等于assist的栈顶元素，再将cur压入assist

执行上述操作后，直到stack空，将assist所有元素逐一压入stack

Solution 1

#include<iostream>
#include<stack>
using namespace std;

void sortStack(stack<int> &s) {
    stack<int> assist;
    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        while (!assist.empty() && assist.top() < cur) {
            s.push(assist.top());
            assist.pop();
        }
        assist.push(cur);
    }
    while (!assist.empty()) {
        s.push(assist.top());
        assist.pop();
    }
}

int main()
{
    int n, num;
    cin >> n;
    stack<int> s;
    for (int i = 0; i < n; ++i) {
        cin >> num;
        s.push(num);
        cout << num << " ";
    }
    cout << endl;
    sortStack(s);
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;

    system("pause");
    return 0;
}