unit1.cpp

来自「一种排序算法」· C++ 代码 · 共 67 行

#include <fstream>
#include <stack>
#include <queue>

using namespace std;

ofstream cout("output.txt");

class StackedPerm
{
    queue<int> InQ, OutQ;
    stack<int> Stk;
    void Print()
    {
        while (!OutQ.empty())
        {
            cout << OutQ.front();
            OutQ.pop();
        }
        cout << endl;
    }
public:
    StackedPerm(int n = 0)
    {
        for (int i = 0; i < n; i++)
            InQ.push(i + 1);
    }
    void Generate();
};

void StackedPerm::Generate()
{
    if (InQ.empty())
    {
        while (!Stk.empty())
        {
            OutQ.push(Stk.top());
            Stk.pop();
        }
        Print();
    }
    else if (Stk.empty())
    {
        Stk.push(InQ.front());
        InQ.pop();
        Generate();
    }
    else
    {
        StackedPerm b = *this;
        OutQ.push(Stk.top());
        Stk.pop();
        Generate();
        b.Stk.push(b.InQ.front());
        b.InQ.pop();
        b.Generate();
    }
}

int main(int argc, char* argv[])
{
    StackedPerm p(5);
    p.Generate();
    return 0;
}