3. 큐(Queue)

큐(Queue) : 선입선출(FIFO)

 - 큐의 경우는 스택의 자료 구조와 달리 선입선출 즉 먼저 들어온 데이터가 가장 먼저 나간다.

또한 큐의 종류는 

 ㆍ 순환큐(Circular Queue)

 ㆍ 링크드큐(Linked Queue)

가 있다.

- 단순한 큐의 구조를 먼저 알아보자.

- List에서는 가장 앞에 있는 노드를 헤더(Head), 가장 뒤에 있는 노드를 테일(Tail)이라고 했습니다. 

- 하지만 큐에서는 가장 앞에 있는 요소를 전단(Front), 가장 뒤에 있는 요소를 후단(Rear)라고 부릅니다.

- 큐의 경우는 선입선출의 구조이기 때문에 제거(Dequeue)는 전단에서 이루어지며, 삽입(Enqueue)은 후단에서 이루어진다.

1. 순환 큐(Circular Queue)

 - 순환 큐에 대해 말하기 전에, 직선 구조를 띈 큐의 문제점을 알아보자.

 - 직선 구조의 큐의 제거 연산 시 A의 데이터가 제거(Dequeue)되면서 뒤에 있는 요소들이 앞으로 옮겨지는 상황이 벌어집니다.

즉 B가 삭제되면 C가 다시 B의 위치로 옮겨오고 C가 삭제되면 D가.....이런식으로 각 요소들의 위치가 빈번하게 변경됩니다. 그렇기 때문에

큐의 크기가 커지면 커질 수록 성능의 저하 문제가 심각하게 발생합니다. 이런 것을 보완하기 위해서 순환 큐가 등장하게 되었습니다.

1. 순환 큐(Circular Queue)

- 위 그림에서 보면 전단이 3, 후단이 10인 것을 알수 있다. 참고로 후단의 큐가 꽉차게 된다면 전단과 후단이 같아지면 큐가 비어 있는지 꽉차있는지 알수 없다. 실제로 후단은 실제 후단의 다음위치하며, 전단과 후단을 구분하기 위해 더미(Dummy)공간을 만드며 만들어진 배열의 크기는 실제 배열의 크기에 1을 더한 값을 갖는다.

즉 큐(Queue)의 사이즈에 +1을 더해준다. 

 - 전단과 후단이 같다면 비어있는 상태(Empty)

 - 후단의 다음 노드가 전단이면 꽉 찬 상태(Full)

2. 링크드 큐(Linked Queue) : 원형이 아닌 직선으로!

 - 링크드 큐의 경우는 링크드 리스트의 형태와 유사하다 그래도 전단에서 제거 연산이 이루어지는 것과 후단에서 

삽입이 이루어진다는 것은 변하지 않는다. 

 - 링크 큐는 삽입 연산때는 후단 노드의 다음 노드에 새롭게 노드를 추가하고, 제거 연산떄는 전단의 위치를 앞으로 옮기면된다.

- 링크드 큐의 경우는 순환 큐와 다르게 큐의 크기에 제한을 받지 않는다.(크기의 유연함)

 - 링크드 큐는 구현이 간단하다는 장점이 있으나, 노드를 제거하거나 삽입할 떄에 New, Delete 연산을 수행합니다. 

 - 반면에 환형 큐는고성능인 반면에, 구현이 링크드 큐보다 복잡하다는 단점이 있다.