스 택 의 push, pop 시퀀스 가 올 바른 지 여부

2043 단어 데이터 구조
제목: 두 개의 정수 서열 을 입력 하 십시오.그 중의 한 서열 은 창고 의 push 순 서 를 표시 하고 다른 서열 이 대응 하 는 pop 순서 일 수 있 는 지 판단 한다.간단하게 보기 위해 서, 우 리 는 push 서열 의 임의의 두 정수 가 모두 같 지 않다 고 가정한다.
예 를 들 어 입력 한 push 서열 이 1, 2, 3, 4, 5 라면 4, 5, 3, 2, 1 은 pop 시리즈 일 수 있 습 니 다.다음 과 같은 push 와 pop 서열 이 있 기 때 문 입 니 다. push 1, push 2, push 3, push 4, pop, push 5, pop, pop, pop, pop. 이렇게 얻 은 pop 서열 은 4, 5, 3, 2, 1 입 니 다.그러나 서열 4, 3, 5, 1, 2 는 push 서열 1, 2, 3, 4, 5 의 pop 서열 일 수 없다.
분석: 이 문 제 는 스 택 이라는 기본 데이터 구조 에 대한 이 해 를 시험 하 는 동시에 우리 의 분석 능력 도 시험 할 수 있다.구체 적 인 실현 코드 는 다음 과 같다.
/ / isStackPushPop. cpp: 콘 솔 프로그램의 입구 점 을 정의 합 니 다. /
#include "stdafx.h"
#include #include
using namespace std;
bool isStackPushPop(int a[], int b[], int n) {  stack ms;  int i = -1, j = 0;  while (i < n && j < n)  {   if (ms.empty() || ms.top() != b[j])    ms.push(a[++i]);   else   {    ms.pop();    j ++;   }  }  return ms.empty(); }
int main() {  int a[] = {1,2,3,4,5};  int b[] = {5,4,2,3,1};  //int b[]={4,5,3,2,1};  //int b[]={5,4,3,2,1};  cout< 
// isStackPushPop.cpp :              。
//

#include "stdafx.h"

#include <iostream>
#include <stack>

using namespace std;

bool isStackPushPop(int a[], int b[], int n)
{
	stack<int> ms;
	int i = -1, j = 0;
	while (i < n && j < n)
	{
		if (ms.empty() || ms.top() != b[j])
			ms.push(a[++i]);
		else
		{
			ms.pop();
			j ++;
		}
	} 
	return ms.empty();
}

int main()
{
	int a[] = {1,2,3,4,5};
	int b[] = {5,4,2,3,1};
	//int b[]={4,5,3,2,1};
	//int b[]={5,4,3,2,1};
	cout<<isStackPushPop(a, b, 5)<<endl;
	system("pause");
	return 0;
}



좋은 웹페이지 즐겨찾기