POJ 1363 레일 스 (데이터 구조 스 택)

2043 단어
제목:
한 열차 가 A 역 에서 들 어 오 면 B 역 이 나 오고 중간 에 플랫폼 이 하나 있어 서 객차 의 순 서 를 바 꿀 수 있 습 니 다. 원래 1 ~ n 이 었 는데 입력 한 서열 이 도달 할 수 있 는 지 볼 수 있 습 니 다.
요점:
스 택 의 압 입 팝 업 을 모 의 하 는 것 입 니 다. 스 택 상단 요소 에 대응 하 는 번호 가 입력 순서 와 일치 하면 팝 업 되 고 일치 하지 않 으 면 계속 누 르 는 것 입 니 다.마지막 으로 스 택 이 비어 있 으 면 순서 가 합 법 적 이라는 것 을 설명 한다. 그렇지 않 으 면 합 법 적 이지 않다.
15114206
Seasonal
1363
Accepted
164K
63MS
C++
646B
2016-01-27 16:51:39
코드 는 다음 과 같 습 니 다:
1. 일반 배열 창고 건설
#include
#include
#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
"); else printf("No
"); top = -1; } printf("
"); } return 0; }

2. C + + 의 STL 사용
#include
#include
#include
using namespace std;
const int maxn=1050;
stack 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
"); else printf("No
"); while (!s.empty()) s.pop(); // , } printf("
"); } return 0; }

좋은 웹페이지 즐겨찾기