들어가며
어제 새벽까지 썼던 8장이
파이어폭스가 멈춰서 다 날아갔다.
하,... 처음부터 다시 써야 한다.
하......
8.0. 스택과 큐로 간단한 코드 생성
지금까지 자료 구조를 논할 때는 주로
자료 구조에 따라
다양한 연산의 성능이 어떻게 달라지는가에
초점을 맞춰왔다.
하지만 프로그래밍 지식 창고에 다양한
자료 구조를 쌓아 두다 보면
보다 간단하고 읽가 쉬운 코드를
생성하는데 도움이 된다.
8장에서는 스택과 큐라는 새로운
자료 구조를 알아보겠다.
사실 두 자료 구조를 완전히 새롭다고
할 수 는 없다.
제약을 갖는 배열일 뿐이다.
하지만 바로 이러한 제약 덕분에
두 자료 구조가 매우 간결해진다.
좀 더 구체적으로 설명하면,
스택과 큐는 임시 데이터를 처리할
수 있는 간결한 도구다.
OS 아키텍처부터 출력 잡과 데이터
순회에 이르기 까지
스택과 큐를 임시 컨테이너로 사용해
뛰어난 알고리즘을 만들 수 있다.
임시 데이터의 예로 식당에서 음식을
주문하는 상황을 가정해보자.
고객이 주문한 내역은 식사를 준비해서
대발할 때까지만 중요하고, 이후로는 버려진다.
이 정보를 계속 가지고 있을 필요가 없다.
임시 데이터란 처리 후에는 전혀
의미 없는 정보이므로
계속 유지하지 않아도 된다.
하지만 처리 중인 주문 데이터는 중요하다.
이상적으로 식당에서는 주문이 들어온
순서대로 식사를 만들어야 한다.
스택과 큐를 사용하면 데이터를
순서대로 처리할 수 있으며
필요 없으면 버릴 수 있다.
8.1. 스택(stack)
스택(stack)이 데이터를 저장하는 방법은
배열과 같다.
즉, 단순히 원소들의 리스트다.
다만 한 가지, 스택에는 다음과 같은
3가지 제약이 있다.
- 데이터는 스택의 끝에만 삽입할 수 있다.
- 데이터는 스택의 끝에서만 읽을 수 있다.
- 데이터는 스택의 끝에서만 삭제할 수 있다.
유명한 감자칩 브랜드인 프링글스를
스택처럼 생각해 볼 수 있다.
포장되어 있는 프링글스 통 가장 위에
있는 칩(과자)을 제외하고는
다른 칩의 윗면을 볼 수 없다.
비슷하게 가장 위를 제외하고는 다른
칩을 추가할 수도, 제거할 수도 없다.
실제로 대부분의 컴퓨터 과학책에서
스택의 끝을 탑(top), 스택의 시작을
바텀(bottom)이라고 부른다.
이러한 제약이 다소 제한적으로
보이겠지만
얼마나 이득인지 알아보겠다.
빈 스택부터 시작해 스택이 어떻게
동작하는지 보자.
스택에 새 값을 삽입하는 것을
푸시(push)라고 한다.
새로운 감자칩을 추가한다고 생각하자.
5를 스택에 푸시한다.
| ↓ |
| 5 |
특별한 것은 없다.
단지 배열의 끝에 데이터를 삽입하는
것이다.
이제 3을 스택에 푸시 한다.
| ↓ | |
| 5 | 3 |
다음으로 0을 스택에 푸시한다.
| ↓ | ||
| 5 | 3 |
0 |
보다시피 데이터를 항상 스택의
탑에 추가하고 있다.
스택의 밑이나 중간에 0을 삽입하려
해도
데이터는 탑에만 추가할 수 있다는
스택의 특징 때문에 불가능하다.
스택의 위에서 원소를 제거하는 것을
팝(pop)이라고 한다.
스택의 제약으로 인해 데이터는
탑에서만 팝할 수 있다.
예제 스택에서 원소를 팝해보자.
먼저 0을 팝한다.
| 0 | ||
| 5 | 3 |
↑ |
이제 스택은 5와 3, 두 원소만
포함한다.
다음으로 3을 팝한다.
| 3 | |
| 5 | ↑ |
이제 스택은 5만 포함한다.
| 5 |
스택 연산을 묘사하는데 쓰이는
유용한 두문자어가
"Last In, First Out"을 뜻하는
LIFO다.
스택에 푸시된 마지막 항목이
스택에서 탑이 되고
이 원소가 스택에서 가장 먼저
팝될 첫 번째 원소가 된다.
8.2. 스택 다뤄보기
오래 사용할 데이터를 저장할 때는
일반적으로 스택을 사용하지 않지만
임시 데이터를 다워야 하는 다양한
알고리즘에서는 스택이 유용한 도구다.
예제로 살펴보자.
자바스크립트 린터(Linter),
즉 프로그래머가 작성한 자바스크립트
코드를 검사해서
각 줄이 문법적으로 올바른지 확인하는
프로그램의 시작 부분을 만들어 보자.
매우 다양한 측면에서 문법을 검사해야
하므로
만들기가 상당히 복잡하다.
예제에서는 린터의 한 가지 측면인
여는 괄호와 닫는 괄호에만 초점을
맞추겠다.
소괄호, 중괄호, 대괄호를 포함하는
괄호는
문법 오류를 일으키는 아주 흔한
주범이다.
이 문제를 해결하기 위해서는
어떤 종류의 괄호 문법이 올바르지
않은지 분석해야 한다.
문제를 나눠 생각해 보면 문법 오류는
3가지 상황에서 발생한다.
- 첫 째, 다음처럼 여는 괄호는 있는데 대응하는 닫는 괄호가 없는 경우
|
1
|
(var x = 2; # 문법 오류 타입 1
|
cs |
- 둘 째, 여는 괄호가 앞에 나오지 않았는데 닫는 괄호가 나온 경우
|
1
|
var x = 2;) # 문법 오류 타입 2
|
cs |
- 셋 째, 닫는 괄호가 바로 앞에 나온 여는 괄호와 종류가 다를 경우
|
1
|
(var x = [1, 2, 3;)] # 문법 오류 타입 3
|
cs |
소괄호끼리 대응하는 쌍이 있고,
대괄호 끼리 대응하는 쌍이 있지만,
닫는 괄호가 바로 앞에 나온 여는 대괄호와
일치하지 않으므로 위치가 틀렸다.
코드 줄을 검사해서 괄호 문법 오류가
없는지 확인하는 알고리즘을
어떻게 구현할 수 있겠는가?
바로 이럴 때 스택을 사용해 훌륭한
린터 알고리즘을 구현할 수 있다.
다음과 같이 동작한다.
빈 스택을 준비해서 다음과 같은
규칙에 따라 각 문자를
왼쪽에서부터 오른쪽 방향으로
읽는다.
1. 괄호(소괄호, 중괄호, 대괄호)가 아닌 모든 문자는 무시하고 넘어간다.
2. 여는 괄호가 나오면 스택에 푸시한다. 스택에 넣는다는 것은 이 괄호가 닫히기를 기다린다는 의미다.
3. 닫는 괄호가 나오면 스택의 탑 원소를 확인한다. 그리고 다음처럼 분석한다.
- 스택에 원소가 없으면 닫는 괄호에 대응하는 여는 괄호가 앞에 나오지 않은 것이다.
이는 문법 오류 타입 2에 해당한다. - 스택에 데이터가 있지만, 닫는 괄호가 스택 위에 있는 원소와 괄호 종류가 다르면,
이는 문법 오류 타입 3에 해당한다. - 닫는 괄호가 스택 위에 있는 원소와 괄호 종류가 같으면 여는 괄호를 성공적으로 닫았다는 뜻이다.
이 괄호는 더 이상 기록할 필요가 없으므로 스택의 탑 원소를 팝한다.
4. 줄 끝에 도달했는데 스택에 여전히 괄호가 남아 있다면 여는 괄호에 대응하는 닫는 괄호가 없다는 의미다. 이는 문법 오류 타입 1에 해당한다.
예제로 어떻게 동작하는지 보자.
|
1
|
(var x = {y : [1, 2, 3;]})
|
cs |
빈 스택을 준비한 후, 각 문자를 왼쪽부터
오른쪽으로 읽기 시작한다.
1단계: 첫 번째 문자는 여는 소괄호다.
2단계: 여는 소괄호 이므로 스택에 푸시한다.
| ↓ |
| ( |
'var x = '은 괄호 문자가 아니므로 모두
무시한다.
3단계: 다음 여는 괄호가 나왔다.
4단계: 스택에 푸시한다.
| ↓ | |
| ( | { |
'y: '은 괄호 문자가 아니므로 무시한다.
5단계: 여는 대괄호가 나왔다.
6단계: 스택에 푸시한다.
| ↓ | ||
| ( | { |
[ |
1, 2, 3도 모두 무시한다.
7단계: 닫는 괄호가 처음 나왔다. 닫는 대괄호다.
8단계: 스택의 탑을 검사한다. 여는 대괄호가 들어있다. 닫는 대괄호와 스택의 탑의 괄호 종류가 같으므로 여는 대괄호를 스택에서 팝한다.
| [ | ||
| ( | { |
↑ |
9단계: 다음으로 닫는 중괄호가 나온다.
10단계: 스택의 탑을 읽는다. 여는 중괄호이므로 일치한다. 스택에서 여는 중괄호를 팝한다.
| { | |
| ( | ↑ |
11단계: 닫는 소괄호가 나왔다.
12단계: 스택의 탑을 읽는다. 괄호 종류가 일치하므로 스택에서 여는 소괄호를 팝한다. 이제 스택은 비었다.
| ( |
| ↑ |
코드 줄을 모두 살펴봤고, 스택이
비었으므로
린터는 이 줄에 문법적 오류*가 없다고
결론 내릴 수 있다.
* 괄호에 관한 문법적 오류에 한하여
위 알고리즘을 루비로 구현해 보겠다.
루비의 배열에는, 배열 끝에 원소를
추가 및 제거할 수 있는
push와 pop 메서드가 기본적으로
내장되어 있다.
배열에 데이터를 추가하고 제거하는
두 메서드만 사용해도
효과적으로 배열을 스택으로써
사용할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
class Linter
attr_reader :error
def initialize
# 간단한 배열을 스택으로 사용한다.
@stack = []
end
def lint(text)
# 텍스트 내 각 문자를 읽는 루프를 시작시킨다.
text.each_char.with_index do |char, index|
if opening_brace?(char)
# 문자가 여는 괄호면 스택에 푸시한다.
@stack.push(char)
elsif closing_brace?(char)
if closes_most_recent_opening_brace?(char)
# 닫는 괄호 문자가 가장 최근에 나온 여는 괄호를 닫았다면
# 스택에서 해당 여는 괄호를 팝한다.
@stack.pop
else # 닫는 괄호 문자가 가장 최근에 나온 여는 괄호를 닫지 않았다면
@error = "Incorrect closing brace: #{char} at index #{index}"
return
end
end
end
if @stack.any?
# 줄 끝에 도달했는데 스택이 비어있지 않다면,
# 여는 괄호에 대응하는 닫는 괄호가 없는 것이다.
@error = "#{@stack.last} does not have a closing brace"
end
end
private
def opening_brace?(char)
["(", "[", "{"].include?(char)
end
def closing_brace?(char)
[")", "]", "}"].include?(char)
end
def opening_brace_of(char)
{")" => "(", "]" => "[", "}" => "{"}[char]
end
def most_recent_opening_brace
@stack.last
end
def closes_most_recent_opening_brace?(char)
opening_brace_of(char) == most_recent_opening_brace
end
end
|
cs |
다음처럼 Linter 클래스를 사용하면,
|
1
2
3
|
linter = Linter.new
linter.lint("( var x = { y: [1, 2, 3] } )")
puts linter.error
|
cs |
자바스크립트 코드 줄이 올바르므로
어떤 오류도 반환하지 않는다.
하지만 실수로 마지막 문자 2개를
뒤바꾸면 어떻게 될까?
|
1
2
3
|
linter = Linter.new
linter.lint("( var x = { y: [1, 2, 3] ) }")
puts linter.error
|
cs |
이렇게 하면 다음과 같은 메시지를
얻는다.
Incorrect closing brace: ) at index 25
마지막 닫는 소괄호를 빼버리면
어떻게 될까?
|
1
2
3
|
linter = Linter.new
linter.lint("( var x = { y: [1, 2, 3] }")
puts linter.error
|
cs |
다음과 같은 오류 메시지를 얻는다.
( does not have a closing brace
위 예제는 스탟을 사용해 아직 닫히지
않은 여는 괄호를 계속해서 기록한다.
이와 비슷하게 9장에서는 '재귀'라
알려진 대단히 중요한 개념의
핵심 기술로서 스택을 사용해 코드
내에서 호출해야 하는 함수를 기록한다.
스택은 입력받은 순서와 반대로 데이터를
처리해야 할 때(LIFO) 항상 이상적이다.
워드 프로세서의 "되돌리기" 함수나
네트워크 애플리케이션에 쓰이는 함수
호출 등에서 스택이 유용할 것이다.
8.3. 큐(queue)
큐(queue) 역시 간결하게 임시 데이터를
다루며
제약이 있는 배열이라는 점에서
스택과 비슷하다.
다만 데이터를 처리하는 순서가
다르므로
작업 중인 애플리케이션의 요구에
따라 선택한다.
극장에 줄 서 있는 사람들을 큐처럼
생각할 수 있다.
줄 맨 앞에 있는 사람이 그 줄을
떠나 가장 먼저 극장에 들어간다.
큐 역시 큐에 첫 번째로 추가된
항목이 가장 먼저 제거된다.
그래서 컴퓨터 과학자는 큐를
"First In, First Out"의 약자인
FIFO로 표현한다.
스택과 마찬가지로, 큐도 다음과 같은
3가지 제약을 포함하는 배열이다.
다만 제약 사항이 조금 다르다.
- 데이터는 큐의 끝에만 삽입할 수 있다. (스택과 동일한 동작이다.)
- 데이터는 큐의 앞에서만 읽을 수 있다. (스택과 정반대 동작이다.)
- 데이터는 큐의 앞에서만 삭제할 수 있다. (스택과 정반대 동작이다.)
이때 큐의 가장 앞 부분을 프론트(front),
가장 뒤 부분을 레어(rear)라고 한다.
빈 큐로 시작해서 큐가 어떻게
동작하는지 보자.
먼저 5를 삽입*한다.
* 큐 삽입에는 표준 명칭이 없다. 참고 문헌마다 put, add, enqueue 등으로 부른다.
| ↓ |
| 5 |
다음으로 9를 삽입한다.
| ↓ | |
| 5 |
9 |
다음으로 10을 삽입한다.
| ↓ | ||
| 5 | 9 |
10 |
지금까지는 스택과 동일하게
동작했다.
하지만 큐의 프론트에서부터 데이터를
삭제하므로, 삭제는 역순이다.
데이터를 삭제하려면 큐의 맨 앞에
있는 5부터 시작해야 한다.
| 5 | ||
| ↑ | 9 | 10 |
다음으로 9를 삭제한다.
| 9 | |
| ↑ | 10 |
이제 큐에는 원소 10 하나만 남았다.
| 10 |
8.4. 큐 다뤄보기
출력 잡(job)부터 웹 애플리케이션의
백그라운드 워커에 이르기까지
많은 애플리케이션에서 흔하게 큐를
사용한다.
프린터가 네트워크 상에 있는 여러
컴퓨터로부터
출력 잡을 받아들일 수 있도록 루비로
간단한 인터페이스를
프로그래밍 한다고 하자.
루비 배열에는 배열 끝에 데이터를
추가하는 push 메서드와
배열 앞에서 데이터를 삭제하는
shift 메서드가 있으므로
두 메서드를 활용해 다음과 같은
클래스를 생성할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class PrintManager
def initialize
@queue = []
end
def queue_print_job(document)
@queue.push(document)
end
def run
while @queue.any?
# 루비의 시프트 메서드는 배열의 첫 번째 원소를 삭제하고 반환한다.
print(@queue.shift)
end
end
private
def print(document)
# 실제 프린터를 실행시키는 코드다
# 데모용으로 터미널에 출력한다.
puts document
end
end
|
cs |
위 클래스를 다음처럼 활용한다.
|
1
2
3
4
5
|
print_manager = PrintManager.new
print_manager.queue_print_job("First Document")
print_manager.queue_print_job("Second Document")
print_manager.queue_print_job("Third Document")
print_manager.run
|
cs |
이렇게 하면 프린터는 요청받은
순서대로 세 문서를 출력한다.
First Document
Second Document
Third Document
위 예제는 단순화됐고,
실제 출력 시스템이 다뤄야할 핵심
기능을 추상화 하기도 했지만
실제로 위와 같은 애플리케이션은
필수적으로 큐를 사용하고
큐는 이러한 시스템 개발에
토대가 된다.
또한 큐는 요청받은 순서대로 요청을
처리하므로
비동기식 요청을 처리하는
완벽한 도구이기도 하다.
이 외에 이륙을 기다리는 비행기나
의사를 기다리는 환자처럼
정해진 순서대로 이벤트가 발생해야
하는 실세계 시나리오를
모델링하는 데 흔하게 쓰인다.
8.5. 마무리
지금까지 알아봤듯이 스택과 큐는
실용적인 알고리즘을
간결하게 처리할 수 있는 프로그래머의
도구다.
스택과 큐를 이해했으니, 새 도전과제가
생겼다.
스택에 기반한 재귀를 배우는 것이다.
재귀 역시 이 책의 나머지 부분에서
다룰,
더 뛰어나고 대단히 효율적인
많은 알고리즘의 토대다.
참고 및 출처
 |
|
