[Data Structure] Queue

큐의 정의는 다음과 같다.

a linear data structure of ordered entries such that entries can be inserted at one end (called the rear) and removed at the other end (called the front)

즉, 한쪽 끝에서 삽입이 일어나고 반대쪽 끝에서 삭제가 일어나는 선형 자료구조를 의미한다.

LIFO(Last-In First-Out) 성질을 띄는 스택과는 다르게 FIFO(First-In First-Out) 성질을 띈다.
먼저 들어온 것이 먼저 나가는 형태를 띄며 일반적으로 줄을 서서 차를 탄다던가 하는 것을 생각하면 된다.

스택과 마찬가지로 응용분야 또한 아주 많다.

회문 인식하는데에 있어서 스택과 같이 사용되기도 하며 시뮬레이션에 자주 사용된다.

큐를 구현하는 것은 배열과 링크드리스트 모두 가능하다.
배열로 구현할 경우에는 여러가지 방법이 있다.
일반적인 배열을 그대로 사용하는 것을 선형 큐라고 하는데 선형 큐 형태로 사용하게 되면 데이터를 넣고 뺌에 따라서 자료가 뒷부분으로 이동하기 때문에 실제로는 자료구조에 공간이 있음에도 불구하고 사용할 수 없는 문제가 생길 수 있다.
이 경우에는 자료를 pop할때 배열의 앞쪽으로 shift하는 방식으로 해결할 수 있지만 shift라는 부가적인 연산이 필요하기 때문에 효율성을 목적으로 하는 자료구조의 목적에 부합되지 않는다.

그래서 배열의 시작과 끝이 붙어있다고 생각하여 자료구조를 구현할 수 있는데 그것을 원형 큐(Circular Queue)라고 한다.
원형 큐에서 생길 수 있는 문제점은 큐의 첫부분을 나타내는 front와 끝부분을 나타내는 rear를 기준으로 자료가 들어있는 비율을 결정하게 되는데 empty일때나 full일때나 front와 rear값이 같아지기 때문에 두개의 차이점을 구분할 수 없다.

따라서 해결책이 필요한데 첫째 해결책은 count 변수를 따로 두어 구분하는 것이다. 이것 또한 4바이트 사용만으로 기존의 연산들을 그대로 사용할 수 있기 때문에 효율적이다.
두번째로는 배열의 전체를 사용하지 않고 배열의 사이즈-1 만큼을 큐로 사용하는 것이다. 그리고 front를 빈 공간을 가리키도록 하면 empty인 경우에만 front와 rear가 같아지기 때문에 그 문제를 해결할 수 있다.