[BOJ] 10828 스택, 전방선언

1. 문제 링크

https://www.acmicpc.net/problem/10828

2. 해설

이 문제는 간단하게 Stack을 구현하는 문제이다.

스택에 대한 설명은 http://compasstree934.tistory.com/7?category=676159 에 있다.

스택에서 push, pop, size, empty, top 이 5가지 메소드들을 구현하는 문제이다.

필자는 두 가지 방법으로 풀었다. 하나는 배열을 이용한 풀이, 또 하나는 linked list를 이용한 풀이.

둘의 차이와 장단점은 설명 링크에 적어놓았다.

배열을 사용해서 구현

1. stack이라는 배열과 stack_size라는 정수 변수를 선언한다.

2. 0-베이스를 사용할 것이므로 stack_size는 0으로 초기화한다.

3. push는 stack_size 값의 index에 해당하는 stack 배열에 집어 넣고, stack_size를 하나 늘려주면 된다.

ex) 비어 있는 상태, stack_size == 0 일 때, push(1) 을 해주면 stack[0] = 1, stack_size == 1 이렇게 된다.

4. pop은 stack_size만 하나 줄여주면 된다. 어차피 원래 있던 값은 나중에 덮여 씌워질 예정이므로 0으로 만들어 줄 필요가 없다.

5. size 는 간단히 stack_size만 리턴해주면 된다.

6. empty 도 !stack_size를 리턴해주면 0이면 true고 아니라면 false를 리턴해준다.

7. top은 가장 최근에 넣은 값이므로 stack_size보다 하나 작은 index에 있는 값을 리턴해주면 된다.

linked list를 사용해서 구현

1. 하나하나는 전부 node라는 struct로 구성된다.

2. stack_size는 0으로 초기화 해서 push될 대 +1, pop될 때 -1 을 해준다.

3. push는 새로운 node를 만들어서 nodePointer인 topPointer위에 연결하고, top을 새로운 노드로 해준다.

4. pop은 topPointer을 delete해준다.

5. top은 topPointer에 있는 값을 리턴한다.

6. size, empty는 위와 동일하다.

3. 소스 코드

1. 배열을 사용한 풀이

#include<iostream>
using namespace std;

class stack{
private:
    int stack[1000000]={0};
    int stack_size=0;
public:
    void push(int x){
        stack[stack_size++] = x;
    }
    void pop(){
        stack_size--;
    }
    int top(){
        return stack[stack_size-1];
    }
    bool empty(){
        return !stack_size;
    }
    int size(){
        return stack_size;
    }
};

int main(){
    int t;
    stack s;
    scanf("%d", &t);
    while (t--) {
        char arr[6]={0}; scanf("%s", arr);
        if (arr[0] == 'p' && arr[1] == 'u') {
            int x; scanf("%d", &x);
            s.push(x);
        }
        else if(arr[0] == 'p' && arr[1] == 'o'){
            if (s.empty()) {
                printf("-1\n");
            }
            else{
                printf("%d\n", s.top());
                s.pop();
            }
        }
        else if(arr[0] == 's'){
            printf("%d\n", s.size());
        }
        else if(arr[0] == 'e'){
            printf("%d\n", s.empty() ? 1 : 0);
        }
        else{
            if (s.empty()) {
                printf("-1\n");
            }
            else{
                printf("%d\n", s.top());
            }
        }
    }
    
    return 0;
}

2. linked list를 이용한 풀이 (main문은 위와 동일하다)

#include<iostream>
using namespace std;

typedef struct node *nodePointer;
struct node{
    int value;
    nodePointer link;
    node(int value){
        this->value = value;
        this->link = nullptr;
    }
};

class stack{
private:
    int stack_size=0;
    
    void makeNode(nodePointer *top, int x){
        nodePointer temp = new node(x);
        if (*top != nullptr) {
            temp->link = *top;
        }
        *top = temp;
    }
    void deleteNode(nodePointer *top){
        nodePointer prevTop = *top;
        *top = (*top)->link;
        delete prevTop;
    }
public:
    nodePointer topPointer = nullptr;
    void push(int x){
        stack_size++;
        makeNode(&topPointer, x);
    }
    void pop(){
        stack_size--;
        deleteNode(&topPointer);
    }
    int top(){
        return topPointer->value;
    }
    bool empty(){
        return !stack_size;
    }
    int size(){
        return stack_size;
    }
};

4. 추가 언급

두 번째 코드는 linked list로 작동하는데 우리가 일반적으로 아는 node를 만들고 사용한 것을 볼 수 있다. 조금 특이한 점을 본다면 node의 포인터를 nodePointer라고 따로 선언을 해준 것 정도로 볼 수 있겠다. 그런데 밑의 코드를 보면 

typedef struct node *nodePointer;
struct node{
    int value;
    nodePointer link;
    node(int value){
        this->value = value;
        this->link = nullptr;
    }
};

이렇게 typedef가 node의 선언보다 더 앞서있다. 이게 어떻게 가능한 것일까?

이는 지금은 자세하게 다루지는 않겠지만 전방선언(forward declaration)이라는 것으로 가능하게 된다.

불완전한 형을 선언해서 나중에 형이 완성되는 것을 전방 선언이라고 한다. 헤더를 적게 include해서 컴파일 시간을 줄일 때도 쓰이고, 서로를 참조하는 상황이 벌어졌을 때 사용되기도 한다.

더 자료를 알고 싶다면 영어 위키 https://en.wikipedia.org/wiki/Forward_declaration 에 들어가서 글을 읽어보길 바란다.