ADT : Queue, 순환 큐 구현

Queue

삽입과 제거가 서로 다른 end에서 발생하는 자료구조.

새로운 요소가 삽입되는 끝은 'rear'라고 부르고 요소가 삭제되는 끝은 'front'이다.

처음 입력된 것이 가장 먼저 나가는 구조. (FIFO)

 

queue의 구현 

1. queue의 front를 queue[0]으로 구현한다.

Pop : queue[0]의 요소를 제거한다. (이 작업을 수행하면 모든 요소를 왼쪽으로 한 칸씩 옮겨야 함. n개의 element,O(n))

push : 자료구조에 요소를 추가한다. (O(1) array를 resizing하는 시간을 제외한다면.)

 

2. queue의 front를 변수로 구현한다.

항상 처음 위치를 가르키는 변수 fornt를 만든다.

Pop : queue[front]를 제거한다. (변수가 제거되면 front를 오른쪽으로 한 칸 옮긴다. O(1))

 

배열 queue의 capacity를 나타내는 capacity 변수가 있다고 가정하자.

처음 삽입된 요소를 뜻하는 front, 가장 최근에 삽입된 요소를 뜻하는 rear

front가 한 번이상 pop될 경우에는 front가 0보다 클 것이다. 그런데 insert가 계속되어서 capacity가 가득차게 된다면 낭비되는 메모리가 발생한다. (pop을 할 때마다 front를 오른쪽으로 옮기기 때문에) queue를 배열로 구현하면 이런 문제가 발생한다.. 모든 요소를 결국 pop한 만큼 왼쪽으로 shift 해주어야함. O(N) 시간 소요 발생

Circular queue

변수 front는 첫 요소의 앞의 장소를 가르키고 있다. pop 명령을 실행하면 시계 방향으로 한 칸 움직여 해당 요소를 삭제한다.

변수 rear은 가장 최근에 삽입된 요소를 가르킨다. insert명령 실행시 시계 방향으로 한 칸 움직여 해당 장소에 추가한다.

 

모든 배열 공간에는 이전 공간과 다음 공간을 가르키고 있다.

마지막 공간(capacity-1)의 다음 위치는 0을 가르킨다. 0의 이전 위치는 마지막 공간(capacity-1)을 가르킨다.

 

이 것을 보고 직접 구현해보자.

front와 rear가 같다면 empty를 뜻한다. 만일 가득차면 rear와 capacity가 같아지게 됨.

그래서 아래 이미지와 같이 queue가 가득차기 전에 queue의 capacity를 증가시켜야 함.

요소의 개수가 capacity-1과 같아지게 된다면 push할 때 아래의 과정을 거쳐야 함.

 

push의 구현

1. push를 할 때 queue가 가득찼다면 우선 array를 두배로 늘림.

2. 두배로 늘린 뒤 같은 크기의 새로운 queue를 생성함.

 

3. 0부터 시작하는 새로운 queue에 2번째 부분을 복사한다. (d 배열의 A와 B, 즉 queue[front+1] 부터 queue[capacity-1]를 의미함.)

4. 첫번째 부분을 복사해서 (queue[0]부터 queue[rear]까지) 새로운 queue의  붙여넣음.

 

pop의 구현

queue는 가장 처음 들어온 요소를 pop시켜야 함. front 변수는 항상 가장 먼저 들어왔었던 요소의 앞공간을 가르키고 있음.

pop할 땐 그 앞의 요소를 가르키게 해서 소멸자를 불러 삭제.

 

변수를 사용해 모든 공간을 사용할 수 있는 순환 큐를 만들 수도 있다.

예를 들어 lastop라는 변수를 만들어서 가장 최근에 실행한 operation을 기록할 경우

front와 rear가 같아졌을 때 비어있는 지 가득 차 있는지 알 수 있다. (예를 들면 lastop이 push일 경우 가득 차 있는 것이고, pop일 경우엔 비어있는 것이다.)