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

지금까지 자료 구조를 논할 때는 주로 자료 구조에 따라 다양한 연산의 성능이 어떻게 달라지는가에 초점을 맞췄다. 하지만 프로그래밍 지식 창고에 다양한 자료 구조를 쌓아 두면 보다 간단하고 읽기 쉬운 코드를 생성하는 데 도움이 된다.

 

스택과 큐는 제약을 갖는 배열이다. 이러한 제약 덕분에 두 자료 구조가 매우 간결해진다.

스택과 큐는 임시 데이터를 처리할 수 있는 간결한 도구다. 다양한 분야에서 사용해 뛰어난 알고리즘을 만들 수 있다.

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 스택 다뤄보기

오래 사용할 데이터가 아닌 임시 데이터를 다뤄야 하는 다양한 알고리즘에서는 스택이 유용한 도구다.

자바스크립트 린터, 즉 프로그래머가 작성한 자바스크립트 코드를 검사해서 각 줄이 문법적으로 올바른지 확인하는 프로그램의 시작 부분을 여는 괄호와 닫는 괄호에만 초점을 맞춰서 만들어보자.

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

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

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

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

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

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

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 사고방식에 입각해 린터 같은 종류의 문제를 풀 수 있다.
• 스택과 LIFO 속성을 제대로 이해해서 작성한 코드는 가독성이 좋다. 알고리즘에 쓰인 스택을 발견하는 순간 그 알고리즘이 LIFO 기반 프로세스로 동작함을 알게 된다.

9.4.1 스택 요약

스택은 마지막에 들어 온 데이터부터 먼저 처리해야 할 때 이상적이다.

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]
  }
}

Queue 클래스는 정해진 방식으로만 데이터를 처리하도록 데이터와의 상호작용을 제한하는 인터페이스로 배열을 감싼다.

9.6 큐 다뤄보기

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

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)
  }
}

이 예제는 단순화됐고 실제 출력 시스템이 다뤄야 할 핵심 기능을 추상화하기도 했지만 이러한 애플리케이션은 필수적으로 큐를 사용한다.

큐는 요청받은 순서대로 요청을 처리하므로 비동기식 요청을 처리하는 완벽한 도구이기도 하다.

9.7 마무리

스택과 큐는 실용적인 알고리즘을 간결하게 처리할 수 있는 프로그래머의 도구다.