2024.03.12 - 큐(Queue)

• 자료구조의 큐(Queue)

큐는 먼저 추가된 데이터가 먼저 출력되는 선입선출(First-In First-Out : FIFO) 자료구조이다.

큐를 대기줄처럼 생각하면 좋다. 식당에서 대기하고 있는데 스택처럼 나중에 줄 선 사람이 먼저 식당에 들어가면 안 되지 않겠는가? 먼저 줄 선 사람이 먼저 식당에 들어가는 것처럼 큐도 먼저 담긴 데이터가 먼저 나간다. 

 

• 선형 큐(Linear Queue)

큐에 데이터를 넣는 과정

큐에서 데이터가 나가는 과정

 

큐에 데이터가 들어가는 과정을 EnQueue, 큐에서 데이터가 나가는 과정을 DeQueue라고 한다.

큐의 맨 앞의 데이터를 Front, 맨 뒤의 데이터를 Rear라고 한다.

EnQueue, DeQueue, Front, Rear

 

 

• 선형 큐의 문제점

앞의 데이터를 DeQueue하면 Front는 계속 뒤로 옮겨지고, 다시 데이터를 EnQueue하면 Rear도 뒤로 옮겨진다.

Rear가 선형 큐의 끝에 도달하면, Front앞에는 데이터를 담을 수 있는 공간이 남아 있는데 더이상 데이터를 담을 수 없는 상황이 생긴다. 이런 경우를 해결하기 위해 원형 큐가 등장했다.

 

 

• 원형 큐(Circular Queue)

선형 큐에서 Rear가 맨뒤에서 맨 앞으로 옮겨지는 것을 이해하기 쉽게 원형 큐로 표현

EnQueue를 하면 Front앞에 공간이 있는 한 Rear가 계속 옮겨갈 수 있다.

선형큐에선 Front 앞에 데이터가 들어갈 수 있는데 Rear가 맨 뒤에 위치해 데이터를 넣을 수 없었지만,  원형큐에선 Front 앞에 데이터가 들어갈 수 있으면 Rear가 계속 뒤로 옮겨가면서 데이터를 저장할 수 있다.

 

 

• 원형큐의 문제점

 

텅빈 원형 큐의 Front와 Rear가 위치가 같다고 했을 때, 가득찬 큐의 Front와 Rear의 위치도 같다.

Front와 Rear의 위치만으로는 큐가 꽉찬 경우와 텅 빈 경우를 구분할 수 없다는 문제가 생긴다.

 

이를 해결하기 위해서 원형 큐는 마지막으로 데이터를 넣을 수 있는 공간을 비워둔다.

 

 

• 개선된 원형 큐

 

개선된 원형 큐는 저장할 수 있는 데이터의 개수 -1 개의 데이터가 저장되었을 때 가득 찬 상태라고 생각한다.

 

 

• C#에서의 큐

C#에서는 일반화 된 Queue<T> 클래스로 원형 큐를 지원한다.

C#에서 지원하는 큐는 큐에 데이터가 꽉 찬 상태일 때 EnQueue하려고 하면, 알아서 저장 공간이 늘어난 새로운 큐에 데이터들을 복사하여 새로운 큐에 데이터를 넣어준다. 

 

- 큐를 선언하는 방법

Queue<자료형> 큐_이름 = new Queue<자료형>();

int형 데이터를 담는 큐 자료구조 myQueue

 

 

- 큐에 데이터를 넣고(EnQueue) / 빼보자(DeQueue)

큐_이름.EnQueue(넣을_데이터);    //큐의 Rear가 위치한 곳에 데이터를 담는다.
                                                         //Rear는 비어있는 다음 위치를 가리킨다.
큐_이름.DeQueue();                        //큐의 Front에 위치한 데이터를 반환하고 큐에서 제거한다.
                                                        //Front는 다음 데이터가 있는 위치를 가리킨다.

 

데이터가 10, 20, 30 순서로 쌓여서, 먼저 들어간 10이 먼저 출력된다.

 

※ 주의 사항

 

큐가 비어있을 때 Dequeue 하려고 하면 예외가 생긴다.

 

 

- 큐에 남은 데이터 개수 세기(Count)

큐_이름.Count     //스택에 담은 데이터 개수를 반환한다.