[자료구조] Deque

Deque

Deque(덱 .. ?)은 스택과 큐를 합친 자료구조이다.

 

• Stack : 한쪽에서만 삽입, 삭제가 가능하다.
• Queue : 한쪽에서는 삽입만, 한쪽에서는 삭제만 가능하다.
• Deque : 양쪽에서 삽입/삭제가 가능하다.

 

Deque (Double Ended Queue)
: 양쪽 끝에서 삽입과 삭제가 가능한 자료구조

 

언제 사용하는데?

그 특징에서 알 수 있는 것처럼 특정 배열에 데이터를 앞/뒤 모두 넣었다 뺐다 할 때 효율적으로 사용할 수 있다.

 

실제로 양쪽에 삽입/삭제가 필요한 경우는 그렇지 많지 않아서

보통 스케줄링 할 때 많이 사용한다고 한다.

 

우리같은 경우는 .. 알고리즘을 풀 때 많이 사용하게 될텐데 ..

만약 !! 알고리즘을 풀 때 반복문 중첩이 없는데 시간 초과가 뜬다면 ?! Deque을 의심해볼 수 있다.

 

 

어떻게 구현하는데?

놀랍지도 않지만 Swift에는 Deque 자료 구조가 따로 없기 때문에 직접 구현해야한다.

만드는 방법은 여러개가 있을 수 있지만 간단하게 배열 2개로 만들 수 있다.

 

 

전체 코드 블럭은 [더보기]를 통해서 볼 수 있다.

class Dequeue<T: Comparable> {
    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 pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
    
    func firstIndex(_ num: T) -> Int {
        let newQue = deQueue.reversed() + enQueue
        if let i = newQue.firstIndex(where: {$0 == num}) {
            return i
        }
        return 0
    }
}