[Swift] 덱 구현해보기

덱

스택과 큐의 특성을 모두 갖는, 둘을 조합한 형태의 자료구조

덱의 ADT(Abstract Data Type)를 구성하는 핵심 함수 네가지의 기능은 다음과 같다.

- 앞으로 넣기

- 뒤로 넣기

- 앞에서 빼기

- 뒤에서 빼기

 

덱은 머리에서 추가와 삭제가 이뤄지는 것은 물론 꼬리에 위치한 노드에서 추가와 삭제가 이뤄진다는 점에서 양방향 연결리스트를 기반으로 덱을 구현하는 경우가 많고, 이는 덱 구현에 있어서 매우 좋은 선택이라 할 수 있다.

 

여기서 간단하게만 덱을 구현해보았다.

class Deque<T>{
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
}