程序员代码面试指南 1.5：用一个栈实现另一个栈的排序

1、思路

使用一个辅助栈help来对原栈stk进行排序，在stk上执行pop操作，弹出的元素记为cur：

1. 若cur ≤ help.top()，则cur压入help栈中；

2. 若cur > hel.top()，则将help中元素逐一弹出并压入stk中，直到cur ≤ help.top()为止，再将cur压入help中；

3. 循环前两步操作，直到所有元素都压入help栈中，此时help栈中元素已经从小到大排列好，最后倒入stk栈中即可。

2、代码

#include <iostream>
#include <stack>

using namespace std;

void sortStack(stack<int>& stk)
{
    stack<int> help;        //辅助栈

    while (!stk.empty())
    {
        int cur = stk.top();
        stk.pop();

        while (!help.empty() && cur > help.top())   //步骤1与2
        {
            stk.push(help.top());
            help.pop();
        }
        help.push(cur);
    }

    while (!help.empty())   //将help栈元素倒入stk栈中
    {
        stk.push(help.top());
        help.pop();
    }
}

int main()
{
    int n;
    cin >> n;
    stack<int> stk;

    while (n -- )
    {
        int num;
        cin >> num;

        stk.push(num);
    }

    sortStack(stk);

    while (!stk.empty())
    {
        cout << stk.top() << " ";
        stk.pop();
    }

    return 0;
}