[자료구조] 큐(Queue)

큐란?

큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO: First - In - First - Out)구조이다.

이러한 큐의 예로는 매표소에소 표를 사기 위해 늘어선 줄을 들 수 있다. 줄에 있는 사람들 중 가장 앞에 있는 사람(즉 가장 먼저 온 사람)이 가장 먼저 표를 사게 되고, 나중에 온 사람들은 줄의 맨 뒤에 서야 할 것이다.

 

큐도 스택과 마찬가지로 프로그래머의 도구로써 폭넓게 이용된다. 

보통 컴퓨터와 주변기기 사이에는 항상 큐가 존재하는데, 그 이유는 컴퓨터의 CPU와 주변기기 사이에는 속도 차이가 있기 때문에 CPU를 효율적으로 사용하기 위하여 큐가 존재한다.

예를 들면, 프린터는 속도가 늦고 상대적으로 컴퓨터의 CPU는 속도가 빠르기 때문에 CPU는 빠른 속도로 인쇄 데이터를 만든 다음, 인쇄 작업 큐에 저장하고 다른 작업으로 넘어간다. 프린터는 인쇄 작업 큐에서 데이터를 가져다가 인쇄한다.

https://yoongrammer.tistory.com/m/46

큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다. 이는 삽입과 삭제가 같은 쪽에서 일어나는 스택과의 다른 점이다.

큐에서 삽입이 일어나는 곳을 후단(rear)라고 하고, 삭제가 일어나는 곳을 전단(front)라고 한다.

 

is_empty & is_full 연산

추상 자료형 큐의 연산들은 추상 자료형 스택과 아주 유사하다. is_empty 연산은 큐가 비어있으면 TRUE를 반환하고 그렇지 않으면 FALSE를 반환한다. is_full 연산은 큐가 가득 찼으면 TRUE를, 그렇지 않으면 FALSE를 반환한다.

 

enqueue & dequeue 연산

가장 중요한 연산은 삽입과 삭제 연산인 enqueue와 dequeue이다. 

enqueue 연산은 큐에 요소를 추가하는 연산으로서 큐의 맨 뒤에 새로운 요소(rear)를 추가한다.

dequeue 연산은 큐의 맨 앞에 있는 요소(front)를 꺼내서 외부로 반환한다.

가득 찬 큐에 요소를 추가하려고 할 때 Overflow가 발생하며, 빈 큐에서 요소를 제거하려고 할 때 Underflow가 발생합니다.

위의 사진을 보면 enqueue와 dequeue 연산이 일어나면 데이터들이 들어온 순서대로 나가는 것을 알 수 있다. 따라서 스택과 달리 삽입, 삭제가 큐의 양끝에서 일어나기 때문에 양단을 잘 살펴보아야 한다.

 

구현 방법

1) 선형큐

큐도 스택과 마찬가지로 구현하는 방법이 여러가지지만 여기서 예를 들어볼 건, 가장 간단한 1차원 배열을 쓰는 방법이다.

위의 사진은 선형큐가 진행되는 과정이다.

 간단하게 설명하자면, 데이터가 증가하되면 rear를 하나 증가하고, 그위치에 데이터가 저장된다. 삭제할 때도 front를 하나 증가하고, front가 가리키는 위치에 있는 데이터를 삭제한다. 하지만 마지막 그림(f)와 같이 큐를 사용하면 할수록 front가 뒤로 밀려나게 되므로 마지막 공간의 front와 rear이 같아지게 되어 이미 이전에 할당된 front의 앞 공간은 쓸 수 없게 된다.

그렇다고 이를 해결하기 위해 front의 위치를 그대로 유지시키면서 삭제를 하려면 매번 뒤에 있는 데이터들을 전부 앞으로 옮겨야 한다.(실제 우리가 줄을 서서 차례를 기다리는 것을 생각하면 쉽다) 이는 오히려 삭제를 하는 것보다 데이터를 옮기는데 더 많은 연산을 하게 되기에 이것이 선형큐의 단점이고 이를 보완한 것이 원형큐이다.

 

2) 원형큐

배열의 앞부분이 비어 있더라도 사용하지를 못한다는 스택의 단점을 보완한 것이 원형큐이다.

즉, 원형큐는 배열을 선형이 아닌, 원형으로 생각는 것으로, front와 rear의 값이 배열의 끝에 도달하면 다음에 증가되는 값은 0이 되도록 하는 것으로 해결한다.

 

원형큐에서는 front와 rear의 개념이 약간 변경된다. 먼저 처기값은 -1이 아닌 0이다. 또한 front는 항상 큐의 첫 번째 요소의 하나 앞을, rear은 마지막 요소를 가리킨다. 

즉, 그림에서와 같이 처음에 front, rear는 모두 0이고 삽입 시에는 rear이 먼저 증가되고, 증가된 위치에 새로운 데이터가 삽입된다. 또한 삭제 시에도 front가 먼저 증가된 다음, 증가된 위치에서 데이터를 삭제한다.

 

front와 rear의 값이 같으면 원형 큐가 비어 있음을 나타낸다.

0번 index에 front == rear인 경우 포화 상태와 공백 상태를 구별하기위해 하나의 자리는 항상 비워둔다.

 

큐의 시간복잡도

•  Insertion O(1)
•  Deletioin O(1)
•  Search O(n)

큐의 삽입은 front에서만 일어나고, 삭제는 rear에서만 일어나기 때문에 시간복잡도는 늘 O(1)이지만 특정 데이터를 찾을 때는 이를 찾을 때까지 수행해야하므로 O(n)의 시간 복잡도를 가진다.