스택과 큐

스택

Stack은 삽입과 삭제 연산이 후입선출(LIFO: Last In First Out)로 이뤄지는 자료구조.

후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.

 

스택은 깊이 우선 탐색(DFS: Depth First Search), 백트래킹 종류의 코딩 테스트에 효과적.

후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 같다.

큐

Queue는 삽입과 삭제 연산이 선입선출(FIFO : First In First Out)로 이뤄지는 자료구조.

먼저 들어온 데이터가 먼저 나간다.

삽입과 삭제가 양방향에서 이뤄진다.

 

큐는 너비 우선 탐색(BFS : Breadth First Search)에서 자주 사용한다.

우선순위 큐

Priority Queue는 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조.

큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다.

우선순위 큐는 일반적으로 힙(Heap)을 이용해 구현하는데 힙은 트리 종류 중 하나이다.