[자료구조] 덱 ( Deque )

Double Ended Queue 를 줄여서 덱 ( Deque ) 이라고 부릅니다.

양 쪽에 뚜껑이 달린 프링글스같은 자료구조입니다.

덱의 가장 큰 특징은 양방향 데이터 추가, 제거가 가능한 큐 ( Queue ) 이며, 큐와 스택에 비해 자유도가 높습니다.

 

데이터는 처음 또는 마지막에 추가되므로,

스택, 큐와 동일하게 뒤에서 데이터를 추가할 경우 데이터의 추가는 O(1) 의 시간복잡도를 갖습니다.

앞쪽에서 데이터를 추가할 경우, 오버헤드를 방지하지 않는다면 데이터의 추가는 O(n) 의 시간복잡도를 갖습니다.

앞쪽에서 데이터를 추가할 경우, 오버헤드를 방지한다면 데이터의 추가는 O(1) 의 시간복잡도를 갖습니다.

 

데이터는 처음 또는 마지막에 제거되므로,

스택과 동일하게 앞에서 데이터를 제거할 경우 데이터의 제거는 O(1) 의 시간복잡도를 갖습니다.

앞쪽에서 데이터를 제거할 경우, 오버헤드를 방지하지 않는다면 데이터의 제거는 O(n) 의 시간복잡도를 갖습니다.

앞쪽에서 데이터를 제거할 경우, 오버헤드를 방지한다면 데이터의 제거는 O(1) 의 시간복잡도를 갖습니다.

 

Deque 를 이해하기 쉽게 그림으로 나타내면 아래와 같습니다.

덱_001

 

아래 그림과 같이 동작하게 됩니다.

front	Deque 에서 제일 앞에 있는 데이터 입니다.
rear	Deque 에서 제일 뒤에 있는 데이터 입니다.
enqueue front	Deque 앞에 데이터를 추가합니다.
dequeue front	Deque 앞의 데이터를 제거합니다. front 를 제거합니다.
enqueue rear	Deque 뒤에 데이터를 추가합니다.
dequeue rear	Deque 뒤의 데이터를 제거합니다. rear 를 제거합니다.

 

덱_002

---

구현

 

Deque 는 Swift 를 사용하여 아래와 같이 구현하며, 아래와 같이 사용할 수 있습니다.

// MARK: Deque 구현
struct Deque<T> {
    private var deque: [T] = []
    
    var count: Int {
        // Deque 의 길이를 반환합니다.
        return deque.count
    }
    
    var isEmpty: Bool {
        // Deque 가 비어있는지 true/ false 를 반환합니다.
        return deque.isEmpty
    }
    
    var front: T? {
        // Deque 의 front 를 반환합니다.
        return deque.first
    }
    
    var rear: T? {
        // Deque 의 rear 를 반환합니다.
        return deque.last
    }
    
    mutating func enqueueFront(_ elememt: T) {
        // Deque 의 맨 앞에 데이터를 추가합니다.
        deque.insert(elememt, at: 0)
    }
    
    mutating func dequeueFront() -> T? {
        // Deque 의 맨 앞의 데이터를 제거합니다.
        if isEmpty {
            return nil
        } else {
            return deque.removeFirst()
        }
    }
    
    mutating func enqueueRear(_ element: T) {
        // Deque 의 맨 뒤에 데이터를 추가합니다.
        deque.append(element)
    }
    
    mutating func dequeueRear() -> T? {
        // Deque 이 맨 뒤의 데이터를 제거합니다.
        if isEmpty {
            return nil
        } else {
            return deque.removeLast()
        }
    }
}


var mDeque = Deque<Int>()

mDeque.enqueueFront(10)		// 데이터 추가, 앞
mDeque.enqueueFront(20)		// 데이터 추가, 앞
mDeque.enqueueRear(30)		// 데이터 추가, 뒤
mDeque.enqueueRear(40)		// 데이터 추가, 뒤

mDeque.isEmpty			// 비어있는지 확인
mDeque.count			// 길이 확인
mDeque.front			// 앞의 값 확인
mDeque.rear			// 뒤의 값 확인

mDeque.dequeueFront()		// 데이터 제거, 앞
mDeque.dequeueFront()		// 데이터 제거, 앞
mDeque.dequeueRear()		// 데이터 제거, 뒤
mDeque.dequeueRear()		// 데이터 제거, 뒤

 

Swift 자체에는 지원하지 않으니 Deque 를 사용하려면 직접 구현해서 쓰셔야 합니다 ^^.

 

P.S

23.02.18 - 오버헤드에 관한 내용은 곧 추가하도록 하겠습니다.

추가적으로 생각나거나 찾은 내용은 날짜를 덧붙여 업데이트 하겠습니다.