[자료구조] 큐(Queue)-1

 

이번에 보일 자료는 큐(Queue)이다.

 

큐는 바로 먼저 들어간 것이 먼저 나오는 선입선출(先入先出), FIFO(First-In, First-Out) 구조의 자료구조 이다.

 

큐도 스택과 같이 우리 주변에서 많이 살펴볼 수 있다.

 

예를 들자면..

 

이런 주사기가 있겠고.

 

이렇게 줄서기 등등

 

스택과 같이 큐도 그렇게 어렵지 않은 개념의 자료구조 이다.

 

간단하게 생각하기에는 "뭐 스택에서 조금만 바꿔주면 큐가 되겟네?" 라고 생각할 수 있다.

 

그럼 일단 큐의 배열 구현 모델을 살펴보자

큐에 데이터를 삽입할 때를 표현해본 것이다

여기서 F는 Front의 약자이고 R은 Rear의 약자로 F는 큐의 맨 앞 머리, R은 큐의 맨 뒤 꼬리를 가리키는 것이다.

 

그리고 삭제할 때를 살펴보자

이 그림에서 보이는 방식은 F가 고정되어있고 R이 움직이면서 삭제 하는 방식이다.

 

이렇게 삭제 할 경우, F가 없어도 충분히 구현 가능하며

중요한 점은 이렇게 삭제할 때마다 저장된 데이터를 한 칸씩 이동시켜야 하는 단점이 있다.

 

그러면 이렇게 하면 어떻게 될까?

위 그림에서는 앞 그림과 달리 R이 아닌 F가 이동하면서 삭제하고 있다.

위 그림에서는 이전 그림 방식과는 달리 지울 때 마다 이동시켜줄 필요가 존재하지 않는다.

 

하지만 이 방식에도 큰 문제점이 한가지 있다.

위의 그림은 배열의 끝까지 가서 저장되어버린 상황이다.

그 때문에 R을 더 이상 이동시킬 수 없다.

 

그래서 이렇게 하면 어떻게 될까 하고 생각해보면….

R을 앞의 빈 공간으로 옮기고 데이터를 저장한 상태이다.

 

이러한 순환은 이해가 쉽게 표현해보면 …

이렇게 원형으로 표현이 가능하다.

 

이러한 방식으로 동작하는 배열 기반의 큐를 가리켜 '원형 큐(circular queue)'라 한다.

 

원형 큐의 데이터 삽입을 표현한 것이다.

원형 큐의 데이터 삭제를 표현한 것이다.

 

이제 원형 큐를 이대로 구현만 해도 될 것 같지만 이러한 원형 큐에서도 문제점이 존재한다.

큐가 전부 가득 찼을 때와 전부 비었을 때를 살펴보면 ….

이제 문제점이 보이는 것 같다.

F와 R의 위치만 가지고는 둘의 경우가 같기 때문에 큐가 가득 찬 경우와 큐가 비어있는 경우를 구분이 불가능하다.

 

그래서 이를 해결하기 위한 일반적인 해결책은 다음과 같다.

배열을 가득 채우지 말고 배열의 길이가 n일 경우 n-1개 채워졌을 때 이것을 가득 찬 것으로 하자!

 

이로써 원형 큐를 구현 할 수 있게 되었다.

구현할 원형 큐의 특성은

• 데이터 삽입 연산 시 R을 한 칸 이동 뒤 R이 가리키는 위치에 데이터 저장
• 데이터 삭제시 F을 한 칸 이동 뒤 F가 가리키는 위치에 데이터 삭제
• F와 R이 같은 위치를 가르킬 때 : 원형 큐가 텅텅 빈 상태
• R이 가리키는 위치의 앞을 가리킬 때 : 원형 큐가 가득 찬 상태

 

다음글에 이를 바탕으로 원형 큐를 구현 하겠습니다.