Stack & Queue

🔰자료구조

스택

한 쪽 끝에서만 데이터를 넣거나(push) 꺼내는(pop) LIFO 자료구조다.

DFS, 백트래킹 종류의 문제에 효과적이다.

🍎 파이썬에선 리스트와 append, pop 메서드로 스택을 구현한다.

큐

한 쪽 끝에서는 데이터를 넣고(enqueue), 다른 한 쪽에서는 데이터를 꺼내는(dequeue) FIFO 자료구조다.

BFS 문제에 자주 사용한다.

🍎 파이썬에선 리스트와 deque을 이용하여 큐를 구현한다. 일반 리스트를 사용하는 것보다 deque를 사용하는 것이 삽입 및 삭제 성능 면에서 좋다.
deque을 사용하면 append와 popleft로 enqueue와 dequeue를 구현한다.

우선순위 큐

큐나 스택과 비슷하지만, 각각의 요소가 우선순위를 가지고 있어 우선순위대로 처리된다.

일반적으로 힙을 이용해 구현한다.