백준 - 10828번(스택)

문제)

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

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

 

입력)

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

 

출력)

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

---

이론)

• 스택이라는 자료구조를 통해 해결하는 문제이다.
• 스택은 입력과 출력이 한 곳에서 이루어 진다. (LIFO)
• 보통 함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법에서 활용된다.
• 밑에 풀이를 보면 알 수 있지만 두 가지 방법으로 문제를 해결하였다.
• 첫번째 방법은 스택 포인터(SP)를 활용 하여 배열의 기본함수를 사용한 방법이다.
• 두번째 방법은 연결리스트로 해결한 방법이다.

풀이1)

class Stack {
    constructor() {
        this.stack = [];
        //stack 포인터 => 해당 위치를 알고 있어야 하므로 기억하고 있는 '스택 포인터'가 필요.
        this.sp = -1;   
    };
    push(o) {
        this.stack[++this.sp] = o;
    };
    pop() {
        if (this.isEmpty(this.sp)) {
            return -1;
        }
        return this.stack.pop(this.sp--);
    };
    size() {
        return this.stack.length;
    }
    isEmpty() {
        return this.sp === -1 ? 1 : 0; //입력값이 최초와 같다면 true, 아니면 false;
    }
    top() {
        if (this.isEmpty(this.sp)) {
            return -1;
        }
        return this.stack[this.sp];
    }
}

풀이2)

const fs = require("fs");
const input = fs.readFileSync("dev/stdin").toString().split('\n');

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class Stack {
    constructor() {
        this.head = null;
        this.t = null;
    }

    createNode(data) { //node를 생성하는 함수
        return new Node(data);
    }

    empty() {
        return this.t === null ? 1 : 0;
    }
    push(data) {

        if (this.empty()) {
            this.head = this.createNode(data);
            this.t = this.head;
        } else {
            //head {data:m, next:c} 라는 객체를 pointer가 참조하도록 한다.
            let pointer = this.head;


            //pointer.next가 존재한다면 제일 꼭대기에 있는 것은 pointer.next 이다.
            while (pointer.next !== null) {
                pointer = poiter.next;
            }
            pointer.next = this.createNode(data);
            this.t = pointer.next;
        }
    };

    pop() {
        let popData;
        if (!this.empty()) {
            popData = this.t.data;
            let pointer = this.head;

            if (this.head === this.t) { //데이터가 하나라면
                this.head = this.t = null;
            } else {
                while (pointer.next !== this.t) {
                    pointer = pointer.next;
                }
                pointer.next = null; //마지막 노드와 연결을 끊음.
                this.t = pointer;
            }
            return popData;
        }
        return -1;
    }
    size() {
        if (this.empty === 1) return 0;
        let count = 0;
        let pointer = this.head;
        while (pointer !== null) {
            count++;
            pointer = pointer.next;
        }
        return count;
    }
    top() {
        if (!this.empty()) {
            return this.t.data;
        }
        return -1;
    }
}


const stack = new Stack();
let answer = '';
for (let i = 1; i <= input[0]; i++) {
    let [command, value] = input[i].trim().split(' ');
    switch (command) {
        case 'push':
            stack.push(value);
            break;
        case 'pop':
            answer += stack.pop();
            break;
        case 'size':
            answer += stack.size();
            break;
        case 'empty':
            answer += stack.empty();
            break;
        case 'top':
            answer += stack.top();
            break;
        default:
            break;
    }
    if (command !== 'push' && i != input[0]) answer += '\n';
}
console.log(answer);