【UVa-514】铁轨——栈的学习

UVa514 Rails（铁轨）

题目：铁轨

题目链接： UVa514链接

题目描述：

某城市有一个火车站，有n节车厢从A方向驶入车站，按进站的顺序编号为1-n.你的任务是判断是否能让它们按照某种特定的顺序进入B方向的铁轨并驶入车站。例如，出栈顺序（5 4 1 2 3）是不可能的，但是（5 4 3 2 1）是可能的。

题目分析：

为了重组车厢，借助中转站，对于每个车厢，一旦从A移入C就不能回到A了，一旦从C移入B，就不能回到C了，意思就是A->C和C->B。而且在中转站C中，车厢符合后进先出的原则。故这里可以看做为一个栈。

【代码】

 #include<cstdio>

 #include<stack>

 using namespace std;

 const int N = ;

 int n, tar[N], A, B;

 int main()

 {

   while (scanf ("%d", &n), n)

   {

     while (scanf ("%d", &tar[]), tar[])

     {

       for (int i = ; i <= n; ++i)

         scanf ("%d", &tar[i]);

       stack<int> sta;

       A = B = ;

       bool ok = true;

       while (B <= n)

       {

         if (A == tar[B])

         {   ++A; ++B;   }

         else if (!sta.empty() && sta.top() == tar[B])

         {   sta.pop();  ++B;  }

         else if (A <= n)

           sta.push (A++);

         else

         {   ok = false;  break;  }

       }

       printf (ok ? "Yes\n" : "No\n");

     }

     printf("\n");

   }

   return ;

 }

【分析】

　　A代表A中当前待进站的第一辆火车

　　tar[B]代表出战序列中当前应该出站的火车

　　栈sta代表火车站（栈）

　　判断条件：

　　　　1.当A == tar[B]时，A进站马上出站，即表示当前序列可以实现

　　　　2.栈顶（车站中的末尾火车）与输入的出站序列比较，若相同，出站，并继续向下比较

　　　　3.以上若不成立，则将当前A压入栈中

　　　　4.出站序列不存在，即A > n，车站中仍有火车，说明输入的出站序列无法实现

【总结】

　　bool emply()  判断栈是否为空

　　void push()  将新元素压入栈中

　　void pop()  用于栈不为空时，弹出栈顶元素

　　void top()  用于取栈顶元素（但不删除）

　　STL的栈定义在头文件<stack>中，可以用“stack<int> s”声明