[Data Structure] 큐(Queue)

큐(Queue)란?

큐(queue)는 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조의 자료구조이다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

 

큐(Queue)의 연산

큐는 아래와 같은 연산들이 필요하다.

• enqueue(): 큐의 맨 뒤(rear)에 데이터를 삽입한다. 
• dequeue(): 큐의 맨 앞(front)에서 데이터를 삭제한다.
• peek(): 큐의 맨 앞(front)의 데이터를 제거하지 않고 반환한다.
• isEmpty(): 큐가 비었다면 1을 반환하고, 그렇지 않다면 0을 반환한다.

여기서 front는 큐의 맨 앞의 위치(인덱스)를 의미하고, rear는 큐의 맨 뒤의 위치(인덱스)를 의미한다.

 

큐(Queue)의 종류

Linear Queue(선형 큐)

막대 모양으로 된 큐이다. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있다.

Circular Queue(원형 큐)

선형 큐의 문제점(배열로 큐를 선언할시 큐의 삭제와 생성이 계속 일어났을때, 마지막 배열에 도달후 실제로는 데이터공간이 남아있지만 오버플로우가 발생)을 보완한 것이 환형 큐이다. front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결 하는 방식이다.

Prioriry Queue(우선순위 큐)

큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다.