큐

큐

자료의 삽입과 삭제에 대한 규칙이 있는 자료구조 이며,
‘큐’의 경우, 가장 먼저 ‘삽입(enQueue) 된 데이터가,
제일 먼저 삭제(deQueue) 된다
(선입선출, FIFO 등으로도 표현된다)
(‘은행 대기열’ 등으로 비유되기도)

스택처럼 ‘중간’의 데이터에 접근할 수 없다는 점에 유의!

큐 자료구조의 시간 복잡도

삽입 (enQueue)

O(1)
스택처럼 뒤에 놓으면 끝!

삭제 (deQueue)

O(n)
(일반적인 배열로 구현한 경우)
지운 후, 나머지 요소를 앞으로 당겨야 하므로

O(1)
(원형 버퍼로 구현한 경우)
이를 ‘원형 큐’라고 하며,
가장 앞(deQueue할 요소)을 가리키는 포인터 (front) 와
가장 뒤쪽(enQueue할 위치)을 가리키는 포인터 (back) 를 사용하여
(C 적인 의미가 아니라 인덱스를 가리킨다는 의미의)
삽입, 삭제, isEmpty, isFull 등을 처리하는 방식이다.

검색

O(N)
-> 스택 처럼 모두 제거(deQueue)하여 확인 한 후,
다시 넣어(enQueue) 준다
(모든 요소를 제거했다가,
다시 집어넣으므로 정확히는 O(2N))

큐 자료구조의 주 용도

• ‘대기줄’이 필요한 경우라면 적용이 가능! (데이터 유입 속도가 데이터의 소모 속도 보다 빠른 경우) (ex : 데이터 제공자 보다 데이터를 소비하는 이가 더 많다던가)
• 각종 ‘버퍼’의 개념 (‘입출력 버퍼’) (ex : 게임에서의 콤보 입력(선입력) 등)