Swift 덱(Deque) 구현

덱 (Deque)

- 양방향으로 데이터를 삽입및 삭제가 가능 한 데이터 구조이다.

- 양쪽으로 push,pop이 가능하며 시간복잡도는 O(1)이다.

- push,pop을 자주 사용하는 알고리즘에서 효율이 좋다.

- Swift는 지원하지않고, 직접 구현해야하며, 두개의 배열로 구현한다.

 

 

import Foundation

// Deque
struct Deque<T> {
    var enqueue: [T]
    var dequeue: [T] = []

    init(enqueue: [T]) {
        self.enqueue = enqueue
    }
    var count: Int {
        return enqueue.count + dequeue.count
    }
    var isEmpty: Bool {
        return enqueue.isEmpty && dequeue.isEmpty
    }

    mutating func first() -> T? {
        if dequeue.isEmpty {
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.last
    }
    mutating func pushFront(_ element: T) {
        dequeue.append(element)
    }
    mutating func pushRear(_ element: T) {
        enqueue.append(element)
    }
    mutating func popFront() -> T? {
        if dequeue.isEmpty {
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()
    }
    mutating func popRear() -> T? {
        if enqueue.isEmpty {
            enqueue = dequeue.reversed()
            dequeue.removeAll()
        }
        return enqueue.popLast()
    }
}