[자료구조] 큐(Queue)... So cute...

 

안녕하세요. 오늘은 자료구조 큐에 대해서 알아보겠습니다.

 

큐는 스택과 비슷합니다. 하지만 작동하는 방식이 약간 다르고 스택의 탑과 바텀을 큐에서는 다른 말로 표현합니다.

 

 

 

스택에서 요소를 스택의 탑에 추가했던 것처럼 큐는 rear(or back)에서 요소를 추가합니다. 

또한 요소의 삭제는 스택의 탑에서 일어났지만 큐는 front에서 일어납니다.

 

큐는 스택처럼 가장 먼저 입력된 데이터가 맨 아래 쌓이고 가장 나중에 입력된 데이터는 맨 위에 쌓이는 구조입니다.

 

하지만 스택에서처럼 입출력이 맨 위에서만 일어나지 않습니다.

 

위에서 설명드린바와 같이 입력은 rear 출력은 front에서 일어납니다. 

 

이러한 구조를 FIFO(First in, First out)이라고 합니다. 

 

먼저 들어온 녀석이 먼저 나간다는 것입니다.

 

이 각각의 큐의 공간에 저장되는 데이터를 요소(Element)라고 합니다.

 

큐에서도 삽입 연산과 삭제 연산이 일어난다고 말씀드렸는데요. 한번 알아보겠습니다.

 

삽입연산(enqueue)는 큐의 rear에서 일어나며, 이때 rear를 1 증가시키고 rear번째 인덱스에 요소를 삽입합니다.

 

따라서 rear는 마지막 요소가 있는 인덱스를 가리키는 변수가 될겁니다.

 

삭제연산(dequeue)는 큐의 front를 1증가시키고 그 곳의 요소를 반환합니다. 

 

따라서 front는 dequeue가 일어난 후의 첫번째가 된 인덱스-1을 가리키는 변수가 됩니다.

 

삭제연산의 과정은 스택에서의 pop과 비슷합니다. pop은 top을 1 감소 시켰고 여기서는 증가시켰지만 메커니즘은 비슷합니다. 그리고 반환 후 메모리 공간에 남아있는 요소를 쓰레기 값 취급한다는 것이 비슷합니다.

 

만약 큐에 요소가 하나도 없다면 empty라고 하며, 큐가 가득찼다면 full이라고 합니다.

---

큐의 과정들을 추상화해보면 코드를 작성하실 때 좀 더 편하게 작성하실 수 있어요

 

큐의 연산들은 다음과 같이 있어요.

 

init(): 큐를 초기화한다.

is_empty(): 스택이 비어있으면 TRUE, 아니면 FASLE를 반환한다.
is_full(): 스택이 가득 차 있으면 TRUE, 아니면 FASLE를 반환한다.

size(): 큐 내의 모든 요소들의 개수를 반환한다.

enqueue(element): 큐의 rear를 1 증가시키고 그곳에 요소를 추가한다.

dequeue(): 큐의 front를 1증가시키고 그곳의 요소를 반환한다.

 

이 정도면 충분합니다.

 

이제 enqueue와 dequeue를 좀 더 자세히 보겠습니다.

 

enqueue

1. 큐가 가득 차 있는지 확인한다.

2. 가득 차 있다면 오류를 발생하고 과정을 종로한다.

3. 가득 차 있지 않다면 rear를 1 증가시킨다.

4. rear에 요소를 삽입한다.

 

dequeue

1. 큐가 비어있는지 확인한다.

2. 비어있다면 오류를 발생하고 과정을 종료한다.

3. 비어있지 않다면 front를 1 증가시킨다.

4. 큐의 인덱스가 front인 곳의 요소를 반환한다.

 

그림으로 표현한다면 다음과 같이 표현할 수 있습니다.

 

enqueue와 dequeue를 살펴보겠습니다.

#define MAX_QUEUE_SIZE 10

typedef struct {
  int key;
} element;

element queue[MAX_QUEUE_SIZE];

void euqueue(element item) {
  if(rear == MAX_QUEUE_SIZE-1)
    queueFull();
  queue[++rear] = item;
}

element dequeue() {
  if(front == rear)
    return queueEmpty();
  return queue[++front];
}

 

enqueue함수를 살펴보면 element 타입의 요소를 매개변수로 받고 있습니다. 이후에 if문을 통해 queue가 꽉 찬 상태인지 점검합니다.

 

만약 꽉 차있다면 queueFull() 함수가 프로그램을 종료할 것입니다.

 

그렇지 안다면 rear를 1 증가 시키고 그곳에 요소를 추가합니다.

 

이번엔 dequeue함수를 살펴봐요.

 

dequeue함수도 enqueue함수처럼 큐의 상태를 먼저 확인해줍니다. 만약 front와 rear가 같다면 큐가 비어있는 상태이기 때문에 queueEmpty()함수가 호출되어 프로그램이 종료합니다.

 

그렇지 않다면 front를 1 증가시키고 그곳의 요소를 return 해줍니다.

---

좀 더 자세히 살펴보겠습니다.

rear와 front를 통해서 큐의 요소에 접근하는데 rear와 front는 계속 증가만 합니다.

 

그러면 요소를 삽입하면 인덱스는 계속 증가하는데, 삭제할 때는 증가한 인덱스가 돌아오지 않고 맨 앞의 front가 증가하기 때문에 언젠간 분명 공간이 있음에도 불구하고 큐가 가득 찼다고 주장하는 상황이 발생합니다.

 

이게 배열로 큐를 만들었을 때의 문제점입니다. 이를 해결하기 위해서는 rear가 배열의 끝에 도달하였을 때 다음에는 배열의 처음으로 돌아오게 하면 됩니다. 

 

front도 마찬가지 입니다!!

 

이는 나머지 연산자를 통해서 구현할 수 있는데 생각보다 간단합니다. 

 

만약 어떤 수를 100으로 나눈 나머지를 구한다고 한다고 하겠습니다. 여기서 어떤 수가 0부터 99라면 100으로 나눈 나머지도 0부터 99가 그대로 나오겠죠.

 

하지만 100을 100으로 나눈 나머지는 0이 됩니다. 

 

이를 이용하면 구현이 간단할 겁니다.

 

이는 마치 순환하는 것처럼 생겼다고 하여 원형큐(Circular queue)라고 합니다.

원형 큐는 비어있는 상황이라면 front와 rear가 같은 상황일 것입니다.

 

다음과 같이 요소들이 추가되고 삭제되는 상황을 거치다 보면 원형 큐가 가득 차는 상황이 올 겁니다.

짠! 드디어 원형큐가 우여곡절 끝에 가득 차버렸습니다.

처음에 저희는 큐가 비어있는 상황을 rear와 front가 같은 상황이라고 했는데 가득 찬 상황도 rear와 front가 같아져버렸습니다.

 

따라서 front == rear를 판단하여서 큐가 가득찬 것인지 비어있는 것인지 알 수가 없게되었는데 이때는 어떻게 해야할까요?

 

사이즈 변수를 이용하면 편할것 같습니다. 사이즈 변수를 하나 선언하고 요소를 추가한다면 +1 삭제한다면 -1을 통해 큐 안에 요소가 얼마나 있는지를 추가적인 조건으로 활용한다면 큐가 정말 꽉찬것인지 비어있는지 판단할 수 있겠습니다!!

 

이제 코드를 통해서 알아보겠습니다.

void enqueue(element item) {
  rear = (rear + 1) % MAX_QUEUE_SIZE;
  if(front == rear) 
    queueFull();
  queue[rear] = item;
}

element dequeue() {
  if(front == rear)
    return queueEmpty();
  front = (front + 1) % MAX_QUEUE_SIZE;
  return queue[front];
}

요소를 삽입하는 과정은 linear queue와 비슷합니다. 하지만 rear가 증가하는 방식이 다릅니다.

 

위에서 mod연산자를 이용하여 큐가 linear queue의 모순적인 점을 해결할 수 있다고 말씀드렸는데 지금 그 방법을 사용했습니다.

 

rear = (rear + 1) % MAX_QUEUE_SIZE를 통해서 rear를 1 증가시킨 값이 MAX_QUEUE_SIZE가 되면 rear를 다시 처음으로 돌아가도록 해주었습니다.

 

이는 당연히 front에도 동일하게 적용되겠습니다.