2.2.8 스택

스택(stack)은 후입 선출법(Last In First Out, LIFO)을 따르는 큐라고 볼 수 있다. 상태를 저장하고 저장했던 순서와 반대로 복원할 경우에 유용하다. 실제로 미국의 자동차 운전 면허 공단 사무소를 방문할 때 스택을 사용해야 하는 경우가 있다. 먼저 5번 카운터로 가면 카운터 직원은 서류를 확인하고 요금 결제에 문제가 있다는 것을 알게 된다. 그리고 13번 카운터로 보낸다. 13번 카운터의 직원은 서류에 사진이 없는 것을 보고 이번에는 47번 카운터로 보내 사진을 찍으라고 한다. 그러고 나서 13번 카운터로 다시 갔다가 거기서 요금 결제 영수증을 가지고 5번 카운터로 돌아가면 운전 면허증을 받을 수 있다. 카운터 목록과 이를 순서대로 처리하는 방법은 스택과 유사하며, 일반적으로 실제 이 사례보다는 훨씬 효율적이다.

스택은 배열로 표현할 수 있다. 다른 점은 새 항목을 어디에 넣고 다음 항목을 어디에서 읽느냐는 것이다. 오름차순으로 숫자를 더해서 스택을 만든다면 그림 2-10과 같을 것이다.

▲ 그림 2-10 스택의 기본 구조