ForestBird

큐(Queue)는 FIFO(First-In First-Out)형식으로 먼저들어온 데이터가 먼저 빠져나가게 된다.

스택을 구현해봤다면 큐도 쉽게 만들 수 있다.

하지만 이런식으로 구현하면 Dequeue를 할 때마다 앞공간이 비워지게 되고 데이터는 계속 쌓이게 된다.

시간이 지나면 데이터는 1개밖에 없는데 큐의 크기는 훨씬 커져 있어서 빈 공간을 낭비하고 있게 된다.

빈 공간을 채울려면 Pop할 때마다 모든 데이터를 앞 쪽으로 한칸씩 옮겨야 하는데 데이터가 무수히 많다면 성능에 좋지 않을것이다.

그래서 나온 것이 원형 큐(circular queue)이다.

간단하게 설명하면 원형 큐에 데이터를 넣을 때 뒷공간에 빈자리가 없다면, 앞 공간의 빈자리에 데이터를 채워넣게 되서 빈 공간을 낭비없이 사용하게 된다.

여기서 내가 추가로 구현한 것은 '동적 원형 큐'이다.

원형 큐를 구글링해보니까 대부분 fixed array를 사용하던데, fixed array를 사용하면 원형큐의 모든 공간이 꽉차면 데이터를 추가할 수 없게된다. 

동적 원형 큐는 벡터(vector)처럼 언제든 큐의 크기를 재할당을 해서 빈공간을 만드는 방법이다.

결국 3개의 큐를 구현하게 되었다

1. 기존방식의 동적배열을 이용한 큐

https://forestbird0.tistory.com/44

2. 원형 큐

https://forestbird0.tistory.com/45

3. 동적 원형 큐

https://forestbird0.tistory.com/47