[Algorithm] 스택(Stack) 자료구조

1. Stack

 

스택은 한쪽에서만 데이터를 넣고 뺄 수 있는, 후입선출(LIFO) 형태의 자료구조를 말한다.

후입선출(Last In First Out)은 가장 먼저 들어간 것이 가장 나중에 나오는 것을 의미한다.

 

따라서 자바스크립트에서 스택을 구현하려면, 배열의 Push와 Pop을 사용하면 된다.

 

 

2. 예시

입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력하는 프로그램을 작성하세요.

function solution(s) {
    let answer = '';
    let stack = [];

    for (const x of s) {
        if (x === '(') stack.push(x);
        else if (x === ')') stack.pop();
        else {
            if (stack.length === 0) answer += x
        }
    }

    return answer;
}

let str = "(A(BC)D)EF(G(H)(IJ)K)LM(N)";
console.log(solution(str));

 

위 예제는 스택을 활용한 코딩테스트 문제이다.

괄호가 나오면 대부분 Stack을 사용한다고 생각하면 된다.

 

소괄호 사이에 있는 값들은 모두 제거하고 남은 값들만 출력해야 하기 때문에

괄호 안에 없는 값들만 answer에 추가해 준다.

 

string을 반복문으로 돌린 후, 괄호일 경우에만 스택에 넣어준다.

그리고 스택의 길이가 비었을 때, 스펠링이 들어오면 answer에 추가해 준다. 

(스택의 길이가 0이다 = 괄호 안에 있지 않다)