[선형 자료구조] 덱/데크(Deque)

덱(Deque)이란?

덱(Deque)은 큐와 스택의 특성을 모두 가지는 자료구조이다.

일반적인 큐와 달리, 덱은 양쪽 끝에서 삽입과 삭제가 가능하다.

 

- 양쪽 끝에서의 삽입/삭제: 덱은 양쪽 끝에서 삽입과 삭제가 가능하며, 이로 인해 여러 가지 패턴의 자료처리가 가능합니다.

- FIFO와 LIFO: 덱은 큐처럼 FIFO(First-In-First-Out) 방식으로도 동작할 수 있고, 스택처럼 LIFO(Last-In-First-Out) 방식으로도 동작할 수 있습니다.

 

구현

class Deque<T> {
    private var enque: [T]
    private var deque: [T] = []
    
    var isEmpty: Bool {
        return enque.isEmpty && deque.isEmpty
    }
    
    var count: Int {
        return enque.count + deque.count
    }
    
    init(_ collection: [T]) {
        self.enque = collection
    }
    
    func pushFront(_ element: T) {
        deque.append(element)
    }
    
    func pushLast(_ element: T) {
        enque.append(element)
    }
    
    func popFront() -> T? {
        if deque.isEmpty {
            deque = enque.reversed()
            enque.removeAll()
        }
        return deque.popLast()
    }
    
    func popLast() -> T? {
        if enque.isEmpty {
            enque = deque.reversed()
            deque.removeAll()
        }
        return enque.popLast()
    }
    
    func front() -> T? {
        if deque.isEmpty {
            return enque.first
        }
        return deque.last
    }
    
    func back() -> T? {
        if enque.isEmpty {
            return deque.first
        }
        return enque.last
    }
    
    func contains(_ elem: T) -> Bool {
        return enque.contains(elem) || deque.contains(elem)
    }
}
 
let deque = Deque([Int]())