큐 Queue
선형 자료구조의 일종으로 한 방향에서는 입력, 한 방향에서는 출력
- FIFO(First In First Out): 선입선출. 가장 먼저 입력된 데이터가 가장 먼저 삭제
- 큐의 가장 첫 원소를 front, 끝 원소를 rear라고 부름. 들어올 때 rear로 들어오지만, 나올 때는 front부터 빠짐. front는 deQueue할 위치, rear는 enQueue할 위치로 -1이 초기값
- 선형 큐의 경우, rear가 배열의 마지막 인덱스를 가르키면 deque를 통해 발생한 배열의 빈 공간을 이용할 수 없다.
원형 큐 Circular Queue
- 선형 큐의 단점 보완
- 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주
- 초기 공백 상태일 때 front와 rear가 0이며 공백, 포화 상태를 쉽게 구분하기 위해 자리 하나를 항상 비워둠
- (rear + 1) % size == front일 때가 포화상태
우선순위 큐 Priority Queue
각 데이터에 우선순위를 부여하여 큐에 넣은 데이터를 꺼낼 때 우선순위가 높은 데이터를 먼저 꺼내는 자료구조
- 힙(Heap) 자료구조를 통해 구현
=> 데이터 우선수위를 지정하여 Heap에 삽입/Heap 삭제 연산을 수행하고 삭제된 데이터 반환 - 힙 포스팅 참고
