5.4 요약¶

스택은 후입선출 원리를 따르는 자료 구조로, 배열이나 연결 리스트로 구현할 수 있다.
시간 효율 측면에서 배열 기반 스택의 평균 효율은 더 높지만, 용량 확장이 발생하면 한 번의 삽입 연산의 시간 복잡도가 \(O(n)\)으로 나빠진다. 반면 연결 리스트 기반 스택은 더 안정적인 효율을 보인다.
공간 효율 측면에서 배열 기반 스택은 어느 정도 공간을 낭비할 수 있다. 다만 연결 리스트의 노드 하나는 배열 원소보다 더 많은 메모리를 차지한다.
큐는 선입선출 원리를 따르는 자료 구조로, 역시 배열이나 연결 리스트로 구현할 수 있다. 시간 및 공간 효율의 비교 결과는 앞의 스택과 비슷하다.
덱은 자유도가 더 높은 큐로, 양 끝에서 원소를 추가하고 삭제할 수 있다.

Q: 브라우저의 앞으로 가기와 뒤로 가기는 이중 연결 리스트로 구현되는가?

브라우저의 앞으로 가기와 뒤로 가기는 본질적으로 ‘스택’을 보여 준다. 사용자가 새 페이지를 방문하면 맨 위에 추가되고, 뒤로 버튼을 누르면 그 페이지가 맨 위에서 꺼내진다. ‘덱’ 절에서 설명했듯 덱을 사용하면 일부 추가 연산을 편리하게 구현할 수 있다.

Q: 스택에서 노드를 꺼낸 뒤 그 노드의 메모리를 해제해야 하는가?

나중에 꺼낸 노드를 계속 사용해야 한다면 해제할 필요가 없다. 더 이상 사용하지 않는 경우, Java와 Python 같은 언어는 자동 가비지 컬렉션이 있으므로 직접 해제하지 않아도 된다. C와 C++에서는 직접 해제해야 한다.

Q: 덱은 두 스택을 이어 붙인 것처럼 보이는데, 어디에 쓰이는가?

덱은 스택과 큐를 합치거나 두 스택을 이어 붙인 것과 같다. 스택과 큐의 논리를 모두 지니므로 두 자료 구조의 모든 활용을 구현할 수 있고 더 유연하다.

Q: 실행 취소(undo)와 다시 실행(redo)은 구체적으로 어떻게 구현하는가?

스택 두 개를 사용한다. 스택 A는 실행 취소용, 스택 B는 다시 실행용이다.