배열을 사용하면 모든 인덱스에서 요소를 추가하거나 제거할 수 있지만 때로는 항목 추가 및 제거를 더 잘 제어할 수 있는 데이터 구조가 필요합니다. 이 기사에서는 스택이 무엇인지 설명하고 스택을 사용하여 이러한 종류의 문제를 해결하는 방법과 구현 예를 제공합니다.

스택이란 무엇입니까?

스택은 LIFO(후입선출) 원칙을 따르는 정렬된 항목 모음입니다. 즉, 항목 추가 및 제거가 같은 끝에서 발생합니다. 최신 요소는 스택의 맨 위에 있고 가장 오래된 요소는 맨 아래에 있습니다. 스택을 책 더미 또는 브라우저 기록(브라우저의 뒤로 버튼)으로 생각할 수 있습니다.

스택의 장단점

스택은 요소를 추가하고 제거할 때 일정한 시간을 허용합니다. 스택에서 요소를 추가하고 제거하기 위해 요소를 이동할 필요가 없기 때문입니다.

스택의 단점은 배열과 달리 스택의 n번째 요소에 대한 지속적인 액세스를 제공하지 않는다는 것입니다. 이는 n이 스택의 요소 수인 요소를 검색하는 데 O(n) 시간이 걸릴 수 있음을 의미합니다.

배열 기반 스택 클래스 만들기

스택이 작동하는 방식을 배우고 이 필수 데이터 구조를 실험할 수 있는 좋은 방법이므로 이전에 해보지 않았다면 직접 시도해 보시기 바랍니다.

class Stack {
  constructor() {
    this.items = [];
  }
}

이 예에서는 스택의 요소를 저장하기 위해 배열을 사용하고 있습니다. 그러나 스택은 LIFO 원칙을 따르기 때문에 요소 삽입 및 제거에 사용할 수 있는 기능을 제한해야 합니다. Stack 클래스에서 다음 메서드를 사용할 수 있습니다.

push(element(s)) : 요소 하나(또는 여러 요소)를 스택 맨 위에 추가합니다.

pop() : 스택의 맨 위 요소를 제거하고 제거된 요소를 반환합니다.

peek() : 스택 자체를 수정하지 않고 스택의 맨 위 요소를 반환합니다.

isEmpty() : 스택에 요소가 포함되어 있지 않으면 true를 반환하고, 스택의 크기가 0보다 크면 false를 반환합니다.

clear() : 스택에서 모든 요소를 ​​제거합니다.

size() : 스택의 요소 수를 반환합니다(배열의 length 속성과 유사).
연습을 원하는 경우 위에서 언급한 방법을 직접 구현해 보시기 바랍니다. 스포일러를 원하지 않으시면 스크롤을 멈춰주세요!

class Stack {
    constructor() {
        this.items =[];
    }

    push(item) {
        return this.items.push(item);
    }

    pop() {
        return this.items.pop();
    }

    peek() {
        return this.items[this.length - 1];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    clear() {
        this.items = [];
    }

    size()  {
        return this.items.length;
    }
}

스택을 사용하여 문제 해결

스택은 다양한 실제 문제에 적용될 수 있습니다. 문제를 역추적하고, 수행한 경로를 기억하고, 작업을 실행 취소하는 데 사용할 수 있습니다. 한 가지 예를 살펴보고 아마도 HackerRank을 통해 다른 문제를 스스로 해결하도록 권장할 것입니다.

십진수를 이진수로 변환

10진수를 2진수로 변환하려면 나누기 결과가 0이 될 때까지 숫자를 2로 나눌 수 있습니다(2진수는 밑이 2인 숫자 시스템이므로). 예를 들면 다음과 같습니다.



다음은 스택을 사용하는 솔루션입니다.

function decimalToBinary(num) {
    const remStack = [];
    let number = num;
    let rem;
    let binaryString = '';

    while (number > 0) {
        rem = Math.floor(number % 2);
        remStack.push(rem);
        number = Math.floor(number / 2);
    }

    while (remStack.length !== 0) {
        binaryString += remStack.pop().toString();
    }

    return binaryString;
}

이 알고리즘에서 나눗셈 결과가 0이 아닌 동안 나눗셈의 나머지(modulo - mod)를 가져와서 스택에 푸시하고 2로 나눌 수를 업데이트합니다. 그런 다음 요소에서 요소를 팝합니다. 비어 있을 때까지 스택하고 스택에서 제거된 요소를 문자열로 연결합니다.

결론

이번 글에서는 스택 데이터 구조에 대해 알아보고, 배열을 이용하여 스택을 표현하는 자체 알고리즘을 구현하고, 연습 문제를 풀어보았습니다. 자세히 알아보려면 다음 리소스 중 일부를 확인하는 것이 좋습니다.

How to Implement a Stack freeCodeCamp

의 Prashant Yadav 작성

Stacks in JavaScript 교과서, Learning JavaScript Data Structures and Algorithms

에서 Loiane Groner 작성