[자료구조] Swift 로 Queue 구현하기

[자료구조] Swift 로 Queue 구현하기

코딩테스트 문제를 풀다보면 Queue 자료구조를 이용해야하는 경우가 종종 있습니다. 모든 경우에서는 잘 모르겠지만... Queue 자료구조를 import 해서 사용할 수 있는 Java 와 Python 등과는 달리 Swift 에서는 Queue 자료구조를 제공하고 있지 않습니다.

 

저는 그래서 코딩테스트 문제를 풀며 필요한 자료구조들을 struct 로 구현해둔 다음 필요할때마다 가져다 사용하는 편입니다. 오늘은 그 중 Queue 를 구현하는 2가지 방법에 대해 알아보겠습니다.

Array 를 Queue 처럼 사용하기

Array 의 내장 메소드 중에 removeFirst() 와 removeLast() 등이 존재하기 때문에 이를 잘 활용한다면 사실 Queue 와 비슷한 모양새를 낼 수 있습니다.

 

기본적으로 Queue 관련 메소드 중 삽입하는 enqueue, 삭제하는 dequeue 를 포함해서 몇가지 메소드를 구현해보겠습니다.

모든 타입을 활용하여 Queue 를 생성할 수 있도록 제네릭을 이용하여 구조체를 선언했습니다. 이후 빈 Array 를 선언합니다.

count, isEmpty

현재 Queue 내 원소들의 개수와 Queue 가 비어있는지를 알려주는 프로퍼티를 생성합니다.

enqueue, dequeue

Array 를 이용하여 Queue 를 구현하였기 때문에 원소 삽입은 배열 뒤쪽에서 진행됩니다. 그렇기 때문에 간단하게 append() 메소드를 이용해 enqueue 를 구현할 수 있습니다.

 

dequeue 같은 경우는 리턴값이 옵셔널로 지정되어 있습니다. 이는 Queue 가 비어있을때 dequeue 를 실행한다면 nil 이 리턴되기 때문입니다.

 

삭제는 앞쪽에서 이루어져야하기 때문에 removeFirst() 메소드를 이용해 구현되었습니다. 하지만 이러면 Array 내의 모든 인덱스를 한 칸씩 앞으로 당겨줘야 하기 때문에 O(n) 의 시간이 걸리게 됩니다. Queue 의 삭제는 O(1) 의 시간복잡도를 가지기 때문에 사실 적절한 방법은 아니라고 생각합니다.

clear

Queue 내의 보든 원소를 삭제하는 메소드입니다. removeAll() 메소드를 이용해 간단하게 구현했습니다.

Stack 을 2개 이용해 Queue 처럼 사용하기

위처럼 Array 를 Queue 처럼 사용했을때 삭제 시 O(n) 의 시간이 걸린다는 문제점이 있었습니다. 그래서 이번에는 Stack 을 2개 이용해 Queue 를 만들어 보겠습니다.

위 그림에는 inbox 와 outbox 라는 이름의 Stack 이 맞닿아 있습니다.

 

inbox 에서는 삽입만이 이루어지고, outbox 에서는 삭제만이 이루어집니다. 삽입할때는 inbox 에 원소를 push 해주면 정상적으로 삽입이 수행됩니다.

 

삭제 시에는 outbox 가 비어있거나 비어있지 않을때를 구분지어야 하는데, 비어있을 경우에는 inbox 의 값들을 거꾸로 뒤집어 outbox 에 넣어줍니다. 이후 outbox 의 맨 마지막 값을 pop 해주면 dequeue 와 같은 효과를 낼 수 있습니다.

 

inbox 의 값들을 거꾸로 뒤집는 reversed() 메소드는 O(1) 의 시간복자도를 가지기 때문에 삭제 시 O(n) 의 시간이 걸리는 위의 방법보다 빠르게 수행이 가능합니다.

 

outbox 가 비어있지 않을 때에는 그냥 outbox 의 맨 마지막 값을 pop 해주면 됩니다.

이 과정을 그림으로 확인해보겠습니다.

Queue 에 1, 2, 3 이라는 값을 순서대로 push 해줍니다. inbox 에서 삽입이 일어나기 때문에 정상적으로 삽입이 이루어집니다.

이후에는 Queue 에서 값을 dequeue 를 시도합니다.

위에서 언급한것과 같이 outbox 가 비어있기 때문에 inbox 의 값을 거꾸로 뒤집어 outbox 에 넣어줍니다. 뒤집힌 채로 Stack 에 삽입되었기 때문에 outbox 의 top 원소값은 1 이 됩니다.

 

이 때 outbox 에서 pop 을 진행합니다.

정상적으로 1이 삭제되는 모습을 확인할 수 있습니다.

 

저희는 1, 2, 3 이라는 값을 차례대로 삽입하였고, 가장 처음 삭제되는 원소는 1, 그 다음은 2와 3이 될 것입니다.

이렇게 Stack 2개를 이용하여 Queue 의 기능을 하게 구현할 수 있습니다.

dequeue() 메소드에는 @discardableResult 어노테이션을 추가했기 때문에 리턴값이 있지만 이를 활용하지 않더라도 warning 이 출력되지 않습니다.

 

이렇게 위에서 설명한것과 같이 inbox 와 outbox 라는 Stack 2개를 이용하여 Queue 를 구현해보았습니다.