06 큐

큐(Queue)란?

: "대기열"

: 스택과 마찬가지로 데이터를 일시적으로 저장하기 위한 자료구조

:

 

큐의 출력 순서

: 선입선출(FIFO, Fisrt In First Out), 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다.

인큐(enqueue): 큐에 데이터를 넣는 작업

디큐(dequeue): 큐에 데이터를 꺼내는 작업

 

배열을 통한 인큐 디큐 복잡도

데이터를 꺼낼때마다 효율이 떨어진다.

 

링 버퍼 구조를 통한 디큐 복잡도 향상

링 버퍼 구성도 

프런트(front): 맨 처음 요소의 인덱스

리어(rear): 맨 끝 요소 하나 뒤의 인덱스(= 인큐 위치)

 

인큐와 디큐 수행시, 프런트와 리어 값을 업데이트하면 앞서 발생한 요소 이동 문제를 해결하고 복잡도를 O(1)이 된다.

 

+ 오래된 데이터를 버리는 용도