[Stack and Queue] 데크, Deque

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 데크 (Deque, Double-ended queue)

• 양쪽 끝에서 삽입과 삭제가 가능한 자료구조
• 스택과 큐를 혼합한 자료구조
• 이중 연결 리스트로 구현하는 것이 편리
• 파이썬에는 데크가 Collections 패키지에 정의되어 있음

 

- 수행 시간

• 데크를 배열이나 이중 연결 리스트로 구현한 경우, 스택과 큐의 수행 시간과 동일
• 양 끝에서 삽입과 삭제가 가능하므로 프로그램이 다소 복잡
• 이중 연결 리스트로 구현한 경우는 더 복잡함

 

- 응용

• 웹 브라우저 방문 기록
• 스크롤
• 문서 편집기 등의 Undo 연산