当前位置: 代码迷 >> 综合 >> POJ1363 Rails(数据结构栈)
  详细解决方案

POJ1363 Rails(数据结构栈)

热度:98   发布时间:2024-01-16 13:57:47.0

题意:

一列火车从A站进入,B站开出,中间有一个站台,可以改变车厢顺序,原本是1~n,看输入的序列能否达到

要点:

就是模拟栈的压入弹出,如果栈顶元素对应的编号与输入的顺序一致就弹出,如果不一致就继续压入。最后如果栈是空的就说明顺序是合法的,否则不合法


15114206 Seasonal 1363 Accepted 164K 63MS C++ 646B 2016-01-27 16:51:39

代码如下:

1.普通数组建栈

#include<stdio.h>
#include<stdlib.h>
#define maxn 1005
int stack[maxn*2];
int top = -1;void push(int e)
{top++;stack[top] = e;
}
void pop()
{top--;
}
int is_empty()
{return top == -1;
}int main()
{int train[maxn];int n,i;while (~scanf("%d", &n),n){while (scanf("%d", &train[1]),train[1]){for (i = 2; i <= n; i++)scanf("%d", &train[i]);int num = 1;for (i=1; i <= n; i++){push(i);while (!is_empty() && stack[top] == train[num]){pop();num++;}		}if (num == n + 1)printf("Yes\n");elseprintf("No\n");top = -1;}printf("\n");}return 0;
}

2.使用C++中的STL

#include<cstdio>
#include<stack>
#include<string.h>
using namespace std;
const int maxn=1050;
stack<int> s; //利用C++中的STL建栈int main()
{int train[maxn];int n,i;while (~scanf("%d", &n),n){while (scanf("%d", &train[1]),train[1]){for (i = 2; i <= n; i++)scanf("%d", &train[i]);int num = 1;for (i=1; i <= n; i++){s.push(i);while (!s.empty() && s.top() == train[num]){s.pop();num++;}		}if (num == n + 1)printf("Yes\n");elseprintf("No\n");while (!s.empty())s.pop();   //每次使用完都要清空栈,不然上一次剩下的会干扰}printf("\n");}return 0;
}