자료구조) Queue

Queue

삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조. 삽입과 삭제가 양방향에서 이뤄진다.

너비 우선 탐색에서 자주 사용된다.

 

우선순위 Queue (Priority Queue)

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

우선순위에 따라 처리해야 할 때 사용 ex) 값이 높은 물건부터 꺼내서 확인해야 하는 경우

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

우선순위 큐는 리스트 또는 힙을 이용하여 구현한다. 일반적으로는 힙을 이용하여 구현.

구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙	O(logN)	O(logN)

힙의 특징

힙은 완전 이진 트리 자료구조의 일종이다. 힙에서는 항상 루트 노드를 제거한다.

최소 힙은 루트 노드가 가장 작은 값을 갖는 것 최대 힙은 루트 노드가 가장 큰 값을 갖는 것

작동 방식

완전 이진 트리 구조를 따르기 때문에 데이터는 왼쪽 노드에 먼저 생성된다.
minHeap이 실행되면 자신의 부모 노드와 값을 비교하여 값이 적으면 위치를 교환하며 정렬을 시켜 루트 노드에는 최솟값이 위치하게 된다. 

삽입은 자식 노드에서 루트 노드로 상향식, 삭제는 루트 노드에서 자식 노드로 하향식

삽입이 실행되면 자신의 부모 노드와 값을 비교하며 루트 노드에 최솟값을 위치시킨다. O(logN) 시간 복잡도를 갖는다.

삭제가 실행되면 루트 노드의 값이 삭제가 되고 마지막 원소가 루트 노드에 위치시킨다. 그 후 다시 정렬을 실행하며 루트 노드에는 다시 최솟값이 위치하게 된다. O(logN) 시간 복잡도를 갖는다. (구현방식에 따라 차이가 있을 수 있음.)

 

Queue 관련 용어

rear: 큐에서 가장 끝 데이터를 가리키는 영역

front: 큐에서 가장 앞의 데이터를 가리키는 영역

add: rear 부분에 새로운 데이터를 삽입하는 연산

poll: front 부분에 있는 데이터를 삭제하고 확인하는 연산

peek: front 에 있는 데이터를 확인할 때 사용하는 연산