[TIL #1] Swift에는 없는 자료구조: queue, deque

Swift에는 없는 자료구조인 queue와 deque를 O(1)로 어떻게 구현할까? 에 대한 질문을 받아서 확실한 대답이 아닌 추측으로 대답했는데 반은 맞은 것 같다.

 

reversed()의 시간 복잡도가 O(1)임을 알고 있었는데, 이를 통해서 queue와 deque를 구현할 수 있지 않을까 생각했었다.

그래서 살펴보니 reversed()의 리턴 타입이 ReversedCollection<Array<Element>> 였었고, 이 ReversedColleciton을 다시 살펴보니 BidirectionalCollection 프로토콜이 채택되어 있었고 이를 다시 살펴보니 원하는 결과를 얻었다.

 

BidirectionalColleciton이 단어 뜻 그대로 양방향콜렉션인데 index가 움직일 때마다 반대쪽에 위치하는 index도 동일하게 움직인다고 한다. 결국 reversed()의 모태인 BidirectionalCollection으로 인해서 반대편 index를 이용해 바로바로 결과를 보여주기에 O(1)이 가능했나보다.

 

 

##

Pingu라는 분께서 친절하시게도 직접 자료구조를 구현해서 소스코드를 올려주셨다. 참고해 보면 좋을 듯 하다.

https://icksw.tistory.com/212

[Swift] Queue(큐) 간단 구현

https://icksw.tistory.com/213?category=932556 

[Swift] Deque(덱) 간단 구현