Swift 자료 구조 - 원형 큐

안녕하세요 밀쿄 입니다.

오늘은 잡담없이 바로 시작합니다.

 

오늘은 원형큐라는 걸 갖고왔습니다

조금 어렵지만 금방 이해하실꺼라 믿습니다.

바로 원리부터 들어가보도록 하죠.

자 여기 손그림이 아니라 큐가 있습니다.

Read포인터랑 write포인터가 있습니다

이 상태에서 

write가 되면

이렇게 write가 증가합니다.

여기서 하나더 들어오면 아래 그림처럼

하나 더 늘어나겠죠?

여기서 이제 read를 하면..

이렇게 됩니다

Read가 하나 늘어나죠.

이렇게 가다가.. 큐가 다차면

write가 처음으로 돌아와서 오버라이드 합니다.

이렇게 가득차면 처음으로 돌아와서

원형버퍼 ,링버퍼, 뭐 그렇게 부릅니다.

참고로 저렇기 때문에 크기가 한정적입니다.

(반대로 애기하면 크기를 모르면 못 쓰겠네요 )

 

이걸 응용해서 큐를 만들껀데요

먼저 링버퍼부터 만들어봅시다

먼저 배열이랑 read랑 wirte 인덱스가 있어야겠네요.

먼저 배열, read랑 write 인덱스를 만들고

배열을 주어진 크기만큼 초기화하는 구문을 넣었습니다.

 

먼저 full 인 경우와 emty인 경우를 생각해봅시다

full인 경우를 생각해보면

그림1

이렇게 read를 단 한번도 하지 않고 write만 진행하면 더 이상 쓸 수 없게 됩니다.

흔히 생각하실 떄 오류가 있는게..(저만 그랬을 지 모르지만 )

예를 들어서

배열 크기가 5니까 인덱스가 4가 최대일꺼야...라고 생각하는

저같은 실수는 안하시길 바랍니다

 

이제 Empty 일 때는

Read 하고 Write가 일치하면

비어있겠죠?

( 따로 그림으로 설명 안하겠습니다 )

코드로 짜면 이렇게 되겠죠?

자 이제

먼저 write를 만들어야하는데..

write를 할 때 full인지 먼저 체크해야죠?

full 이면 읽기 실패했다고 false를 반환합니다

그리고 나머지 연산이 들어가는 이유는 

배열이 가득차 있지않은 경우에

writeIndex가 마지막에 도달해서

새로운 값이 들어가야하면 0번째 인덱스로 되돌리기 위해서 입니다.

위에 그림 1에서 read가 진행되었다는 예시를 생각해뵤면

read가 1이고 write가 5가 되고

새로운 write 명령이 들어오면 배열의 처음으로 돌아가야합니다

즉 5 (writeIndex) % 5 (array.count )는 0 이므로 처음으로 돌아갑니다

여기서 주의할 점은 defer이기때문에 index가 먼저일어나지 않는다는 점이죠.

 

같은 원리로 read를 작성해봅시다

read는 비어있는 큐를 읽으면 안되니까 비어있는지 확인해줍니다

아까와 같은 원리로 나머지 연산자를 사용했습니다.

이번에도 역시 defer가 있어서 index가 먼저증가하지 않는 다는점

그리고 읽기 완료된 공간은 nil이 된다는게 중요합니다.

 

자 이렇게하면 링버퍼의 작성이 끝납니다

이제 이걸 응용해서 큐를 만들어보겠습니다.

사실 함수명만 바뀌었네요.

 

이렇게 원형큐로 만든 enqueue와 dequeue

전부다 복잡도가 O(1)입니다.

 

(배열로 만든건 enqueue만 O(1)이고

dequeue는 O(n) 이었습니다. )

 

하지만..성능은 좋아졋지만

크기를 알아야하는 단점이 있네요.

 

 

제가 오늘 만든 소스는 아래와 같은 출처를 가집니다.

https://github.com/raywenderlich/swift-algorithm-club/blob/master/Ring%20Buffer/RingBuffer.swift

raywenderlich/swift-algorithm-club

https://store.raywenderlich.com/products/data-structures-and-algorithms-in-swift

Data Structures & Algorithms in Swift