[책] 누구나 자료구조와 알고리즘 - 9장 스택과 큐로 간결한 코드 생성

 

누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고

 

스택과 큐는 제약을 갖는 배열이다.

운영체제 아키텍처, 출력 잡, 데이터 순회 등 임시 컨테이너로 사용해 뛰어난 알고리즘을 만들 수 있다.

이러한 스택과 큐는 임시 데이터를 처리하되 데이터를 처리하는 순서에 특히 중점을 둔다.

 

스택 Stack

스택에는 다음과 같은 세가지 제약이 있다.

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

이미지 출처: https://www.programiz.com/dsa/stack

 

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

스택에 새 값을 삽입하는 것을 스택에 푸시(push)한다고 한다.

스택의 위에서 원소를 제거하는 것을 스택으로부터 팝(pop)한다고 한다.

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

 

- 대부분의 프로그래밍 언어에서는 스택이 내장 데이터 타입이나 클래스로 딸려있지 않다. 구현은 사용자의 몫이다.

- 스택은 어떤 데이터 구조를 쓰든 개의치 않는다. LIFO 방식으로 동작하는 데이터 원소들의 리스트이면 된다.

- 그래서 스택은 추상 데이터 타입에 속한다. 스택은 다른 내장 데이터 구조를 사용하는 이론적 규칙 집합으로 이뤄진 데이터 구조다.

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

추상자료형이란 자료형의 연산을 정의한 것으로 실제 구현 방법은 명시하지 않음

 

예제

린터 (linter) 자바스크립트 문법 검사기에서 스택을 사용할 수 있다. (ex. 소괄호, 중괄호, 대괄호...)

- 여는 괄호면 스택에 푸시한다. (끝지점까지 돌았는데도 스택에 남아있으면 오류 출력)

- 닫는 괄호면 스택에서 팝한다. (스택이 비어있으면 팝할 수 없다. 종류가 같은 괄호여야 한다.)

 

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

스택이 배열로 구현할 수 있다면, 그냥 배열로 사용하면 안될까?

제약을 갖는 데이터 구조(스택, 큐 ...)의 중요성

1. 잠재적 버그를 막을 수 있다. (배열 중간에 실수로라도 삽입 삭제 불가능) 
2. 문제를 해결하는 새로운 사고 모델(mental model)을 제공한다. (문제를 해결할 수 있는 아이디어 제공)

 

큐 Queue

큐도 스택처럼 임시 데이터를 처리하기 위해 디자인 된 데이터 구조이며, 추상 데이터 타입이다.

큐는 다음과 같은 세가지 제약이 있다.

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

 

이미지 출처: https://thebook.io/080200/0077/

 

큐의 시작을 앞(Front), 큐의 끝을 뒤(Back)라고 부른다.

삽입은 인큐(enqueue), 삭제는 디큐(dequeue)라고 부른다.

큐 연산은 "First In, First Out" 줄여서 FIFO 이라고 한다.

 

큐는 출력 잡(job), 웹 애플리케이션의 백그라운드 워커에 이르기까지 많은 애플리케이션에서 흔하게 큐를 사용한다.

큐는 이러한 시스템 개발에 토대가 된다.

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

이 외에 이륙을 기다리는 비행기나 의사를 기다리는 환자처럼 정해진 순서대로 이벤트가 발생해야 하는 실세계 시나리오를 모델링하는 데 흔하게 쓰인다.

 

마무리

스택과 큐를 이해했으니 다음 장에서는 스택에 기반한 재귀를 배울 예정이다.

재귀 역시 효율적인 많은 알고리즘의 토대다.