'스택'과 '큐'란 새로운 자료 구조는 "제약을 갖는 배열"로, 임시 데이터를 처리할 수 있는 간결한 도구다. 우리는 이것들을 임시 컨테이너로 사용해서 뛰어난 알고리즘을 만들 수 있다.
한 예로 손님이 주문한 내역은 식사를 준비하는 데까지만 중요하고, 이후는 버려진다. 해당 정보를 계속 가지고 있을 필요가 없으므로 임시 데이터란 다 쓴 후에는 버려도 된다. 스택과 큐는 이와 같은 임시 데이터를 처리하되 데이터를 처리하는 '순서'에 중점을 둔다.
9. 1 스택
'스택(stack)'이 데이터를 저장하는 방법은 배열과 같다. 단순히 원소들의 리스트다. 다만 3가지 제약이 있다.
- 데이터는 스택의 끝에만 삽입할 수 있다.
- 데이터는 스택의 끝에서만 삭제할 수 있다.
- 스택의 마지막 원소만 읽을 수 있다.
예를 들어 '접시 더미'를 스택처럼 생각해보자. 가장 위에 있는 접시를 제외하고는 다른 접시의 윗면을 볼 수 없다. 또 가장 위를 제외하고는 접시를 추가, 제거가 불가능하다. 스택의 끝은 '위(top)', 스택의 시작은 '밑(bottom)'이라고 부른다.
스택에 새 값을 삽입하는 것을 "스택에 푸시(push)한다"라고 말한다.
5를 스택에 푸시하자.
| 5 |
그리고 3을 스택에 푸시하자.
| 5 | 3 (push) |
또 7을 스택에 푸시하면 다음과 같다.
| 5 | 3 | 7 (push) |
데이터는 항상 스택의 위(끝)에 추가한다. 스택의 밑이나 중간에 삽입은 불가능하다.
원소를 스택의 위에서 제거하는 것을 "스택으로부터 팝(pop)한다"라고 한다. 이 또한 스택의 제약으로 위에서만 팝할 수 있다.
7을 팝 하자.
| 5 | 3 | 7 (pop) |
이제 3을 팝 해보자.
| 5 | 3 (pop) |
이제 스택은 5만 남는다.
| 5 |
스택 연산을 묘사하는 두문자어는 'LIFO(Last In, First Out)'이다. 마치 교실에 마지막으로 들어오고 가장 먼저 나가는 '게으른 학생'과 비슷해 보인다.
9. 2 추상 데이터 타입
대부분의 프로그래밍 언어들은 배열을 지원하지만, 스택은 지원하지 않는다. 따라서 스택의 구현은 사용자의 몫이라서 Stack 클래스를 직접 만들어야 한다.
스택을 생성하려면 실제 데이터를 저장할 내장 데이터 구조 중 하나를 골라야 한다. 스택은 일반적으론 배열을 사용하지만, 내부적으로 어떤 데이터 구조를 쓰든 상관없다.
단지 'LIFO' 방식으로 동작하는 데이터 원소들의 리스트면 된다. 배열을 쓰든 그 외 내장 데이터 구조를 쓰든 중요하지 않다. 따라서 스택은 '추상 데이터 타입'에 속한다.
스택은 다른 내장 데이터 구조를 사용하는 '이론적 규칙 집합'으로 이뤄진 데이터 구조다. 추상 데이터 타입이라는 말은, 그저 이론상의 개념이라는 뜻이다(1장에서 봤던 '집합'도 중복이 없는 데이터 원소들의 리스트란 이론상의 개념과 같다).
9. 3 스택 다뤄보기
스택은 임시 데이터를 다룰 때 사용하는 유용한 도구다(오래 사용할 데이터를 저장할 때는 일반적으로 스택을 사용하진 않는다).
예를 들어, 컴퓨터가 사용자의 코드를 검사해서 '여는 괄호'와 '닫는 괄호'가 문법상 맞는지 확인하는 프로그램을 짜려고 한다. 소괄호, 중괄호, 대괄호 중에서 짝이 맞게 괄호를 닫는지 확인하는 것이 목적이다.
일단 빈 스택을 준비해서 각 문자를 왼쪽부터 오른쪽 방향으로 읽는다.
(1) 괄호(소괄호, 중괄호, 대괄호)가 아닌 모든 문자는 무시한다.
( var x = { y : [ 1, 2, 3 ] } )
(2) 첫 번째 문자는 여는 소괄호다. 이를 스택에 푸시한다.
| ( (push) |
(3) 다음 여는 괄호가 나오면 스택에 푸시한다.
| ( | { (push) |
(4) 마지막 괄호까지 스택에 푸시한다.
| ( | { | [ (push) |
(5) 닫는 괄호가 나오면 스택 위에서 원소를 팝 한다. 닫는 대괄호와 스택에서 팝 한 원소의 종류가 같으니 오류 없이 알고리즘을 이어갈 수 있다.
| ( | { | X (pop) |
(6) 다음 닫는 괄호가 나오면 또 스택 위에서 원소를 팝 한다. 비교해서 동일한 괄호면 오류가 없다.
| ( | X (pop) |
(7) 다음 닫는 괄호가 나오면 스택의 마지막 원소를 팝한다. 똑같이 비교한다.
| X (pop) |
코드 줄을 다 살펴봤고 스택이 비었으므로 이 줄에는 문법적 오류가 없다고 결론 내릴 수 있다.
9. 4 제약을 갖는 데이터 구조의 중요성
스택이 제약을 갖는 배열이라면, 스택이 하는 일은 배열도 할 수 있다는 뜻이다. 하지만 스택처럼 제약을 갖는 데이터 구조는 나름의 이점을 가진다.
이점 1 : 제약을 갖는 데이터 구조를 사용하면 잠재적 버그를 막을 수 있다. 무심코 (혹은 악의적으로) 배열 중간에서 항목을 추가, 삭제하는 일이 발생하면 오류를 일으킨다. 스택을 사용하면 위 항목만 제거하게 되니 안전하다.
이점 2 : 스택 같은 데이터 구조는 문제를 해결하는 새로운 사고 모델을 제공한다. 스택의 경우 '후입 선출(LIFO) 프로세스'에 대한 전반적인 아이디어를 주기 때문에 해당 사고방식을 토대로 문제를 풀 수 있다.
스택은 마지막에 들어온 데이터부터 먼저 처리해야 할 때 이상적이다. 대표적으로 '워드 프로세서의 "되돌리기" 함수가 스택의 훌륭한 활용 사례다. 사용자가 타이핑하는 각 키스트로크를 추적해 스택에 푸시하고, 사용자가 "되돌리기" 키를 누르면 가장 최근 키스트로크를 스택에서 팝한 후 문서에서 제거하는 것이다.
9. 5 큐
"큐(queue)" 역시 임시 데이터를 처리하기 위해 디자인된 데이터 구조다. 스택처럼 추상 데이터 타입이다.
극장에 줄 서 있는 사람들을 큐처럼 생각할 수 있다. '선착순' 개념으로 줄 맨 앞에 있는 사람이 그 줄을 떠나 가장 먼저 입장한다. 큐에 첫 번째로 추가된 항목이 가장 먼저 제거되는데 이는 'FIFO(First In, First Out)'라고 한다.
큐는 주로 가로로 묘사된다. 그리고 흔히 큐의 시작을 '앞(front)', 큐의 끝을 '뒤(back)'라고 부른다. 큐도 시택과 마찬가지로 세 가지 제약을 갖는 배열이다.
- 데이터는 큐의 끝에만 삽입할 수 있다.
- 데이터는 큐의 앞에서만 삭제할 수 있다.
- 큐의 앞에 있는 원소만 읽을 수 있다.
스택과는 '삽입'은 동일하지만, '삭제'와 '읽기'의 순서에서 차이가 있다. 큐는 가장 먼저 들어온 '앞' 원소들만 삭제하고 읽을 수 있다.
5를 큐에 인큐(enqueue)하자.
| 5 |
그리고 9를 삽입한다.
| 5 | 9 (enqueue) |
다음으로 100을 삽입한다.
| 5 | 9 | 100 (enqueue) |
지금까지는 스택과 동일하게 작동했다. 하지만 큐는 앞에서부터 데이터를 삭제하므로 삭제는 역순이다.
데이터를 삭제하려면 큐의 맨 앞에 있는 5부터 시작한다.
| 5 (dequeue) |
9 | 100 |
이제 9를 디큐 해보자.
| 9 (dequeue) |
100 |
이제 큐에는 100만 남는다.
| 100 |
다른 여러 추상 데이터 타입처럼 많은 프로그래밍 언어에 큐가 구현되어 있지 않다. Queue 클래스를 만들려면 'enQueue' 메서드는 배열 끝에 데이터를 삽입하고, 'deQueue' 메서드는 배열에서 첫 번째 항목을 제거한다. 또한 'read' 메서드는 배열의 첫 번째 원소만 본다.
9. 6 큐 다뤄보기
큐의 경우 프린터에서 요청받은 순서대로 각 문서를 출력하는 등의 애플리케이션에 흔하게 사용된다. 요청이 들어온 순서대로 처리되기 때문이다.
또한 큐는 요청받은 순서대로 요청을 처리하므로 비동기식 요청을 처리하는 좋은 도구이기도 하다. 이 외에 이륙을 기다리는 비행기, 의사를 기다리는 환자처럼 정해진 순서대로 이벤트가 발생해야 하는 시나리오를 모델링하는 데 흔히 쓰인다.
9. 7 마무리
스택과 큐는 실용적인 알고리즘을 간결하게 처리할 수 있는 도구다.
해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.
오로지 학습용으로 작성하였음을 밝힙니다.
더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.
'자료구조 & 알고리즘' 카테고리의 다른 글
| Ch.11 재귀적으로 작성하는 법 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.07 |
|---|---|
| Ch.10 재귀를 사용한 재귀적 반복 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.06 |
| Ch.08 해시 테이블로 매우 빠른 룩업 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.05.09 |
| Ch.07 일상적인 코드 속 빅 오 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.05.05 |
| Ch.06 긍정적인 시나리오 최적화 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.05.05 |
