데이터 구조: 스택이란?

많은 컴퓨터 과학 기초 중에서 데이터 구조는 소프트웨어 개발자가 잘 알고 있어야 하는 필수 지식 주제 목록의 상단 근처에서 찾을 수 있습니다. 데이터 구조는 개발자가 많은 양의 데이터를 효율적으로 관리할 수 있도록 하며 선택한 데이터 구조에 따라 프로그램 또는 알고리즘을 선택합니다. 이것은 사용 중인 문제를 동반하는 문제와 함께 가장 일반적인 데이터 구조 중 일부에 대해 자세히 살펴보는 주간 시리즈가 될 것입니다.

먼저 스택입니다!

이제 스택이 무엇인지 궁금할 것입니다. 이 데이터 구조를 이해하는 가장 간단한 방법은 실제 예제로 쉽게 나타낼 수 있습니다. 부엌에 가서 접시가 들어 있는 캐비닛을 열면 저와 같은 경우가 아니라면 접시가 깔끔하게 쌓인 것을 볼 수 있을 것입니다. 여전히 식기세척기를 꺼내야 합니다 😆 이제 접시가 어떻게 끝났는지 생각해 보세요 이 스택에서 사용하고 필요할 때 제거하는 방법. 당신이 접시를 잡으러 갈 때 스택에 마지막으로 놓은 접시가 가장 먼저 제거될 가능성이 높습니다.

이것이 바로 스택 데이터 구조가 작동하는 방식이며 데이터 구조의 한쪽 끝에서만 작업을 허용합니다. 스택을 설명하는 두 개의 쉬운 약어: LIFO(후입선출) 및 FILO(선입선출). 스택의 작업을 참조할 때 삽입 작업을 푸시라고 하고 제거를 팝이라고 합니다.

이제 스택 데이터 구조를 사용하여 당면한 문제를 해결할 수 있는 문제를 살펴보겠습니다.

유효한 괄호

str , '(' , ')' , '{' , '}' , '[' 문자가 포함된 입력']'이 주어지면 주어진 문자열이 유효한지 확인합니다.

다음과 같은 경우 입력str이 유효합니다.

1. 여는 브래킷은 동일한 유형의 브래킷으로 닫힙니다. '()' => true , '(]' => false

2. 여는 브래킷이 올바른 순서로 닫힙니다. '([])' => true , '([)]' => false

str가 유효한 경우 true를 반환하고 그렇지 않으면 false를 반환합니다. 단순함을 위해 우리는 이 문제의 엣지 케이스에 대해 걱정하지 않을 것입니다.

const isValid = (str) => {
    let map = { ')': '(', '}': '{', ']': '[' };
    let stack = [];

    for (let i = 0; i < str.length; i++) {
        if (str[i] === '(' || str[i] === '{' || str[i] === '[') stack.push(str[i]);
        else if (map[str[i]] === stack[stack.length - 1]) stack.pop();
        else return false;
        console.log(stack);
    };
    return stack.length === 0;
};

isValid("{{}[][[[]]]}");

산출:

[ '{' ]
[ '{', '{' ]
[ '{' ]
[ '{', '[' ]
[ '{' ]
[ '{', '[' ]
[ '{', '[', '[' ]
[ '{', '[', '[', '[' ]
[ '{', '[', '[' ]
[ '{', '[' ]
[ '{' ]
[]
true

위의 isValid 함수에서 스택을 사용하여 접하는 특정 순서로 여는 대괄호를 추적합니다. 여는 대괄호를 만나면 스택에 push() (추가)합니다. 닫는 대괄호를 만나면 스택에 추가된 마지막 여는 대괄호가 현재 닫는 대괄호와 같은 대괄호 유형인지 확인합니다. 만약 그렇다면 스택에서 여는 대괄호를 제거합니다pop(). 스택에 추가된 마지막 여는 대괄호가 우리가 만난 닫는 대괄호와 같은 유형이 아니면 false를 반환합니다.

함수 실행의 결과 출력에서 ​​스택이 for 루프의 각 반복을 통해 FILO & LIFO 원칙을 준수하고 있음을 알 수 있습니다.

이것이 스택 데이터 구조를 더 잘 이해하는 데 도움이 되었기를 바랍니다. 스택을 활용할 수 있는 질문이나 기타 재미있는 문제가 있으면 아래 의견에 남겨주세요.

건배!