하나의 시퀀스 가 스 택 의 팝 업 시퀀스 인지 판단 합 니 다.

4084 단어 알고리즘
두 개의 서열 을 정 하여 뒤의 서열 이 맞 는 지 판단 하 다.
첫 번 째 시퀀스 입 점 순서
데이터 구 조 를 배 운 사람 은 이런 문 제 를 많이 만 났 을 거 예요.
                1 2 3 4 5     
      4 5 3 2 1            

사고방식
먼저 스 택 서열 을 알 수 있 습 니 다. 4, 5, 3, 2, 1 의 첫 번 째 요 소 는 4 입 니 다. 즉, 스 택 에 들 어 갈 때 4 를 찾 은 다음 에 스 택 에서 5 를 계속 찾 아야 합 니 다. 하나의 스 택 으로 현재 의 스 택 요 소 를 저장 할 수 있 습 니 다.
예 를 들 어 4 에서 스 택 을 나 가 는 것 은 이때 스 택 에 1, 2, 3, 4, 123 이 4 앞 에 있 기 때문에 스 택 에서 아래 표 로 계속 표시 합 니 다.
순서        
조작 하 다.               
 스 택 요소            
팝 업 숫자  첫 번 째 는 4, 먼저 4 를 찾 아 라.
1
1 창고 에 넣다
 1
 
2
창고 에 넣다
 1 2
 
3
창고 에 넣다
1 2 3
 
4
창고 에 넣다
1 2 3 4
이때 스 택 상단 요 소 는 스 택 순서 의 첫 번 째 와 같 습 니 다. 찾 았 습 니 다. 다음 단 계 는 스 택 에서 이 요 소 를 꺼 내 는 것 입 니 다.
5
4 창고 에서 나오다
1 2 3
4 출고 순서 뒤로 이동, 5 지향 
6
창고 에 넣다
1 2 3 5
이때 스 택 상단 요 소 는 스 택 순서 의 첫 번 째 와 같 습 니 다. 찾 았 습 니 다. 다음 단 계 는 스 택 에서 이 요 소 를 꺼 내 는 것 입 니 다.
7
창고 에서 나오다
1 2 3
4 5 출고 후 이동  가리키다
8
창고 에서 나오다
1 2 
4 5 3. 스 택 꼭대기 요 소 는 스 택 요소
9
창고 에서 나오다
1
4 5 3 2 창고 꼭대기 원 소 는 스 택 요소
10
창고 에서 나오다
 
4 5 3 2 1 나 왔 습 니 다.  하면, 만약, 만약... 스 택 시퀀스 에 다른 것 이 없 으 면 true 라 고 표시 합 니 다.

#include
#include
using namespace std;

bool JudgeStackA_B(int *pushnumber,int *popnumber,int length)
{
        bool result=false;

        if(pushnumber!=NULL&&popnumber!=NULL&&length>0)
        {
            int *p=pushnumber;
            int *q=popnumber;
            stack<int> s;

            while(q-popnumberwhile(s.empty()||*q!=s.top())
                {
                    if(p-pushnumber==length)  //           
                        break;
                    s.push(*p);
                    p++;

                }

                if(s.top()!=*q)  //                             
                    break;
                s.pop();
                q++;
            }

            if(s.empty()&&q-popnumber==length)   
                result=true;
        }

        return result;


}

void main()
{
    int a[5]={1,2,3,4,5};
    int b[5]={4,5,2,3,1};

    if(JudgeStackA_B(a,b,5))
        printf("Yes
"); else printf("No
"); }

좋은 웹페이지 즐겨찾기