이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다.
출처 : https://www.onlybook.co.kr/entry/algorithm-interview
- 스택, 큐는 가장 고전적인 자료구조 중 하나
- 스택은 거의 모든 애플리케이션을 만들 때 사용됨
- 파이썬은 스택/큐 자료형을 따로 제공하지 않지만, 리스트가 두 기능을 모두 제공
- 추상 자료형 (ADT)
- 스택에 요소들이 차곡차곡 쌓인 것처럼 생각됨
- 실제로 연결 리스트로 구현시, 물리 메모리에 순서와 관계 없이 여기저기 무작위 배치됨
- 스택
- 후입선출 (LIFO, Last In First Out)
- 주요 2가지 연산을 지원하는 요소의 컬렉션으로 사용되는 추상 자료형
- push() : 요소를 컬렉션에 추가
- pop() : 가장 최근 삽입한 요소를 제거
- 큐
- 선입선출 (FIFO, First In First Out)
- 시퀀스의 한쪽 끝에 엔티티 추가, 반대쪽 끝은 엔티티를 제거할 수 있는 엔티티 컬렉션
- 스택에 비해 상대적으로 쓰임새가 적음
- 너비 우선 탐색(BFS, Breadth-First Search), 캐시 구현에 사용
- 리스트는 동적 배열로 구현되어, 큐의 연산을 수행하기 효율적이지 않음
- Deque 사용