문제 주소

이번 기회에 백준 문제풀었던 걸 복기하기 위해 작성을 시작했습니다!!
같이 열심히 백준 풀어봅시다!

이 문제에 대해 간단히 알아봅시다:)

다음과 같은 기능을 구현하는 스택입니다.

push X: 정수 X를 스택에 넣는 연산
pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다.
만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력
size: 스택에 들어있는 정수의 개수를 출력
empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

1. 스택 구조란?

스택 구조는 흔히 말하는 FILO(First In, Last Out), 즉 선입후출 구조입니다.

위와 같은 스택 구조는 기본적으로 일직선 적인 구조라 선형구조입니다.
그래서 스택을 배열과 연결 리스트 두 가지 방식으로 짤 수 있습니다.

typedef struct StackNode {
    element data;
    struct StackNode* link;
}stack;

위의 코드는 간단한 스택의 리스트형 구조입니다.
노드끼리 연결해주는 포인터와 데이터입니다. 연결리스트의 기본 요소니 기억해주세요

마지막 부분은 TOP으로 잡겠습니다. 나가는 출구 및 입구!

2. 스택 각 기능 구현

스택에서 필요한 것은 딱 두가지 선형 구조와 어디가 마지막인지 알려주는 탑 입니다.

push :
새로운 노드를 생성하고 데이터를 저장합니다.
새 노드의 link를 현재 TOP으로 설정!
pop:
1. 스택이 비어있는 경우 -1을 반환합니다.
2. 스택의 모든 노드를 순회.
size: 스택에 들어있는 정수의 개수를 출력
empty: 스택이 비어있으면 1, 아니면 0을 출력
top: 스택이 비어있으면 -1을, top인덱스가 가르키는 노드의 데이터를 반환

3. 답안 코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef int element;

typedef struct StackNode {
    element data;
    struct StackNode* link;
}stack;

void push(element x);
element pop(void); // no top = -1
int size(void);
int empty(void); //empty == 1, not empty == 0
element top(void); // no top = -1

stack* TOP;

int main()
{
    int n;
    char cmd[6];
    int cnt = 0;

    TOP = NULL;

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%s", cmd);
        getchar();

        if (!strcmp(cmd, "push")) {

            element input;
            scanf("%d", &input);

            push(input);
            continue;
        }

        else if (!strcmp(cmd, "pop")) {
            printf("%d\n", pop());
            continue;
        }

        else if (!strcmp(cmd, "size")) {
            printf("%d\n", size());
            continue;
        }

        else if (!strcmp(cmd, "empty")) {
            printf("%d\n", empty());
            continue;
        }

        else if (!strcmp(cmd, "top")) {
            printf("%d\n", top());
            continue;
        }
    }

    return 0;
}

void push(element x) {
    stack* tmp = (stack*)malloc(sizeof(stack));

    tmp->link = TOP;
    tmp->data = x;
    TOP = tmp;

    return;
}
element pop(void) {
    if (empty()) return -1;
    else {
        stack* old = TOP;

        TOP = old->link;
        element tmp = old->data;
        free(old);
        return tmp;
    }
}
int size(void) {
    stack* tmp = TOP;
    int cnt = 0;

    while (tmp) {
        cnt++;
        tmp = tmp->link;
    }
    return cnt;
}
int empty(void) {
    if (TOP == NULL) {
        return 1;
    }
    else {
        return  0;
    }
}
element top(void) {
    if(empty()) return -1;
    else {
        return (TOP->data);
    }
}