#005_자료구조와 알고리즘_들어온 순서대로! 큐(Queue)

안녕하세요 삽잡이입니다.

지난 시간에 Stack을 배워봤으니, 이번 시간에는 Queue를 배워보도록 하겠습니다.

Queue와 같은 경우에는, 들어가는 순서대로 나갑니다.

어찌보면... 현실에 맞는 자료구조가 아닐지...

즉, 차례대로 자료를 보관하고 가장 오래전에 보관된 자료를 꺼내주는

First In First Out 방식의 자료구조 형식을 가지고 있습니다.

Queue에서는 보관할 위치를 꼬리에 보관한다고 하여 rear,

가장 앞에 것을 꺼낸다 해서 front

이 두가지의 위치를 알고 있을 필요가 있습니다. 

stack에서는 나가는 구멍과 들어오는 구멍이 하나이기에 위치정보 하나만 알아도 상관이 없었지만,

Queue는 나가고 들어오는 구멍들이 다르기에 두개의 위치정보를 알아야하는 것입니다.

자... 그렇다면 생각해봅시다...

보관할 위치가 바뀐다고 꺼낼 위치가 바뀌나요? 아니지요...

이해가 가시나요??

자... 아무튼... 지금 설명한 queue는 문제가 있습니다.

크기가 5인 queue가 있다고 가정해보겠습니다.

크기가 5일 때에는 보관된 개수와 관계 없이 5번만 보관하면 

데이터가 나가는 것과 관계 없이 보관을 못하는 문제가 발생하게 됩니다.

맞지 않습니까? 꺼내는 위치를 보관하는 front 따로

보관할 위치인 rear 따로 있기 때문에 이러한 문제가 발생하게 되는 것입니다.

그래서 현재 보관하고 있는 자료 개수를 기억해서

꽉 차지 않았다면 앞으로 이동시키는 방식을 제공하게 됩니다.

흔히들 circular 라고 말합니다. 맞습니다... 원형 큐라고 하지요...

이처럼... 계속 순환을 하게 만드는 것이지요...

현재 보관하고 있는 자료 개수를 기억하여서 꽉차지 않았다면, 앞으로 이동시킨다.

이런 것입니다. 하하...

front = (front +1) % 최대값;

을 하게되면 0 ~ 최대값-1 까지 계속 반복 시킬 수 있게 됩니다.

참고로 말씀드리자면, 순환 형식과 같이 비스무리한 공간을 사용할 때에도

나머지 연산을 많이 사용한다고들 합니다.

생각해보도록 하겠습니다... 

자료가 아무것도 없을 때에는 front와 rear의 값이 같습니다.

그런데 여기서 또 문제가 발생하게 됩니다....

뭐냐? 공간이 꽉 차게 될 때에도 front와 rear가 같게 되는 것이지요...

따라서 아래와 같은 완충 지대를 만들어줍니다.

이 완충지대는 front 앞을 보관하지 못하도록 약속을 하는 것이지요...

완충 지대에 오게 되면 꽉 찬 것이라고 생각할 수 있게 말입니다.

결론적으로,,

원형 큐에서 꽉 찬것에 대한 판단을 아래와 같이 할 수있게 됩니다.

front == (rear+1) % 최대값;

큐 같은 경우에는

일상 생활에서 겪을 수 있는 굉장히 상식적인 절차이기때문에

쉽게 이해하실 수 있으리라 생각합니다.

이상 글을 마치도록 하겠습니다.

이상 삽잡이였습니다~!