큐 (Queue)

큐(Queue)

- 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아두기 위한 자료구조이다

- 스택과 달리 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(First In First Out / FIFO) 구조를 갖는다

 

 

- 큐에 데이터를 넣는 작업은 인큐(enQueue), 꺼내는 작업은 디큐(deQueue)라고 한다

- 그리고 데이터를 꺼내는 쪽을 Front, 넣는 쪽은 Rear라 부른다

 

 

선형 큐

 

- 기본적인 큐의 형태로 선형으로 구현된 큐를 말한다

- 선형 큐는 인덱스의 감소 없이 증가만이 이루어지는 방식이기 때문에, 큐의 앞부분에는 데이터가 없는 경우가 발생한다

- 이러한 방식은 front의 앞부분을 다시 활용 못하기 때문에 메모리를 낭비한다는 단점이 있다

 

 

 

- 메모리 낭비를 하지않고, 앞의 빈 공간을 사용하기 위해서는 Front는 고정해두어야한다

- 그리고 deQueue를 할때마다 남아있는 데이터를 한 칸씩 앞으로 옮겨주어야 한다

- deQueue를 할 때마다 모든 데이터를 옮기는 방식은 굉장히 번거롭다

 

 

원형 큐

 

- 원형큐는 deQueue를 할 때마다 모든 데이터를 이동시켜야하는 선형큐의 문제점을 보완하기 위해 등장했다

- 원형 큐는 선형이 아닌 원형의 형태로 되어있다

- 처음과 끝이 연결된 형태로, 데이터가 큐의 끝에 다다르면 다시 처음으로 돌아갈 수 있게 된다

- 그렇기 때문에 선형 큐처럼 모든 데이터를 이동시킬 필요 없이, 빈 공간을 활용할 수 있다

 

우선순위 큐

- 일반적인 큐와 달리 우선순위를 고려한다

- 우선순위 큐는 들어가는 순서에 관계없이, deQueue 할 때 우선순위에 맞게 데이터를 꺼낸다

- 만약 A, B, C, D의 우선순위가 1, 2, 3, 4 이라면 데이터 삽입 순서와 상관없이 무조건  A→B→C→D의 순서로 deQueue 된다

- 우선순위 큐는 힙을 사용해 구현하는 것이 일반적이다