큐 (Queue)

큐란?

큐는 대기줄이란 뜻이다. 대기줄처럼 뒤에서 데이터가 들어오고 앞에서 데이터가 나가는 형태다. 그래서 먼저 들어온 데이터가 먼저 나가는 FIFO(Firt in First Out) 의 특성을 가진다.

 

큐의 연산

큐는 앞, 뒤 양쪽에서 데이터의 입출력이 이루어진다. 보통 데이터가 출력되는 앞쪽을 front, 데이터가 입력되는 뒤쪽을 rear 라고 한다.

 

READ - peek

맨 앞(front)의 데이터를 읽는다. front 정보만 체크하면 되므로 O(1) 의 시간복잡도를 가진다.

 

INSERT - enqueue

맨 뒤(rear)에 데이터를 추가한다. rear 정보만 체크하면 되므로 O(1) 의 시간복잡도를 가진다.

 

DELETE - dequeue

맨 앞(front)의 데이터를 삭제한다. front 정보만 체크하면 되므로 O(1) 의 시간복잡도를 가진다.

 

SEARCH

큐를 구현하는 데 사용되는 자료구조와 알고리즘에 따라 다르다.