실행 결과를 보면 덱을 이용해서 스택과 큐를 모두 구현할 수 있다는 것을 확인할 수 있습니다.

마지막으로 파이썬의 덱은 어떻게 구현되어 있는지 유추해 봅시다. 파이썬 공식 문서를 확인하면 deque 파트에 다음 문장이 있습니다.

“Indexed access is O(1) at both ends but slows to O(n) in the middle.”

“인덱스로 양 끝에 접근할 때는 빅오가 O(1)이지만 중간에 있는 데이터에 접근하려면 조금 느려서 빅오가 O(n)이다.”라고 쓰여 있습니다. 동적 배열의 인덱싱은 빅오가 O(1)이고, 연결 리스트에서 데이터에 접근할 때는 모든 노드를 순회해야 하므로 빅오가 O(n)인 것을 이미 알고 있지요. 이 문장으로 파이썬의 덱은 이중 연결 리스트를 이용하여 구현했음을 유추할 수 있습니다. 실제로 소스 코드를 직접 확인하지 않아도 스택 오버플로나 다른 문서를 보면 파이썬의 덱이 이중 연결 리스트를 이용해서 구현했다는 것을 확인할 수 있습니다. 이와 같이 자료 구조를 공부해 두면 새롭게 접하는 자료 구조라도 공식 문서나 각종 자료를 이용해서 내부 구현이나 작동 방식을 쉽게 유추할 수 있고 상황에 맞는 자료 구조를 골라 성능도 향상시킬 수 있습니다.

이 장에서는 여러모로 쓸모가 많은 스택과 큐, 덱을 자세히 알아보았습니다. 이 장을 마지막으로 선형 자료 구조는 모두 끝이 났습니다. 다음 장부터는 비선형 자료 구조에 속하는 그래프와 트리를 자세히 알아보겠습니다.