[자료구조] 큐(Queue)

큐란? 선입선출(First-Input, First-Out FIFO)구조를 가진 자료구조

 

 

 

위 그림처럼 가장 처음에 들어온 것이 가장 먼저 나갑니다. 이 그림을 보셨으면 큐가 어떤 구조인지 이해가 되실 것입니다.

 

그럼 이제 큐의 용어에 대해 좀 더 자세히 알아봅시다!

 

큐의 용어에는

- Front ( Head )

- Rear ( Tail )

- Put ( Insert )

- Get ( Delete )

 

- Queue Underflow

- Queue Overflow

 

- Linear Queue

- Circular Queue

가 있습니다.

 

우선 Front 와 Rear 에 대해서 알아봅시다.

 

Stack에서 Top과 Bottom 과 비슷한 의미입니다. 

 

하지만 Queue에서는 먼저 들어온 데이터를 Front 제일 나중에 들어온 데이터를 Rear 라고 합니다.

 

Queue는 스택과 달리 모양을 다양하게 만들 수 있기 때문에 이 점 잘 알아두시기 바랍니다.

 

 

위 그림은 1 2 3 ... 이런 식으로 숫자 순서대로 입력 된다고 할때의 모습입니다.

 

Front는 데이터들 중 가장 먼저 들어온 데이터를 의미합니다.

Rear는 데이터들 중 가장 마지막에 들어온 데이터를 의미합니다.

 

큐의 경우는 스택과는 다르게 Front와 Rear 모두 값이 변할 수 있습니다. Put이 되면 Rear가 변하구요. Get이 되면 Front가 변하겠죠.

 

그렇다면!! Put과 Get에 대해서 알아볼까요?

 

Put은 큐의 맨뒤에 데이터를 넣는 것입니다.

 

 

Get은 큐의 맨앞에 데이터를 빼는 것입니다.

 

 

위에서 보신 것처럼 Put 과 Get은 데이터를 추가하거나 제거할 때 사용됩니다. 그로 인해서 Front와 Rear이 움직이게 되구요. 이 Front와 Rear이 움직임으로 인해서 큐는 빈 공간을 좀 더 활용적으로 사용할 수 있습니다. 이 것에 대해서는 Queue Underflow와 Queue Overflow를 배운 후 알아보도록 하겠습니다.

 

그렇다면 Queue Underflow와 Queue Overflow란 무엇이냐!!!

 

큐 언더플로우는 큐가 비어있을 때 Get을 하는 경우에 발생합니다. 아무 데이터도 없는데 데이터를 달라고 하면 당연히 오류가 나겠죠?

 

큐 오버플로우는 큐가 꽉차있을 때 Put을 하는 경우에 발생합니다. 큐에 더이상 데이터를 저장할 공간이 없는데 데이터를 넣으려 한다면 데이터 손실이 일어나겠죠?

 

 

 

그럼 이제 아까 설명하려 했던 큐의 공간 활용성에 대해서 설명하도록 하겠습니다. 제가 지금까지 그림으로 설명한 큐는 모두 배열로 만들었을 경우를 가정하고 있습니다. 그렇다면 큐의 크기는 한정되어 있겠죠? 이 상황에서 Get과 Put을 여러번 해서 다음과 같은 상황이 됬다고 가정해봅시다.

 

 

 

이 상황에서 Put을 하려고 하면 큐는 꽉찬 상황이기 때문에 Queue Overflow가 발생하게 됩니다. 아래에 두 칸의 공간을 확보하고 있는데도 말이죠. 이런 특성을 가진 큐를 Linear Queue라고 합니다. 이런 특성의 큐를 가지고 있다면 Get을 통해 큐를 비우지 않는다면 더 이상 데이터를 Put할 수 없겠죠.

 

 

 

이러한 특성의 단점을 해결하기 위해서 나온 것이 Circular Queue입니다. 

 

 

 

큐를 마치 원처럼 생각하는 것입니다. 어차피 먼저 들어온 데이터는 Front로부터 찾으면 되기 때문에 비어있는 아래 공간에 데이터가 들어오더라도 문제가 없는 것이죠.

 

 

 

물론 큐가 비어있거나 꽉차있다면 Queue Underflow와 Queue Overflow는 발생합니다. 하지만 공간의 낭비를 줄이기 때문에 Linear Queue 보다는 Circular Queue가 더 좋은 것입니다.

 

그렇다면 Circular Queue만 설명하면 됬지 왜 Linear Queue까지 설명했을까요? 네 그것은 바로 배열에서 큐를 구현할 때에 한정된 이야기입니다. 링크드 리스트를 이용해서 구현한다면 Circular Queue를 구현하지 않더라도 Linear Queue를 이용해서 공간의 낭비를 줄일 수 있습니다.

 

 

 

큐를 작성할 때 배열을 이용하느냐 링크드 리스트를 이용하느냐 Linear Queue를 이용하느냐 Circular Queue를 이용하느냐는 여러분의 몫입니다^^. 그럼 이 것으로 큐에 대한 강의를 마칩니다.

[출처] 자료구조 - 큐(Queue)|작성자 임종수