🔍파이썬 스택
- 파이썬은 기본적으로 list에서 append 메소드와 pop 메소드를 제공하여 스택처럼 사용할 수 있다. 하지만 collections 라이브러리에 있는 deque를 사용할 수 있다.
list를 사용할 때와 deque를 사용할때의 주요한 차이점
1. 시간 복잡도
list를 스택처럼 사용할 경우, append() 메서드를 이용해 값을 리스트의 끝에 추가하고 pop() 메서드를 이용해 리스트의 끝에서 값을 삭제할 수 있다. 하지만 이 경우, 리스트의 맨 끝에서 값을 추가하거나 삭제하면, 리스트 내부의 모든 값들을 이동시켜야 하기 때문에 시간이 오래 걸릴 수 있다. 따라서, list로 스택을 구현하는 경우, 시간 복잡도는 최악의 경우 O(n)이 된다.
🙋♂️리스트의 마지막 원소만 제거하는데 모든 값들을 이동 시켜야 하는 이유?
리스트는 동적 배열이기 때문에, 크기가 가변적이다. 파이썬의 리스트는 다른언어의 배열과 유사한 구조로, 원소를 삭제하면 메모리 공간을 재할당하여 새로운 공간에 원소를 복사하는 작업이 필요하다.
반면, deque는 이중 연결리스트(doubly linked list)를 기반으로 구현되어 있어서, 리스트의 양 끝에서의 값 추가/삭제 연산을 O(1)의 시간 복잡도로 처리할 수 있다. 따라서, deque로 스택을 구현하는 경우, 시간 복잡도는 항상 O(1)이된다.
2. 메모리 사용량
list를 스택처럼 사용할 경우, 기본적으로 동적 배열(dynamic array)로 구현되어 있기 때문에, 초기에 크기를 설정하지 않아도 된다. 하지만, 리스트가 늘어나면 할당된 메모리보다 더 큰 메모리가 필요하게 되면, 더 큰 메모리를 할당하고 기존의 값들을 새로운 메모리에 복사하는 과정이 필요하다
반면, deque는 이중 연결리스트로 구현되어 있기 때문에, 리스트가 늘어나면 새로운 노드를 추가하고 기존의 노드와 연결해주는 것으로 구현된다. 따라서, deque는 더 많은 메모리를 사용하지만, 더 효율적으로 메모리를 사용한다다.
따라서, list로 스택을 구현하는 경우, 시간 복잡도는 더 높지만 메모리 사용량이 적다. 반면, deque로 스택을 구현하는 경우, 시간 복잡도는 낮지만 메모리 사용량이 더 많다. 따라서, 사용하고자 하는 문제의 성격에 따라서 적절한 자료구조를 선택하여 사용해야 한다.
요약
deque를 사용할때, 메모리 사용량, 처리시간에 이점이 있다.
