Swift) DoubleStack - Queue

DoubleStack을 이용한 Queue

Queue를 하나의 Array로 만든다면, 첫번째 요소를 제거하려 removeFirst()를 호출할텐데 공식문서를 보면 시간복잡도가 O(n) 인 모습을 볼수 있다.

이는 첫번째 요소가 빠지고 그 뒤의 요소들이 앞으로 당겨지는 과정에서 발생하는 비용으로 인한 것이다.

그래서 그러한 단점을 보완한 DoubleStack 즉, Array 2개를 이용해 단점을 보완한다

 

하나의 Array에 먼저 enqueue 하여 요소를 넣어주고 dequeue할 때 다른 Array에 reversed()를 이용하여 넣어준다면 첫번째 배열의 첫번째 요소가 두번째 배열에선 마지막 요소가 되기에 dequeue하여 요소를 뺄 때 첫번째 요소를 뺴서 뒤의 요소들이 앞으로 당겨지는 비용이 쓰이지 않게 되어 시간복잡도가 O(1)이 되고, 요소가 많아도 비용이 늘지 않게 되는 것이다.