[Jobdu] 제목 1522: min 함 수 를 포함 하 는 스 택

5993 단어 job
제목 설명:
스 택 의 데이터 구 조 를 정의 합 니 다. 이 형식 에서 스 택 의 최소 요 소 를 얻 을 수 있 는 min 함 수 를 실현 하 십시오.
입력:
입력 은 여러 개의 테스트 샘플 을 포함 할 수 있 으 며, 입력 은 EOF 로 끝 납 니 다.모든 테스트 사례 에 대해 입력 한 첫 번 째 행 위 는 정수 n (1 < = n < = 1000000) 이 고 n 은 입력 할 작업 의 절차 수 를 대표 합 니 다.다음은 n 줄 이 있 고 줄 마다 알파벳 Ci 가 있 습 니 다.Ci = 's' 시 다음 숫자 k 가 있 습 니 다. 대 표 는 k 를 창고 에 넣 습 니 다.Ci = 'o' 시 스 택 상단 요 소 를 팝 업 합 니 다.
출력:
모든 테스트 사례 의 모든 작업 에 대응 하고 스 택 이 비어 있 지 않 으 면 해당 스 택 의 최소 요 소 를 출력 합 니 다.그렇지 않 으 면 NULL 을 출력 합 니 다.
샘플 입력:
7

s 3

s 4

s 2

s 1

o

o

s 0

샘플 출력:
3

3

2

1

2

3

0

간단 합 니 다. 하나의 스 택 으로 현재 의 최소 값 을 저장 합 니 다. 새 요소 가 현재 의 최소 값 보다 시간 이 적 으 면 min 스 택 에 들 어가 고 스 택 에서 나 올 때 스 택 꼭대기 요소 가 현재 의 최소 값 이 라면 min 스 택 에서 팝 업 됩 니 다.
 1 #include <iostream>

 2 #include <stack>

 3 #include <cstdio>

 4 using namespace std;

 5  

 6 int n, a;

 7 char ci;

 8  

 9 int main() {

10     //freopen("a.in", "r", stdin);

11     while (cin >> n) {

12         stack<int> s;

13         stack<int> min;

14         while (n--) {

15             cin >> ci;

16             if (ci == 's') {

17                 cin >> a;

18                 s.push(a);

19                 if (min.empty() || a < min.top())

20                     min.push(a);

21             } else if (ci == 'o') {

22                 if (s.top() == min.top()) 

23                     min.pop();

24                 s.pop();

25             }

26             if (min.empty())

27                 cout << "NULL" << endl;

28             else

29                 cout << min.top() << endl;

30         }

31     }

32     return 0;

33 }

34 /**************************************************************

35     Problem: 1522

36     User: hupo250

37     Language: C++

38     Result: Accepted

39     Time:120 ms

40     Memory:1524 kb

41 ****************************************************************/

좋은 웹페이지 즐겨찾기