[Algorithm] 큐 구현하기 (Swift)

Swift에서 스택과 큐

Swift로 프로그래밍을 하다 보면 자료구조를 구현해줘야 하는 것들이 있다. 그중 하나가 큐이다. 스택의 경우 removeLast() 와 append(_:) 의 경우 complexity 가 O(1) 이기 때문에 배열에서 위와 같은 함수를 사용하여 그대로 구현할 수 있다.

따라서 스택은 구현이랄 것도 없다. 원래 있는 메서드를 개념에 맞게 사용하면 그것이 스택 자료구조이다.

var stack: [Int] = [1, 2, 3, 4, 5]
stack.append(6)

print(stack.removeLast()) // 6
print(stack) // [1, 2, 3, 4, 5]

 

하지만 큐의 경우 FIFO 이기 때문에 removeFirst() 메소드를 사용해야 하는데 문제는 complexity 가 O(n) 이라는 것이다. 당연하게도 배열의 첫 요소를 없애고 나머지 요소를 한 칸씩 앞으로 당기기 때문에 O(n) 이 나오는 것은 당연하다.

큐는 아래와 같이 구현하면 큐라고 할 순 있겠지만, 문제는 removeFirst() 할때마다 O(n) 의 시간이 걸린다는 것이다. 단순히 이렇게 구현하게 된다면 큐가 커질수록 시간은 오래 걸릴 것이다. (알고리즘 문제의 경우 무조건 시간초과가 난다)

var queue: [Int] = [1, 2, 3, 4, 5]
queue.append(6)

print(queue.removeFirst()) // 1
print(queue) // [2, 3, 4, 5, 6]

 

큐 구현하기

초 간단 버전

바로 removeFirst() 를 쓰지 않는 것...! 그냥 head 라는 인덱스를 사용하여 접근하는 것이다. 요소를 지우지 않고 계속 쌓는 느낌이다. 하지만 head는 큐에서 맨 앞요소를 사용할 때마다 1을 더해준다.

var queue: [Int] = [1, 2, 3, 4, 5]
var head = 0

queue.append(6)

print(queue[head]) // 1
head += 1
print(queue) // [1, 2, 3, 4, 5, 6]

 

굳이 복잡하게? 구현해보자면... enqueue, dequeue 로 큐를 편하게 쓰게 바꿀 수 있다.

import Foundation

struct Queue<T> {
    private var array: [T] = []
    private var head: Int = 0

    var isEmpty: Bool {
        return head >= array.count
    }
    
    var count: Int {
        return array.count - head
    }
    
    init() { }
    
    init(_ element: [T]) {
        array = element
    }

    mutating func enqueue(_ element: T) {
        array.append(element)
    }

    mutating func dequeue() -> T? {
        guard head < array.count else { return nil }
        let element = array[head]
        head += 1
        return element
    }
}

// 사용 예시
var queue = Queue([1, 2, 3, 4])
queue.enqueue(5)
print(queue) // Queue<Int>(array: [1, 2, 3, 4, 5], head: 0)
print(queue.count) // 5
print(queue.dequeue()) // Optional(1)
print(queue.count) // 4
print(queue) // Queue<Int>(array: [1, 2, 3, 4, 5], head: 1)

문제점

문제점은 딱 하나다 계속 배열이 쌓인다는 것, 결국 dequeue를 해도 메모리에서 해제가 되지 않기 때문에 계속 메모리를 차지하고 있는다는 것이다.

 

스택 두개와 .reversed() 로 큐 구현하기

이 아이디어는 Swift에서 reversed() 메소드의 complexity 가 O(1) 인 것을 활용하는 것이다.

inbox, outbox 를 사용한다. dequeue를 할 때, outbox 의 마지막 요소를 꺼내고, 만약 outbox가 없다면 inbox를 reversed() 로 뒤집어 준 뒤 outbox 에 넣어주고 다시 outbox 의 마지막 요소를 꺼내주면 된다. 이렇게 되면 메모리의 사용이 줄어들게 된다.

struct Queue<T> {
    private var inbox: [T] = []
    private var outbox: [T] = []
    
    var isEmpty: Bool {
        return inbox.isEmpty && outbox.isEmpty
    }
    
    var count: Int {
        return inbox.count + outbox.count
    }
    
    init() { }
    
    init(_ array: [T]) {
        self.inbox = array
    }
    
    mutating func enqueue(_ n: T) {
        inbox.append(n)
    }
    
    mutating func dequeue() -> T? {
        if outbox.isEmpty {
            outbox = inbox.reversed()
            inbox = []
        }
        return outbox.popLast()
    }
}

var queue = Queue([1, 2, 3, 4])
queue.enqueue(5)

print(queue) // Queue<Int>(inbox: [1, 2, 3, 4, 5], outbox: [])
print(queue.count) // 5
print(queue.dequeue()) // Optional(1)
print(queue.count) // 4
print(queue) // Queue<Int>(inbox: [], outbox: [5, 4, 3, 2])

 

.reversed() 에 대해서

그럼 여기서 의문이 생긴다. 어떻게 reversed() 의 시간복잡도는 O(1) 이 될 수 있을까? 다시 공식문서를 살펴보게 된다면 reversed() 가 반환하는 것은 새로운 배열이 아닌 ReversedCollection 임을 알 수 있다. 새로운 배열을 반환하는 것이 아닌 원본 배열의 요소를 직접 참조하는 방식으로 이루어 진다. 원본 컬렉션을 복사하지 않고 요소를 역순으로 순회할 수 있도록 하는 것이기 때문에 시간 복잡도가 O(1) 인 것이다.

 

의문점

원본배열을 바꾸어 봤지만 바뀐 6이 아니라 그대로 1이 나오게 되는데 생성 시점의 배열에 역순으로 접근하는 것 같다. 살짝 이부분이 이해가 가지 않는데, 좀더 메모리나 Swift에 대한 공부가 필요 할 것 같다.

var array = [1, 2, 3, 4, 5]
let reversedArray = array.reversed() // reversedArray는 원본 배열의 역순 뷰를 반환
array[0] = 6 // 원본 배열 변경

print(array)                 // [6, 2, 3, 4, 5]
print(Array(reversedArray))  // [5, 4, 3, 2, 1] reversedArray는 원본 배열의 이전 상태를 유지