CS) 자료구조 스택(Stack)

김명성·2023년 6월 14일

지금까지 자료 구조를 논할 때는 주로 자료 구조에 따라 다양한 연산의 성능이 어떻게 달라지는가에 초점을 맞췄다.

하지만 프로그래밍 지식 창고에 다양한 자료 구조를 쌓아두면 보다 간단하고 읽기 쉬운 코드를 생성하는 데 도움이 된다.

이번에 배울 자료구조는 스택이다

사실 스택이나 뒤에서 배울 큐 모두 새로운 자료구조는 아니다

단지 제약을 갖는 배열일 뿐이다.

하지만 바로 이러한 제약 덕분에 두 자료구조가 매우 간결해진다.

좀 더 구체적으로 설명하면 스택과 큐는 임시 데이터를 처리할 수 있는 간결한 도구다.

운영 체제 아키텍처부터 출력과 데이터 순회에 이르기까지 스택과 큐를 사용하여 뛰어난 알고리즘을 만들 수 있다.

임시 데이터의 예로 식당에서 음식을 주문하는 상황을 생각해 보자.

손님이 주문한 내역은 식사를 준비해서 서빙할 때까지만 중요하고, 이후로는 버려진다. 이 정보를 계속 가지고 있을 필요가 없다.

임시 데이터란 처리 후에는 전혀 의미 없는 정보이므로 다 쓴 후에는 버려도 된다.

곧 배우겠지만 스택과 큐는 이와 같은 임시 데이터를 처리하되 데이터를 처리하는 순서에 특히 중점을 둔다.

스택 (Stack)

스택이 데이터를 저장하는 방법은 배열과 같다.
즉, 단순히 원소들의 리스트다.
다만 한 가지, 스택에는 3가지 제약이 있다

데이터는 스택의 끝에만 삽입할 수 있다.

데이터는 스택의 끝에서만 삭제할 수 있다.

스택의 마지막 원소만 읽을 수 있다.

접시가 여러장 포개어져 있는 상황을 생각해보자.
접시를 쌓을때에는 위에서 쌓는다.그리고 설거지를 할 때에도 위에서 가져온다. 또한 가장 위에 있는 접시를 제외하고는 다른 접시의 윗면은 볼 수 없다.

실제로 대부분의 컴퓨터 과학책에서 스택의 끝을 Top, 스택의 시작을 Bottom이라 부른다

배열의 첫 번째 항목은 스택의 Bottom이고 마지막 항목의 스택의 Top이다.

Last in First Out (LIFO)
스택 연산을 묘사하는데 쓰인다.

추상 데이터 타입

실제로 대부분의 프로그래밍 언어에는 스택이 내장 데이터 타입이나 클래스로 딸려 있지 않다.

구현은 사용자의 몫이다.

대부분의 언어가 배열을 지원하는 것과 극명하게 대조된다.

일반적으로 스택을 생성하려면 실제로 데이터를 저장할 내장 데이터 구조 중 하나를 골라야 한다.

자바스크립트에서는 pop() push() 메서드로 구현이 가능하다.

스택은 내부적으로 어떤 데이터 구조를 쓰든 개의치 않는다. LIFO 방식으로 동작하는 데이터 원소들의 리스트면 된다.
그래서 스택은 추상 데이터 타입에 속한다.
스택은 다른 내장 데이터 구조를 사용하는 이론적 규칙 집합으로 이뤄진 데이터 구조다.

앞으로 마주칠 많은 자료 구조가 추상 데이터 타입이다.

다른 내장 데이터 구조를 기반으로 작성된 코드일 뿐이며 심지어 냊아 데이터 구조 역시 추상 데이터 타입일 수 있다.

프로그래밍 언어 자체에서 Stack 클래스를 구현한다해도 스택 데이터 구조에 여전히 내부적으로 다양한 데이터 구조를 쓸 수 있다는 개념은 변하지 않는다.

스택을 다뤄보며 이해하기

오래 사용할 데이터를 저장할 때는 일반적으로 스택을 사용하지 않지만 임시 데이터를 다뤄야 하는 다양한 알고리즘에서는 스택이 유용한 도구다.

자바스크립트의 린터, 즉 프로그래머가 작성한 자바스크립트 코드를 검사해서 각 줄이 문법적으로 올바른지 확인하는 프로램을 만들어 보자.

매우 다양한 측면에서 문법을 검사해야 하므로 만들기 상당히 복잡하다.

예제에서는 린터의 한 가지 측면인 여는 괄호와 닫는 괄호에만 초점을 맞추겠다.

이 문제를 풀려면 어떤 종류의 괄호 문법이 올바르지 않은지 분석해야 한다.

문제를 나눠 생각해보면 세 가지 상황에서 발생한다.

Type1. 여는 괄호에 대응하는 닫는 괄호가 존재하지 않는 경우
(const x = 2;

Type2. 그 반대로 닫는 괄호에 대응하는 여는 괄호가 존재하지 않는 경우
const x = 2);

Type3. 괄호의 순서가 맞지 않는 경우
const x = [1)];

코드 줄을 검사해서 괄호 문법에 오류가 있는지 확인하는 알고리즘을 어떻게 구현할 수 있을까?

바로 이럴 때 스택을 사용해 훌륭한 린터 알고리즘을 구현할 수 있다.

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

괄호가 아닌 모든 문자는 무시하고 넘어간다.
여는 괄호가 나오면 스택에 푸시한다. 스택에 넣는다는 것은 이 괄호가 닫히기를 기다린다는 의미다.
닫는 괄호가 나오면 스택 위에 원소를 팝해서 확인하고 다음과 같이 분석한다

팝한 항목(항상 여는 괄호)이 현재 닫는 괄호와 종류가 다르면 문법 오류 타입3에 해당한다.
스택이 비어 팝할 수 없으면 현재 닫는 괄호에 대응하는 여는 괄호가 앞에 나오지 않는 것이다. 문법 오류 타입2이다.
줄 끝에 도달했는데 스택에 여전히 남아있는 괄호가 있다면 다는 괄호가 없다는 의미로 문법 오류 타입1이다.

예제로 스택이 어떻게 동작하는지 알아보자.

({var x = {y: [1, 2, 3]})

첫 번째 여는 괄호는(다.
여는 괄호는 스택에 푸시한다.
괄호가 아닌 문자는 무시한다.
두번째 여는 괄호는 {다.
괄호가 아닌 문자는 무시한다
여는 괄호는 스택에 푸시한다.
세 번째 여는 괄호는 [다.
괄호가 아닌 문자는 무시한다
여는 괄호는 스택에 푸시한다.
첫 번째 닫는 괄호는 ]이다.
스택에서 볼 수 있는 값은 [이다.
쌍이므로 팝한다.
두 번째 닫는 괄호는 }이다.
스택에서 볼 수 있는 값은 {이다.
쌍이므로 팝한다.
세 번째 닫는 괄호는 )이다.
스택에서 볼 수 있는 값은 )이다.
쌍이므로 팝한다.

코드 줄을 전부 살펴봤고 스택이 비었으므로 린터는 이 줄에 문법적 오류가 없다고 결론 내릴 수 있다.



function lintBrace(string) {
  const stack = [];
  for(let i = 0; i < string.length; i++) {
  if (string[i] === '{' || string[i] === '[' || string[i] === '(') {
    stack.push(string[i]);
    return true;
  }
  if (string[i] === '}' || string[i] === ']' || string[i] === ')') {
    const pop = stack.pop();
    if (pop === '{' && string[i] === '}') {
      return true;
    }else if (pop === '[' && string[i] === ']') {
      return true;
    }else if (pop === '(' && string[i] === ')') {
      return true;
    }else {
      return 'check your brace!';
    }
  }
  }
}

예제는 스택을 사용해 린터를 아주 깔끔한 알고리즘으로 구현했다.
하지만 실제로 스택은 내부적으로 배열을 사용하는데, 꼭 스택을 써야 할까?
그냥 배열로 같은 일을 해내면 되지 않을까?

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

정의대로 스택이 제약을 갖는 배열일 뿐이라면 스택이 하는 일은 배열도 할 수 있다는 뜻이다.

그렇다면 스택이 주는 이점은 무엇일까?

제약을 갖는 데이터 구조는 다음과 같은 이유로 중요하다.

제약을 갖는 데이터구조를 사용하면 잠재적 버그를 막을 수 있다.
스택을 사용하면 Top에서만 항목을 제거하기 때문에 다른 방법으로 배열이 변형되는 것을 막는다.
스택 같은 데이터 구조를 통해 문제를 해결하는 새로운 사고 모델을 제공한다.
가령 스택은 후입 선출 프로세스에 대한 전반적인 아이디어를 제공하며 LIFO 사고방식에 입각해 방금 구현한 린터 같은 종류의 문제를 풀 수 있다.
제약을 정확히 이해하고 작성한 코드는 다른 개발자에게 익숙하고 명쾌하게 읽힌다. 알고리즘에 쓰인 스택을 발견하는 순간 그 알고리즘이 LIFO 기반 프로세스로 동작함을 알게 된다.

요약

스택은 마지막에 들어 온 데이터부터 먼저 처리해야 할 때 이상적이다.
가령 워드 프로세서의 되돌리기 함수가 스택의 훌륭한 사례다.
사용자가 타이핑하는 각 키 스트로크를 추적해 스택에 푸시한다.
이후 사용자가 되돌리기 키를 누르면 가장 최근 키 스트로크를 스택에서 팝한 후 문서에서 제거한다. 이제 스택 맨 위로는 그 다음의 최근 키스트로크가 놓이게 되고 필요에 따라 되돌릴 수 있다.

김명성

이전 포스트

CS) 해시 테이블 코테에 적용해보기 (숫자 짝꿍)

다음 포스트