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

• 9장에서는 스택과 큐를 알아본다.
• 스택과 큐는 임시 데이터를 처리할 수 있는 간결한 도구다.
• 운영 체제 아키텍처부터 출력, 데이터 순회에 이르기까지 스택과 큐를 임시 컨테이너로 활용하여 뛰어난 알고리즘을 만들 수 있다.

1. 스택

• 스택이 데이터를 저장하는 방법은 배열과 같다. 즉, 원소들의 리스트다.
• 스택에는 다음과 같은 제약이 있다.
  • 데이터는 스택의 끝에만 삽입할 수 있다.
  • 데이터는 스택의 끝에서만 삭제할 수 있다.
  • 스택의 마지막 원소만 읽을 수 있다.
• 접시 더미를 쌓아올린 것처럼 생각해도 좋다.
• 스택의 끝(삽입, 삭제, 읽기 가능)을 top, 밑을 bottom이라고 한다.
• 스택에 새 값을 삽입하는 것을 스택에 푸시한다고도 말한다.
• 스택의 끝에서 원소를 제거하는 것을 pop이라고 한다.
• LIFO - Last In, First Out

2. 추상 데이터 타입

• 실제로 대부분의 프로그래밍 언어에서는 스택이 내장 데이터 타입이나 클래스로 딸려 있지 않다.
• 배열과는 극명하게 대조된다.
• 스택이라는 자료구조는 배열과 종류가 다르다.
• 배열은 대부분의 프로그래밍 언어에 내장되어 있고 컴퓨터 메모리와 직접 상호작용한다.
• 반면 스택은 규칙의 집합이며 특정 결과를 얻기 위해 배열과 상호작용하는 방식이다.
• 스택은 내부적으로 어떤 자료구조를 쓰든 상관없다. LIFO 방식으로 동작할 수 있는 데이터 원소들의 리스트면 된다.
• 그렇기 때문에 스택은 추상 데이터 타입에 속한다.
• 1장에서 봤던 집합 역시 추상 데이터 타입이다.
• 스택과 집합의 자료구조 자체는 그저 이론상의 개념일 뿐이다.

// kotlin에는 stack의 구현이 존재하지 않는다. 즉, 직접 구현하거나 java의 stack을 사용해야 한다.
import java.util.Stack

val stack = Stack<Int>()

• 여기서 사용되는 Java의 Stack은 다음과 같은 상속 구조를 가진다.

Java의 Stack 상속구조

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

• 정의대로 스택이 제약을 갖는 배열일 뿐이라면 스택이 하는 일은 배열도 할 수 있다는 뜻이다.
• 그렇다면 스택이 주는 이점은 무엇일까?
• 제약을 갖는 데이터 구조는 다음과 같은 중요성을 가진다.
  1. 잠재적 버그를 막을 수 있다.
  2. 문제를 해결하는 새로운 사고 모델(mental model)을 제공한다.
  3. LIFO 속성을 이해하여 작성한 코드는 다른 개발자에게 익숙하고 명백하게 이해될 수 있다.

5. 큐

• 스택과 마찬가지로, 큐도 임시 데이터를 처리하기 위해 디자인된 데이터 구조다. 순서를 제외하면 많은 면에서 스택과 비슷하다.
• 큐도 추상 데이터 타입이다.
• FIFO - First In, First Out
• 큐의 시작을 앞(front), 끝을 뒤(back)라고 한다.
• 큐는 다음과 같은 제약을 가진다.
  • 데이터는 큐의 끝에만 삽입할 수 있다. (스택과 동일)
  • 데이터는 큐의 앞에서만 삭제할 수 있다. (스택과 반대)
  • 큐의 앞에 있는 원소만 읽을 수 있다. (스택과 반대)

// kotlin에는 Queue의 구현이 존재하지 않는다. 
// Java에서 제공하는 Queue를 사용할 경우 Queue가 인터페이스이기 때문에 Queue로 선언하되 LinkedList에 할당해 주어야 한다.
// ArrayList로도 구현이 가능하다.

var queue: Queue<Int> = LinkedList()

7. 마무리

• 스택과 큐는 실용적인 알고리즘을 간결하게 처리할 수 있는 도구다.
• 다음은 스택에 기반한 재귀를 배워 본다.