스 택 시퀀스 문제 요약

최근 데이터 구조 에 관 한 지식 을 복습 하면 서 스 택 시퀀스 에 관 한 문제 가 많이 발생 했다.
  대체적으로 이미 알 고 있 는 요소 의 스 택 서열 을 구 한 다음 에 스 택 서열 을 구 하 는 것 이다.예 를 들 어 스 택 에 들 어 가 는 것 이 1, 2, 3, n 인 다음 에 가능 한 스 택 시퀀스 수 를 구하 고 정확 한 스 택 시퀀스 인지 판단 합 니 다.
  다음은 내 가 만난 두 가지 문제 다.
묘사 하 다.
닝 닝 이 고려 한 것 은 다음 과 같은 문제 이다. 하나의 조작 수 서열 은 1, 2 에서 n 까지 이 고 창고 A 의 깊이 는 n 보다 크다.
현재 두 가지 조작 을 진행 할 수 있 습 니 다.
 
1. 하나의 수 를 조작 수 시퀀스 의 헤드 에서 스 택 의 헤드 로 이동 합 니 다 (데이터 구조 스 택 에 대응 하 는 push 작업)
2. 스 택 의 끝 에서 출력 시퀀스 의 끝 으로 숫자 를 이동 합 니 다 (데이터 구조 에 대응 하 는 pop 작업)
 
이 두 가지 조작 을 사용 하면 하나의 조작 수 서열 에서 일련의 출력 서열 을 얻 을 수 있 습 니 다. 다음은 1, 2, 3 에서 2, 3, 1 의 과정 을 이유 로 합 니 다.
 
동작 수: 1, 2, 3
창고:
출력 단자:
 
동작 수: 23
창고: 1 (창고 바닥)
출력 단자:
 
동작 수: 3
창고: 21 (창고 바닥)
출력 단자:
 
동작 수: 3
창고: 1 (창고 바닥)
출력 단자: 2
 
동작 수:
창고: 3 1 (창고 바닥)
출력 단자: 2
 
동작 수:
창고: 1 (창고 바닥)
출력 단자: 23
 
동작 수:
창고:
출력 단자: 23 1
 
현재 임의의 N 에 대해 입력 단의 데 이 터 는 반드시 1, 2, 3... N 입 니 다.
임의의 서열 에 대해 규칙 에 따라 이러한 서열 을 만 들 수 있 습 니까?
입력
첫 번 째 줄 은 정수 n (n < = 1000) 을 포함 하고 수열 의 길 이 를 표시 하 며 두 번 째 줄 은 n 개의 수 a1, a2,..., an 을 포함 하여 기대 순 서 를 표시 합 니 다.(a1，a2，…，an) ∈ Permutation{1, 2, …, n}
 
출력
만족 할 수 있다 면 Yes 를 출력 하 십시오. 그렇지 않 으 면 No 를 출력 합 니 다.
샘플 입력

5

1 2 3 5 4

샘플 출력

Yes

이 문제 풀이 사상 은 스 택 시퀀스 i 에 있 는 요소 A [i], i 위치 에 있 는 요소 입 니 다. A [i] 보다 작은 요소 가 존재 하면 내림차 순 으로 배열 해 야 합 니 다. 그렇지 않 으 면 오류 가 발생 합 니 다. 

#include "stdio.h"

int main()
{
	int num;
	int *A;
	int i,j,total;
	int max=0;
	int flag=0;

	int wrong =0;
	int temp,k;
	while(scanf("%d",&num)!=EOF)
	{
		A =(int *)malloc(sizeof(int)*num);
		for(i=0;iif(A[k]/ * A [i] 후의 요 소 를 확보 하고 A [i] 보다 작은 일정한 내림차 순 으로 배열 합 니 다 * /
{
if(A[k]
}
}
if(wrong==1)
{
printf("No");
break;
}
}
if(wrong==0)
printf("Yes");
free(A);
}
return 0;
}

다음 문 제 는 가능 한 스 택 시퀀스 를 구 하 는 것 입 니 다.
묘사 하 다.
닝 닝 이 고려 한 것 은 다음 과 같은 문제 이다. 하나의 조작 수 서열 은 1, 2 에서 n 까지 이 고 창고 A 의 깊이 는 n 보다 크다.
현재 두 가지 조작 을 진행 할 수 있 습 니 다.
 
1. 하나의 수 를 조작 수 시퀀스 의 헤드 에서 스 택 의 헤드 로 이동 합 니 다 (데이터 구조 스 택 에 대응 하 는 push 작업)
2. 스 택 의 끝 에서 출력 시퀀스 의 끝 으로 숫자 를 이동 합 니 다 (데이터 구조 에 대응 하 는 pop 작업)
 
이 두 가지 조작 을 사용 하면 하나의 조작 수 서열 에서 일련의 출력 서열 을 얻 을 수 있 습 니 다. 다음은 1, 2, 3 에서 2, 3, 1 의 과정 을 이유 로 합 니 다.
 
동작 수: 1, 2, 3
창고:
출력 단자:
 
동작 수: 23
창고: 1 (창고 바닥)
출력 단자:
 
동작 수: 3
창고: 21 (창고 바닥)
출력 단자:
 
동작 수: 3
창고: 1 (창고 바닥)
출력 단자: 2
 
동작 수:
창고: 3 1 (창고 바닥)
출력 단자: 2
 
동작 수:
창고: 1 (창고 바닥)
출력 단자: 23
 
동작 수:
창고:
출력 단자: 23 1
 
현재 임의의 N 에 대해 입력 단의 데 이 터 는 반드시 1, 2, 3... N 입 니 다.
나타 날 수 있 는 출력 단 데이터 시퀀스 의 종 수 를 구하 십시오.
 
입력
첫 번 째 행 위 는 T 조 데이터 가 있 음 을 나타 내 는 숫자 T 입 니 다.
각 조 의 데 이 터 는 하나의 정수 n (1 ≤ n ≤ 9) 만 포함 합 니 다.
출력
각 그룹의 데이터 에 대해 출력 이 얻 을 수 있 는 출력 시퀀스 의 총 항목
샘플 입력

1
3

샘플 출력

5

이 문제 의 풀이 방향 은 바로 재 귀 를 이용 하 는 것 이다. 모든 요 소 는 창고 에 한 번 만 들 어 갈 수 있 기 때문에 모든 요소 가 창고 에 들 어간 후에 이 상황 의 횟수 를 통계 하 는 것 이다.

#include "stdio.h"
int sum;
void dfs(int top,int head,int n)
{
	if(head==n+1)
	{
		sum++;
		return;
	}
	if(top>0)
	{
		dfs(top-1,head,n); /*     ，   */
	}
	if(head

물론 제목 이 많이 바 뀌 었 으 니 창고 의 성격 을 잘 파악 한 후에 먼저 나 가면 된다.이렇게 하면 우리 가 문 제 를 푸 는 이기 가 될 거 야.