[Swift] Deque(덱) 간단 구현

안녕하세요 Pingu 입니다.🐧

 

Swift에는 Deque 자료구조가 따로 없어서 직접 만들어야합니다.😂

참고로 Deque는 앞뒤로 모두 삽입, 삭제가 가능한 자료구조입니다.

 

매번 만드는게 귀찮아서 이렇게 따로 글을 남기려고합니다.

 

Deque를 만드는 방법에는 다양한 방법이 있지만 이번 글에서는 간단하게 배열 2개로 만든 Deque를 만들었어요.

Swift에서는 배열을 뒤집는 reversed() 메서드의 시간복잡도가 O(1) 이므로 Deque와 같은 성능을 낼 수 있다고 봅니다.

 

Deque의 가장 기본적인 기능들만 구현했습니다.

 

감사합니다.

// Made by Pingu
class Deque<T: Equatable> {
    var enqueue: [T]
    var dequeue: [T] = []
    var count: Int {
        return enqueue.count + dequeue.count
    }
    var isEmpty: Bool {
        return enqueue.isEmpty && dequeue.isEmpty
    }
    var first: T? {
        if dequeue.isEmpty {
            return enqueue.first
        }
        return dequeue.last
    }
    init(_ queue: [T]) {
        enqueue = queue
    }
    func pushFirst(_ n: T) {
        dequeue.append(n)
    }
    func pushLast(_ n: T) {
        enqueue.append(n)
    }
    func popFirst() -> T? {
        if dequeue.isEmpty {
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()
        
    }
    func popLast() -> T? {
        var returnValue: T?
        if enqueue.isEmpty {
            dequeue.reverse()
            returnValue = dequeue.popLast()
            dequeue.reverse()
        } else {
            returnValue = enqueue.popLast()
        }
        return returnValue
    }
    func contains(_ n: T) -> Bool {
        return enqueue.contains(n) || dequeue.contains(n)
    }
    func removeAll() {
        enqueue.removeAll()
        dequeue.removeAll()
    }
}