[자료구조] 큐 Queue

큐 (Queue)

  큐는 FIFO(First-In First-Out)를 따르는 자료구조이다. 즉, 가장 먼저 넣은 아이템이 가장 먼저 제거되며 입구와 출구가 다른 자료구조이다. 일상적인 개념에서 '줄서기'에 빗대어 많이 표현된다.

 

큐의 연산

(1) enqueue( ) : 큐의 마지막에 새로운 아이템을 추가한다.

(2) dequeue( ) : 큐의 첫 번째 항목을 제거한다.

(3) front( ) : 큐의 첫 번째 항목을 알려준다. (가장 먼저 출력될 아이템)

(4) rear( ) : 큐의 마지막 항목을 알려준다. (가장 최근에 추가된 아이템)

 

큐의 성능

- 탐색 : 큐에서 탐색은 모든 아이템을 하나하나 훑어봐야 되기 때문에 O(n)시간이 필요하다.

- 삽입 : 상수 시간에 가능하다.

- 제거 : 상수 시간에 가능하다.

 

큐의 활용 사례

(1) 캐시 구현

(2) 동일 우선순위의 예약 (ex. 번호표, 인쇄 대기)

(3) 윈도우 시스템 메시지 처리기

(4) 수식의 괄호 검사 (parenthesis check)  - 실제로 계산기와 함께 스택 구현을 연습하는 예제로 많이 활용한다.

(5) BFS 알고리즘