算法笔记（c++）--使用一个辅助栈排列另一个栈　　

---

仅仅使用一个辅助栈，不使用其他数据结构来排列一个栈，要求，上大下小。

分析下。肯定是先吧主栈中的数据都放到辅助栈中，在辅助栈中上小下大。

1.首先循环提取主栈中的top，如果辅助栈为空就直接放进去，如果比辅助栈顶小也直接放进去，如果比辅助栈顶大就把辅助站中元素一个个弹到主栈中，直到找到比栈顶小或者栈为空就放进去。

代码如下：

#include<iostream>

#include<queue>

#include<string>

#include<stack>

using namespace std;

void reverse(stack<int>& s)

{

    stack<int> temp;

    while(!s.empty())

    {

        int top=s.top();

         s.pop();

         if(temp.empty())//如果是空直接放进去

             temp.push(top);

         else if(temp.top()>top)//如果temp.top大也直接放进去

             temp.push(top);

         else

         {

             while(!temp.empty()&&temp.top()<top)//注意这里，这里必须要empty在前不然会引发top异常

             {

                    int t=temp.top();

                    temp.pop();

                    s.push(t);

             }

             temp.push(top);

         }

    }

    while(!temp.empty())

    {

        int mm=temp.top();

        temp.pop();

        s.push(mm);

    }

}

int main()

{

    stack<int> a;

    for(int i=;i>=;i--)

    {

        a.push(i);

    }

    reverse(a);

    for(int i=;i>=;i--)

    {

        cout<<a.top();

        a.pop();

    }

    return ;

}