자료구조(6) 큐

큐는 "선입선출" 구조의 자료구조이다. 때문에 FIFO(First-in , First-out) 구조의 자료구조라 불린다.

 

큐 역시 스택과 마찬가지로 배열을 기반으로, 그리고 연결 리스트를 기반으로도 구현이 가능하다.

 

처음 큐를 접하면 다음과 같이 생각하는 것이 보통이다.

"스택과 큐의 차이점이 앞에서 꺼내느냐 뒤에서 꺼내느냐에 있으니, 이전에 구현해 놓은 스택을 대상으로 꺼내는 방법만 조금 변경하면 큐가 될 것 같다"

하지만 큐의 구현모델을 알게되면 이보다는 큰 차이가 있다고 느낄 것이다.

 

큐의 배열 기반 구현

F를 참조하여 dequeue 연산을 하고, R을 참조하여 enqueue연산을 한다 (F=머리, R=꼬리)

"뒤로 넣고 앞으로 빼는 자료구조" // 이것만 외워도 큐의 원리가 쉽게이해된다.

 

잘못된 dequeue 연산 방법

1. dequeue 연산 시 반환할 데이터를 배열의 맨 앞부분에 위치시키는 방식.

이 방법을 적용하면 dequeue 연산 시마다 저장된 데이터를 한 칸씩 이동시켜야 하는 단점이 있다.

(삭제시키고 나서 배열의 맨 앞부분이 비워져있으니, 데이터들을 한칸씩 왼쪽으로 이동시켜야 한다.)

 

1. dequeue 연산 시 F를 이동(>)시킨다.(사실 이방식임 ㅋ 다만 배열의 맨처음부분을 비워주고 삭제시 F를 먼저 이동하고 삭제, 그리고 R을 위치를 배열의 끝에만 국한시키는것이 아니다(물론 F도) 싸이클을 돌 수 있게 해주면 됨) 이 방식을 취하게 되면 dequeue의 과정에서 데이터의 이동이 필요치 않다. 그저 F가 가리키는 위치만 한 칸 오른쪽으로 옮기면 그뿐이다. 하지만 이 방법도 완전하지는 않다.  왜냐하면 잦은 dequeue 연산으로 데이터가 배열의 끝에 저장되는 상황이 발생하면 더 이상  R을 오른쪽으로 이동시킬 수 없기 때문이다. 그런데도 dequeue 연산의 진행으로 인해 배열의 앞쪽은 비어있는 상황을 맞이하게 된다.

 

올바른 dequeue 연산 방법 (원형 큐 방식)

"R을 배열의 앞부분으로 이동시키면 된다. 그럼 추가로 dequeue 연산을 진행할 수 있다." 쉽게 말해서 R을 회전시키는 것이다. R이 배열의 끝에 도달하면, 다시 맨 앞으로 이동시켜서 R이 회전하게 만드는 것이다. 물론 R을 뒤쫓아 가는 F도 배열의 끝에 도달하면 회전해야 한다. 그리고 이러한 방식으로 동작하는 배열 기반의 큐를 가리켜 "원형 큐"라 한다. 논리적으로 배열이 원형의 형태를 갖춘다고 해서 붙여진 이름이다.

 

첫 번째 데이터가 추가되는 순간 F와 R이 동시에 그 데이터를 가르킨다. 그 녀석은 큐의 머리이자 꼬리이다.

 

큐가 꽉찬 경우나 텅빈 경우나 F가 R보다 한칸 앞선 위치를 가리킨다. 그리고 이것이 의미하는 바는 이렇다

"F와 R의 위치만 가지고는 꽉 찬 경우와 텅 빈 경우를 구분할 수가 없다!"

 

해결방법 : 배열의 길이가 N이라면 데이터 N-1개가 채워졌을 때, 이를 꽉 찬것으로 간주한다(이것만은아니고)

+Plus : NextPosInx 함수를 통해서 위의 조건을 만족하면 0을 return 하고 0 == front 일때 진짜로 데이터가 꽉찬걸로 간주한다.(배열의 마지막까지 데이터가 꽉찻음에도 dequeue의 특성상 데이터를 머리쪽부터 지우기때문에 배열의 앞쪽은 빈 상태일수도 있기때문이다.)  

(혹시나 해서 말하지만, F와 R의 위치는 계속 회전한다. 따라서 F와 R의 상대적 위치 차를 통해서 텅 빈 경우와, 꽉 찬 경우를 구분해야 한다. 물론 이렇게하면 저장공간 하나를 낭비하게 되지만, 실보단 익이 많다)

 

• 원형 큐가 텅 빈 상태 : F와 R이 동일한 위치를 가리킨다.
• 원형 큐가 꽉 찬 상태 : R이 가리키는 위치의 앞을 F가 가리킨다.

 

enqueue 연산 시, R이 가리키는 위치를 한칸 이동 시킨다음에, R이 가리키는 위치에 데이터를 저장한다.

dequeue 연산 시, F가 가리키는 위치를 한칸 이동 시킨다음에, F가 가리키는 위치에 저장된 데이터를 반환,소멸한다.

 

배열 기반의 큐라 하면 대부분의 경우 원형 큐를 의미한다고 봐도 무방하다.

 

큐의 연결 리스트 기반 구현

배열의 기반으로 큐를 구현하는 경우에는 몇가지 고려할 사항이 있었다. 하지만 연결리스트를 기반으로 구현하는 경우에는 의외로 신경 쓸 부분이 적다.

 

배열 기반 원형큐에 관해 다음판단이 잘못된 이유를 설명하였다

"스택과 큐의 차이점이 앞에서 꺼내느냐 뒤에서 꺼내느냐에 있으니, 이전에 구현해 놓은 스택을 대상으로 꺼내는 방법만 조금 변경하면 큐가 될 것 같다"

하지만 그 대상이 "연결  리스트 기반의 큐"라면, 위의 판단은 어느정도 옳다! 연결리스트를 기반으로 구현하면 앞서 논의한 고민거리들이 사라지기 때문이다. 하지만 다음과 같은 차이점이 있기 때문에 여전히 스택의 구현과 차이가 있다고 할 수 있다.

"스택은 push와 pop으로 이뤄지는 위치가 같은 반면, 큐는 enqueue와 dequeue가 이뤄지는 위치가 다르다."

 

연결리스트 기반의 큐에서도 원형 큐와 마찬가지로 front와 rear를 유지(사용)해야 한다. enqueue 연산과 dequeue 연산이 이뤄지는 위치가 다르기 때문이다.

 

enqueue함수의 경우 큐의 머리를 가리키는 front 뿐만 아니라 큐의 꼬리를 가리키는 rear도 있다는데 주의해야 한다. 이 때문에 노드의 추가과정이 둘로 나뉘기 때문이다.

 

• 첫 번째 노드가 추가될 때에는 F뿐만 아니라 R도 새 노드를 가리키도록 설정해야한다.
• 두 번째 노드가 추가될 때에는 F는 변함이 없다. 대신 R이 새 노드를 가리키게 해야 한다.

 

dequeue함수의 경우 이와 관련해서 다음과 같이 생각할 수 있다

"enqueue 함수의 구현과 마찬가지로 노드의 삭제과정도 둘로 나뉠꺼야!"

하지만 그렇지 않다! 노드의 삭제과정에서 신경 쓸 부분은 F 하나이기때문이다.

• F가 다음 노드를 가리키게 한다.
• F가 전에 가리키던 노드를 소멸시킨다.

데이터가 하나 남은 상황에서 데이터를 소멸시킨 시킨다고 가정하면, F에 Null이 저장된다. F는 마지막 노드를 참조하여 다음 노드의 주소 값을 얻게되는데 그 값이 Null이다.(enqueue 코드확인) 그런데 R에는 Null이 아닌 쓰레기값(마지막 노드가 소멸되면서 주소값이 의미없어짐으로)이 저장되어있는데 이것이 문제가 되지는 않을까? 문제되지 않는다! 우리는 QIsEmpty함수를 정의할 때에도 F에 저장된 값만을 참조하여 TRUE 또는 FALSE를 반환하도록 정의하였다. 이렇듯 큐가 텅 비었는지 확인할 때에도 F만을 참조하니, R에 쓰레기 값이 저장된 위의 상황은 문제가 되지않는다! 그리고 굳이 R에 Null을 넣을 필요가 없다면, dequeue의 과정은 둘로 나뉘지 않는다.