[알고리즘] 선형 큐 문제점 및 한계

큐 자료구조는 들어온 것이 먼저 나가는 first in first out 구조입니다.

헷갈리신다면 양쪽이 뚫려있는 원통을 상상해보세요.

양쪽이 뚫려있는 원통에 공을 하나씩 넣으면 먼저 들어온 공이 먼저 나가겠죠.

이런 기본적인 큐 구조를 선형 큐라고 부릅니다.

들어오는 것을 enquene, 나오는 것을 dequene라고 합니다.

 

선형 큐에는 문제가 있습니다.

삽입과 삭제를 반복하다 보면 앞에 있는 인덱스가 비어있음에도 꽉 찼다고 인식할 수 있습니다.

그렇게 되면 비어있는 공간을 활용할 수 없습니다.

예를 통해 보도록 하죠.

가장 앞을 가르키는 것을 front, 마지막을 rear라고 부릅니다.

오른쪽에서 들어가 왼쪽으로 나간다고 하면 1,2,3이 순서대로 나갈 수 있습니다.

front는 1이고 rear에 있는 숫자는 3입니다.

dequene 과정은 front를 고정하고 rear인덱스를 늘리며 진행됩니다.

1,2가 나가고 공간이 비어있다면 3번째 큐에 값이 존재하기 때문에 앞에도 공간이 차있다고 인식합니다.

 

이를 해결하기 위해서 큐에서 요소를 빼낼 때 해당 요소 뒤에 있는 것들을 한 칸씩 앞으로 보내거나

원형 큐를 사용하면 됩니다.

다음 시간에는 원형 큐에 대해 알아보도록 하겠습니다.