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

Deah (김준희)·2024년 3월 6일
개발서적알고리즘자료구조
0

누구나 자료구조와 알고리즘 (개정2판)

목록 보기
9/15
post-thumbnail

들어가기 전에

지금까지는 주로 자료 구조에 따라 다양한 연산의 성능이 어떻게 달라지는가에 초점을 맞춰왔다.
하지만 다양한 자료 구조를 알고있게 된다면 간단하고 읽기 쉬운 코드를 작성하는 데 도움이 된다.

9장에서는 스택과 큐라는 새로운 자료 구조를 알아본다. 스택과 큐는 제약을 갖는 배열이라고 할 수 있으며, 더 구체적으로 설명하면 임시 데이터를 처리할 수 있는 간결한 도구이다. 운영 체제 아키텍처부터 출력과 데이터 순회까지 스택과 큐를 임시 컨테이너로 사용하여 뛰어난 알고리즘을 만들 수 있다.

🧐 임시 데이터란 무엇일까?

만약 식당에서 음식을 주문하는 상황을 가정한다면, 손님이 주문한 내역은 식사를 준비해서 배달할 때까지만 중요하고 그 이후로는 버려진다. 고로 이 정보를 계속 가지고 있을 필요가 없다는 뜻이다.
즉, 임시 데이터는 처리 후에 전혀 의미 없는 정보가 되므로 사용한 이후에는 버려도 된다.

스택과 큐는 이와 같은 임시 데이터를 처리하되 '순서'에 중점을 두어 처리하게 된다.


9.1 스택

스택(Stack)이란?
한쪽 끝에서만 데이터에 제한적으로 접근할 수 있는 후입선출(Last-In-First-Out) 형태의 선형(linear) 자료구조로 "쌓다"라는 의미를 가지며, 데이터를 차곡차곡 쌓아 올린 형태를 띈다.

스택의 세 가지 제약

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

접시 더미를 생각해볼 때, 가장 위에 있는 접시를 제외하고는 다른 접시의 윗면은 볼 수 없다.
그리고 가장 위를 제외하고는 접시를 추가하거나 제거 할 수 없다.

실제로 스택의 끝을 위(top), 스택의 시작을 밑(bottom)이라고 부르는데,
그 이유는 스택을 수직으로 높인 배열로 보면 이해할 수 있다.
아래 그림과 같이 배열의 첫 번째 항목은 스택의 밑(bottom)이고, 마지막 항목은 위(top)이다.

🤔 밑과 위... 배열에 비해서 제약이 있는 거 아닌가요?

  • 스택에 데이터 추가 : 푸시(push)
  • 스택에서 데이터 삭제 : 팝(pop)

스택은 항상 데이터를 스택의 위(끝)에 푸시한다. 스택의 밑이나 중간에 데이터를 삽입하고 싶더라도 데이터는 가장 위에만 추가할 수 있는 것이 스택의 특징이다. 그리고 데이터를 삭제할 때에도 똑같이 위에서만 팝할 수 있다.

스택은 후입선출(Last-In-First-Out), 즉 LIFO 구조이다.
스택에서 푸시된 마지막 항목이 스택에서 팝될 첫 번째 항목이라는 의미이다.


9.2 추상 데이터 타입

대부분의 프로그래밍 언어에서는 스택이 내장되어 있지 않다. 필요에 의해 개발자가 직접 구현해야 한다. 대부분의 언어가 배열를 지원하는 것과 극명하게 대조된다.

스택을 생성하기 위해서는 실제로 데이터를 저장할 내장 데이터 구조 중 하나를 골라야 한다.
다음 코드는 배열을 사용하여 스택을 구현하는 자바스크립트 코드의 예시이다.

기본 코드

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

  push(element) {
    this.data.push(element);
  }

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

  read() {
    return this.data[this.data.length - 1];
  }
}

해설

class Stack {
  // 스택을 초기화하면 자동으로 빈 배열 생성
  constructor() {
    this.data = [];
  }

  // 스택에 데이터를 추가하는 push 메서드 => 가장 위(끝)에 추가
  push(element) {
    this.data.push(element);
  }
  
  // 스택에서 데이터를 삭제하는 pop 메서드 => 가장 위(끝)에서 삭제
  pop() {
    return this.data.pop();
  }

  // 스택에서 데이터를 읽는 read 메서드 => 가장 위(끝) 데이터 읽기
  read() {
    return this.data[this.data.length - 1];
  }
}

사실 스택은 내부적으로 어떤 데이터 타입을 사용하던 상관 없다. LIFO(Last-In-First-Out) 방식으로 동작하는 데이터 원소들의 리스트로 구현되면 된다. 그렇기 때문에 스택은 추상 데이터 타입에 속한다.

추상 데이터 타입(Abstract Data Type, ADT)란?
자료들과 그 자료들에 대한 연산들을 명기한 것이다. 추상 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료 구조와 다르며, 인터페이스와 구현을 분리하여 추상화 계층을 둔다.

1장-자료 구조가 중요한 까닭에서 살펴봤던 집합(Set)도 추상 데이터 타입 중 하나이다.
어떤 구현에서는 배열을 사용하는 반면, 또 어떤 구현에서는 해시 테이블을 사용할 수도 있다.
중요한 것은 집합 자체는 이론상의 개념일 뿐이며, 중복이 없는 데이터 원소의 리스트라는 것이다.

앞으로 책에서 다룰 많은 자료 구조가 추상 데이터 타입이며, 다른 내장 데이터 구조를 기반으로 작성된 코드일 뿐이다. 그리고 기반이 자료 구조 역시 추상 데이터 타입일 수 있다.


9.3 스택 다뤄보기

스택은 일반적으로 임시 데이터를 다뤄야하는 알고리즘에서 유용하다.

자바스크립트의 코드를 검사하여 문법 오류를 확인하는 린터(linter) 프로그램을 만든다고 했을 때,
이 알고리즘에 스택을 사용하면 훌륭한 알고리즘을 구현할 수 있다.

a. 괄호가 아닌 모든 문자는 무시하고 넘어간다.
b. 여는 괄호가 나오면 스택에 푸시한다. (괄호가 닫히기를 기다린다는 의미)
c. 닫는 괄호가 나오면 스택 위에 원소를 팝하여 확인하고, 다음과 같이 분석한다.
- 팝한 항목(= 항상 여는 괄호)이 현재 닫는 괄호와 종류가 다르면 문법 오류이다.
- 스택이 비어 팝할 수 없으면 현재 닫는 괄호에 대응하는 여는 괄호가 없으므로 문법 오류이다.
- 팝한 항목이 현재 닫는 괄호와 종류가 같으면 성공이며, 코드를 계속 파싱할 수 있다.
d. 코드의 끝에 도달했음에도 스택에 항목이 남아있다면, 대응하는 닫는 괄호가 없으므로 문법 오류이다.

아래 코드에 대해 적용해보자.

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

  1. 코드를 왼쪽부터 오른쪽으로 읽기 시작한다. 첫 번째 문자는 여는 소괄호이다.

  2. 여는 괄호이므로 스택에 푸시한다.

현재 스택 상태
(

(varx={y:[1,2,3]})
👆

  1. var x = 는 괄호가 아니므로 모두 무시하고 지나가며, 다음 문자는 여는 중괄호이다.

  2. 여는 괄호이므로 스택에 푸시한다.

현재 스택 상태
{
(

(varx={y:[1,2,3]})
👆

  1. y: 는 괄호가 아니므로 무시하고 지나가며, 다음 문자는 여는 대괄호이다.

  2. 여는 괄호이므로 스택에 푸시한다.

현재 스택 상태
[
{
(

(varx={y:[1,2,3]})
👆

  1. 1, 2, 3 은 괄호가 아니므로 무시하고 지나가며, 다음 문자는 닫는 대괄호이다.

  2. 닫는 괄호가 나왔으므로 스택에 가장 위 요소([)를 팝한다.
    현재 닫는 괄호(])와 팝한 요소([)의 괄호 종류가 같으므로 다음으로 이어간다.

현재 스택 상태
{
(

(varx={y:[1,2,3]})
👆

  1. 다음 문자는 닫는 중괄호이다.

  2. 닫는 괄호가 나왔으므로 스택에서 가장 위 요소(})를 팝한다.
    현재 닫는 괄호(})와 팝한 요소(}) 의 괄호 종류가 같으므로 다음으로 이어간다.

현재 스택 상태
(

(varx={y:[1,2,3]})
👆

  1. 다음 문자는 닫는 소괄호이다.

  2. 닫는 괄호가 나왔으므로 스택에서 마지막 요소())를 팝한다.
    현재 닫는 괄호())와 팝한 요소()) 의 괄호 종류가 같으므로 다음으로 넘어간다.

현재 스택 상태
ﾠ

모든 코드를 전부 살펴봤고 현재 스택이 비어있으므로, 해당 코드에 문법 오류가 없다는 결론을 지을 수 있다.

코드로 구현한다면

기본 코드

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

  push(element) {
    this.data.push(element);
  }

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

  read() {
    return this.data[this.data.length - 1];
  }
}
class Linter {
    constructor() {
        this.stack = new Stack();
    }

    lint(text) {
        for (let char of text) {
            if (this.isOpeningBrace(char)) {
                this.stack.push(char);
            } else if (this.isClosingBrace(char)) {
                let poppedOpeningBrace = this.stack.pop();

                if (!poppedOpeningBrace) {
                    return `${char}은 여는 괄호가 없습니다.`;
                }

                if (this.isNotAMatch(poppedOpeningBrace, char)) {
                    return `${char}은 여는 괄호와 매치되지 않습니다.`;
                }
            }
        }

        if (this.stack.length > 0) {
            return `${this.stack[this.stack.length - 1]}은 닫는 괄호가 없습니다.`;
        }

        return true;
    }

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

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

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

❗️ 책의 루비 예제 코드를 자바스크립트로 바꾸다보니 현재 여는 괄호만 있을 때 통과되는 오류 발생 중... 추후 수정...


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

스택이 제약을 갖는 배열이라면, 이들이 하는 일을 배열도 할 수 있다는 뜻이 된다.
그렇다면 스택이 주는 이점은 무엇일까? (큐도 마찬가지)

1. 제약을 갖는 데이터 구조를 사용하면 잠재적 버그를 막을 수 있다.
2. 스택과 같은 데이터 구조는 문제를 해결하는 새로운 사고 모델(Mental Model)을 제공한다.

첫 번째 항목은 린팅 알고리즘을 예로 들 수 있다. 린팅 알고리즘은 스택의 위에서 항목을 제거하는 경우에만 동작한다. 개발자가 중간에서 항목을 삭제하는 코드를 작성한다면, 알고리즘은 고장난다. 그러나 스택에서는 중간에서 항목을 삭제할 수 없으므로 이같은 사고를 방지할 수 있다.

두 번째 항목에 대해서, 스택은 후입선출(LIFO) 구조에 대한 전반적인 아이디어를 제공한다. 이런 사고방식에 입각해 린팅 알고리즘류의 문제를 풀 수 있다.

즉, 스택(Stack)은 마지막에 들어온 데이터부터 먼저 처리해야 할 때 이상적이다. (LIFO)
예를 들어, Ctrl(cmd) + Z 처럼 되돌리기 함수 같은 것이 좋은 활용 사례이다.


9.5 큐

큐(Queue)란?
선입선출(First-In-First-Out, FIFO) 형태의 자료구조이며, "대기열"이라고도 한다.

큐의 세 가지 제약

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

큐도 스택과 마찬가지로 임시 데이터를 처리하기 위한 자료 구조이다.
데이터를 처리하는 순서만 제외하면 스택과 비슷하며, 큐도 스택과 같이 추상 데이터 타입이다.

극장에 줄 서 있는 사람들을 생각했을 때, 가장 앞에 서 있는 사람이 가장 먼저 티켓을 구매하여 극장에 들어간다. 이처럼 큐는 첫 번째로 추가된 항목이 가장 먼저 제거된다. 그리고 큐의 시작을 앞(front), 큐의 끝을 뒤(back)이라고 부르며 스택과 달리 가로로 묘사된다.

큐에 데이터를 삽입하는 것을 흔히 인큐(Enqueue),
큐의 앞에서부터 데이터를 삭제하는 것을 디큐(Dequeue)라고 부른다.
(삽입과 삭제라고 해도 무방)

큐 구현

스택과 마찬가지로 큐도 추상 데이터 타입이며, 대부분의 프로그래밍 언어에는 큐가 구현되어있지 않기 때문에 필요에 따라 개발자가 직접 구현해야 한다.

다음 코드는 배열을 사용하여 큐를 구현하는 자바스크립트 코드의 예시이다.

기본 코드

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

해설

class Queue {
    // 큐를 초기화하면 자동으로 빈 배열 생성
	constructor() {
    	this.data = [];
    }
  
  	// 큐에 데이터 추가하는 enqueue 메서드 => 가장 뒤(끝)에 추가
  	enqueue(element) {
    	this.data.push(element);
    }
  
  	// 큐에서 데이터를 삭제하는 dequeue 메서드 => 가장 앞(처음)에서 삭제
  	dequeue() {
    	return this.data.shift();
    }
  
  	// 큐에서 데이터를 읽는 read 메서드 => 가장 앞(처음) 데이터 읽기
  	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 Printer {
	constructor() {
    	this.queue = new Queue();
    }
  
  	printJob(document) {
    	this.queue.enqueue(document);
    }
  
  	run() {
    	while (this.queue.read()) {
          	// print(this.queue.dequeue());
        	console.log(this.queue.dequeue());   // 프린트 대신 콘솔 출력
        }
    }
}

해설

class Queue {
	constructor() {
    	this.data = [];
    }
  
  	enqueue(element) {
    	this.data.push(element);
    }
  
  	dequeue() {
    	return this.data.shift();
    }
  
  	read() {
    	return this.data[0];
    }
}
class Printer {
  	// 초기화하면서 큐 생성 (큐는 배열 활용)
	constructor() {
    	this.queue = new Queue();
    }
  
  	// 큐에 프린트 해야 할 문서를 인큐 (삽입)
  	printJob(document) {
    	this.queue.enqueue(document);
    }
  
  	// 프린트 실행
  	// 큐에 문서가 있는 동안 반복하며, 가장 먼저 쌓인 문서부터 프린트 (= 디큐 = 삭제)
  	run() {
    	while (this.queue.read()) {
          	// print(this.queue.dequeue());
        	console.log(this.queue.dequeue());   // 프린트 대신 임시 콘솔 출력 활용
        }
    }
}

테스트

const printer = new Printer();

printer.printJob('첫 번째 프린트');
printer.printJob('두 번째 프린트');
printer.printJob('세 번째 프린트');

printer.run();
// 첫 번째 프린트
// 두 번째 프린트
// 세 번째 프린트

실습

  1. 전화를 건 사람을 잠시 대기시킨 후 "다음 연결 가능한 통화원"에게 연결해 주는 콜센터 소프트웨어를 개발할 때, 스택과 큐 중 어느 것을 사용해야 할까?

정답 : 큐
먼저 전화를 건 사람부터 먼저 처리되는 FIFO 구조를 활용해야 하기 때문이다.

  1. 1, 2, 3, 4, 5, 6 순서대로 스택에 수를 푸시한 후 두 항목을 팝하면 스택에서 어떤 수를 읽을 수 있는가?

정답 : 4
(아래) [1, 2, 3, 4, 5, 6] (위) 형태로 스택에 쌓이게 되며, 스택에서는 가장 마지막 요소부터 처리되므로 6과 5가 순서대로 팝(삭제)된다. 그리고 마찬가지로 가장 마지막 요소만 읽을 수 있으므로 다음으로 읽을 수 있는 것은 4이다.

  1. 1, 2, 3, 4, 5, 6 순서대로 큐에 수를 삽입한 후 두 항목을 디큐하면 큐에서 어떤 수를 읽을 수 있는가?

정답 : 3
(처음) [1, 2, 3, 4, 5, 6] (끝) 형태로 큐에 쌓이게 되며, 큐에서는 가장 처음에 쌓인 요소를 먼저 처리하므로 두 항목을 디큐하면 1과 2가 순서대로 삭제된다. 그 다음 읽을 수 있는 것은 3이다.

  1. 스택을 사용해 문자열을 거꾸로 만드는 함수를 작성하라. (e.g. "abcde" ➡️ "edcba")
class Stack {
	constructor() {
    	this.data = [];
    }
  
  	push(element) {
    	this.data.push(element);
    }
  
  	pop() {
    	this.data.pop();
    }
  
  	read() {
    	return this.data[this.data.length - 1];
    }
}

class ReverseString {
	constructor() {
    	this.stack = new Stack();
    }
  
  	reverse(string) {
      	for (const char of string) {
        	this.stack.push(char);
        }
      
      	let result = '';
      
      	while (this.stack.read()) {
        	result += this.stack.read();
          	this.stack.pop();
        }
      
      	return result;
    }
}
const reverseString = new ReverseString();

reverseString.reverse('abced');    // 'decba'
reverseString.reverse('1234567')   // '7654321'
profile
Deah (김준희)
기록 중독 개발자의 기록하는 습관
이전 포스트

8장. 해시 테이블로 매우 빠른 작업

다음 포스트

10장. 재귀를 사용한 재귀적 반복

0개의 댓글