9장 스택과 큐로 간결한 코드 생성

김현수·2022년 2월 15일

누구나 자료 구조와 알고리즘

목록 보기

9/20

지금까지는 자료 구조에 따라 연산의 성능이 어떻게 달라지는가에 초점을 맞췄다.
스택과 큐는 제약을 갖는 배열이다. 제약 덕분에 두 자료 구조가 매우 간결해진다.
스택과 큐는 임시 데이터를 처리할 수 있는 간결한 도구로, 다양한 분야에서 사용해 뛰어난 알고리즘을 만들 수 있다.
임시 데이터는 처리 후에는 의미 없는 정보이므로 다 쓴 후에는 버려도 된다.

9.1 스택

스택에는 세 가지 제약이 있다.

데이터는 스택의 끝에만 삽입할 수 있다.
데이터는 스택의 끝에서만 삭제할 수 있다.
스택의 마지막 원소만 읽을 수 있다.

스택의 끝을 위(top), 스택의 시작을 밑(bottom)이라고 부른다.

스택에 새 값을 삽입하는 것을 스택에 푸시한다고 하고, 스택의 위에서 원소를 제거하는 것을 스택으로부터 팝한다고 한다.

스택 연산은 LIFO(Last In, First Out)이다.
즉, 스택에 푸시된 마지막 항목이 스택에서 팝될 첫 번째 항목이라는 의미다.

9.2 추상 데이터 타입

대부분의 프로그래밍 언어에는 스택이 내장 데이터 타입이나 클래스로 딸려 있지 않다. 직접 구현해야 한다.

class Stack {
  constructor() {
    this._data = [];
  }
  push(item) {
    this._data.push(item);
  }
  pop() {
    return this._data.pop();
  }
  read() {
    return this._data[this._data.length - 1];
  }
}

이 스택 구현은 _data라는 배열에 데이터를 저장한다.

배열을 기반으로 Stack 클래스를 만들다 보니 사용자가 배열과 상호작용하는 인터페이스가 제한적이다. 원래 배열은 어떤 인덱스든 정상적으로 읽을 수 있으나, 스택 인터페이스로 배열을 사용하면 마지막 항목만 읽고, 삽입하고, 삭제할 수 있다.

사실 스택은 꼭 배열로만 만들어야 하는 것은 아니다. LIFO 방식으로 동작하는 데이터 원소들의 리스트면 된다. 그래서 스택은 추상 데이터 타입에 속한다.

9.3 스택 다뤄보기

임시 데이터를 다뤄야 하는 다양한 알고리즘에서는 스택이 유용한 도구다.

자바스크립트 린터의 시작 부분을 여는 괄호와 닫는 괄호에만 초점을 맞춰서 만들어보자.

문법 오류는 세 가지 상황에서 발생한다.

여는 괄호는 있는데 닫는 괄호가 없는 경우
- (var x = 2;
여는 괄호가 앞에 나오지 않았는데 닫는 괄호가 나오는 경우
- var x = 2);
닫는 괄호가 바로 앞에 나온 여는 괄호와 종류가 다를 경우
- (var x = [1, 2, 3)]
- 소괄호끼리 대응하는 쌍이 있고, 대괄호끼리 대응하는 쌍이 있는데, 닫는 괄호가 앞의 대괄호와 일치하지 않으므로 위치가 틀렸다.

빈 스택을 준비해서 규칙에 따라 각 문자를 왼쪽부터 오른쪽 방향으로 읽는다.

괄호가 아닌 모든 문자는 무시하고 넘어간다.
여는 괄호가 나오면 스택에 푸시한다. 스택에 넣는다는 것은 이 괄호가 닫히기를 기다린다는 의미다.
닫는 괄호가 나오면 스택 위의 원소를 팝해서 확인한다.
- 팝한 항목이 현재 닫는 괄호와 종류가 다르면 오류 3번이다.
- 스택이 비어 팝할 수 없으면 닫는 괄호에 대응하는 여는 괄호가 앞에 안 나온 것이다. 오류 2번이다.
- 팝한 항목이 현재 닫는 괄호와 종류가 같다면 계속 진행한다.
줄 끝에 도달했는데 스택에 괄호가 남아있다면 오류 1번이다.

(var x = {y: [1, 2, 3]})을 왼쪽부터 오른쪽으로 읽기 시작한다.

첫 번째 글자는 (이다.
여는 괄호이므로 스택에 푸시한다. var x =는 괄호가 아니므로 무시한다.
다음 여는 괄호는 {다.
스택에 푸시한다. y:는 무시한다.
다음 여는 괄호는 [다.
스택에 푸시한다. 1, 2, 3은 무시한다.
닫는 괄호 ]가 나왔다.
스택 위에서 원소를 팝하니 [가 나왔다. 닫는 괄호와 스택에서 팝한 원소의 괄호 종류가 같으니 오류 없이 알고리즘을 이어갈 수 있다.
닫는 괄호 }가 나왔다.
스택 위에서 원소를 팝하니 {가 나왔다. 닫는 괄호와 스택에서 팝한 원소의 괄호 종류가 같다.
닫는 괄호 )가 나왔다.
스택 위에서 원소를 팝하니 (가 나왔다. 닫는 괄호와 스택에서 팝한 원소의 괄호 종류가 같다.
코드 줄을 전부 살펴봤고 스택이 비어있으므로 린터는 이 줄에 괄호와 관련된 문법적 오류가 없다고 결론내릴 수 있다.

9.3.1 코드 구현: 스택 기반 코드 린터

class Stack {
  constructor() {
    this._data = [];
  }
  push(item) {
    this._data.push(item);
  }
  pop() {
    return this._data.pop();
  }
  read() {
    return this._data[this._data.length - 1];
  }
}

class Linter extends Stack {
  lint(text) {
    for (let i = 0; i < text.length; i++) {
      if (this.isOpeningBrace(text[i])) {
        super.push(text[i]);
      } else if (this.isClosingBrace(text[i])) {
        let poppedOpeningBrace = this.pop();

        if (!poppedOpeningBrace) {
          return `${text[i]} doesn't have opening brace`;
        }

        if (this.isNotAMatch(poppedOpeningBrace, text[i])) {
          return `${text[i]} has  mismatched opening brace`;
        }
      }
    }
    if (super.read()) {
      return `${super.read()} does not have closing brace`;
    }

    return true;
  }

  isOpeningBrace(char) {
    return ["(", "{", "["].includes(char);
  }

  isClosingBrace(char) {
    return [")", "}", "]"].includes(char);
  }

  isNotAMatch(openingBrace, closingBrace) {
    return closingBrace !== { "(": ")", "{": "}", "[": "]" }[openingBrace];
  }
}

9.4 제약을 갖는 데이터 구조의 중요성

스택이 제약을 갖는 배열일 분이라면 스택이 하는 일은 배열도 할 수 있다.

스택, 큐처럼 제약을 갖는 데이터 구조는 다음과 같은 이유로 중요하다.

제약을 갖는 데이터 구조를 사용하면 잠재적 버그를 막을 수 있다.
9.3.1의 린팅 알고리즘을 사용하면서 배열의 중간에서 항목을 제거하면 알고리즘이 고장난다. 스택 위 항목을 제외하고는 삭제할 수 없으므로, 스택을 사용하면 위에서만 항목을 제거하게 되고 알고리즘이 고장나는 것을 막을 수 있다.
문제를 해결하는 새로운 사고 모델을 제공한다. 스택을 사용하면 LIFO 사고방식에 입각해 린터 같은 종류의 문제를 풀 수 있다.

9.4.1 스택 요약

스택은 마지막에 들어온 데이터부터 먼저 처리해야 할 때 이상적이다. Ctrl + Z 동작이 스택의 훌륭한 활용 사례다.

9.5 큐

큐 역시 임시 데이터를 처리하기 위해 디자인된 데이터 구조로, 데이터를 처리하는 순서만 제외하면 많은 면에서 스택과 비슷하다.

큐는 First In First Out의 약자인 FIFO로 표현한다. 주로 가로로 묘사 되며, 큐의 시작을 앞(front), 큐의 끝을 뒤(back)이라고 부른다.

큐에는 세 가지 제약이 있다.

데이터는 큐의 끝에만 삽입할 수 있다.
데이터는 큐의 앞에서만 삭제할 수 있다.
큐의 앞에 있는 원소만 읽을 수 있다.

9.5.1 큐 구현

class Queue {
  constructor() {
    this._data = [];
  } 
  enqueue(element) {
    this._data.push(element);
  }
  dequeue() {
    this._data.shift();
  }
  read() {
    return this._data[0]
  }
}

9.6 큐 다뤄보기

프린터가 네트워크 상에 있는 여러 컴퓨터로부터 출력 잡(job)을 받아들일 수 있도록 프로그래밍 한다. 요청 받은 순서대로 각 문서를 출력하도록 한다.

class Queue {
  constructor() {
    this._data = [];
  } 
  enqueue(element) {
    this._data.push(element);
  }
  dequeue() {
    return this._data.shift();
  }
  read() {
    return this._data[0]
  }
}

class PrintManager extends Queue {
  queuePrintJob(document) {
    super.enqueue(document)
  }
  run() {
    while (super.read()) {
      this.print(super.dequeue())
    }
  }
  print(document) {
    console.log(document)
  }
}