[Programming] Queue(큐): 선형 큐(Linear Queue), 원형 큐(Circular Queue)

Queue(큐)

---

Queue란?

Queue(큐)는 Data Sturcutre(자료구조)의 한 종류로써 간단한 방식을 사용하지만 많이 사용되는 Data Sturcutre이다. 선입선출이라고 불리는 FIFO(First Input First Output) 방식을 사용하고 있기에 가장 먼저 들어온 데이터가 제일 먼저 내보내지는 방식을 보인다.

큐의 종류는 대표적으로 선형 큐와 원형 큐가 있으며, 두가지 방식 모두 FIFO 방식이지만 형태의 차이에 따른 기능적 차이가 있다. 따라서 상황에 따라서 선형 큐를 사용하는 것이 효율적일 수 있고 반대로 원형 큐를 사용하는 것이 프로그래밍에 효율적일 수 있다.

 

Queue 용어

Queue를 프로그래밍에서 사용하기 위해서는 각 기능에 대한 용어가 어떤 것이 있는지 알아두는 것이 좋다. 프로그래밍 언어마다 Queue 명령어가 조금씩 다르다는 점을 유의해야 하며, 여기서 말하는 용어는 명령어가 아닌 공통적으로 사용하는 Queue에 대한 용어이다.

enQueue	데이터를 추가한다. rear + 1
deQueue	데이터를 출력 또는 내보낸다. front + 1
isFull	Queue가 Full 상태인지를 확인한다. rear = n-1 rear 값이 마지막 데이터값을 나타내면 Full 상태이다.
isEmpty	Queue가 empty 상태인지를 확인하다. front = rear
createQueue	Queue를 생성한다. front, rear
Qpeek	Queue에서 앞 쪽 데이터를 출력 또는 내보내지 않고 확인하는 용도로 사용한다.

 

선형 큐(Linear Queue)

선형 큐는 일자로 구성된 큐이다. 일반적으로 큐에 대해서 배울때 볼 수 있는 형태에 해당한다. 일렬로 구성된 큐가 앞쪽부터 데이터가 쌓이며 뒤쪽에 새로운 데이터가 추가된다. 데이터가 출력 또는 내보내 질 때는 앞 쪽 데이터부터 순서대로 내보내 진다. 아래의 그림을 참고하면 이해하기가 쉽다.

Enqueue와 Dequeue

위의 그림처럼 선형 큐의 경우에는 제일 먼저 들어온 데이터가 빠져나가고 뒤 쪽에 새로운 데이터가 더해지는 걸 확인할 수 있다. 하지만 문제는 제일 먼저 들어온 데이터가 내보내지고 모든 데이터가 새로운 공간으로 이동되어지는 것이 아니다. 내보내진 데이터의 공간은 두고 새로운 데이터가 추가적으로 더해질 뿐이다. 물론 데이터가 내보내질 때마다 모든 데이터 값이 새로운 공간(주소)으로 이동되도록 프로그래밍이 가능하다. 하지만 기본적인 선형 큐 방식에서는 이 부분이 포함되지 않기에 유의해야 한다. 결과적으로 선형 큐에 비어있는 공간이 있음에도 공간이 꽉 차 있다고 컴퓨터는 판단할 수 있다. 따라서 내보내지는 데이터만큼 데이터가 이동하거나 비어있는 공간으로 데이터가 추가되게끔 설정해줘야 한다. 또는 다음에서 살펴볼 원형 큐를 활용하는 방법도 있다.

앞 쪽 배열에 공간이 비어있지만 공간이 Full 상태로 인지한다.

 

원형 큐(Circular Queue)

원형 큐는 선형 큐가 가지는 문제점을 보완해서 나온 큐의 한 종류이다. 말 그대로 원형 방식을 취함으로써 기존의 선형 큐가 가지는 문제를 별도의 추가적인 설정 없이 해결할 수 있다. 원형 큐는 기존의 큐가 꽉 찬 상태(포화 상태)인지 아니면 공간에 여유가 있는지를 판단할 수 있어야 한다. 따라서 한 공간은 비워둠으로써 큐 공간 상태가 어떤지 판단이 가능하다. 이것을 기존에 enQueue가 rear +1을 했다면, 원형 큐에서는 (rear + 1)% arraysize == front를 통해 현재 배열 또는 공간이 포화상태인지를 확인할 수 있다. 아래 그림을 보면 이해하기가 수월하다.

(rear+1)%arraysize == front

 

원형 큐는 (rear + 1)%arraysize == front 공식을 기본으로 배열의 공간이 포화 상태인지를 확인하고 공간이 있으면 데이터가 추가되고 공간이 포화 상태이면 데이터가 출력되거나 내보내지는 순환 방식을 보이고 있다.