검 지 OFPER 에 min 함 수 를 포함 하 는 스 택 (9 도 OJ 1522)

제목 설명:
스 택 의 데이터 구 조 를 정의 합 니 다. 이 형식 에서 스 택 의 최소 요 소 를 얻 을 수 있 는 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

문제 풀이 방향:
창고 에 있 는 원소 가 손발 을 만 들 면 된다 는 것 을 쉽게 생각 할 수 있다.우 리 는 매번 두 개의 정 보 를 동시에 저장 합 니 다. 하 나 는 현재 요소 의 값 이 고 하 나 는 현재 의 최소 값 입 니 다.

typedef struct stack{

    int num;

    int min;

}Stack;

typedef struct arr{

    Stack s[1000000];

}Arr;

 
스 택 을 사용 하지 않 고 머리 에 꽂 힌 링크 를 사용 하 는 것 도 고려 할 수 있 습 니 다. 그러면 메모 리 를 절약 할 수 있 습 니 다.
코드:

#include <stdio.h>

#include <stdlib.h>

typedef struct stack{

    int num;

    int min;

}Stack;

typedef struct arr{

    Stack s[1000000];

}Arr;

int main(int argc, char const *argv[])

{

    int n,i,m;

    char c;

    while(scanf("%d",&n)!=EOF && n>=1 && n<=1000000){

        Arr *a = (Arr *)malloc(sizeof(Arr));

        int top = 0;

        for(i=0;i<n;i++){

            scanf("
%c",&c);

            if(c == 's'){

                scanf("%d",&m);

                if(top == 0){

                    a->s[top].min = m;

                }else{

                    a->s[top].min = (m<a->s[top-1].min?m:a->s[top-1].min);

                }

                a->s[top].num = m;

                top++;

                printf("%d
",a->s[top-1].min);

            }

            else{

                if(top > 1){

                    top--;

                    printf("%d
",a->s[top-1].min);

                }else{

                    top = 0;

                    printf("NULL
");

                }

            }

        }

    }

    return 0;

}

/**************************************************************

    Problem: 1522

    User: xhalo

    Language: C

    Result: Accepted

    Time:20 ms

    Memory:8728 kb

****************************************************************/