[Swift] Dequeue 구현하기

Dequeue는 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조로, 이를 통해 큐와 스택의 기능을 모두 수행할 수 있습니다.

 

Dequeue를 구조체와 배열을 이용해 구현할 수 있습니다.

제네릭을 활용하여 Dequeue 구조체를 정의하고, 주요 기능들을 구현해보겠습니다.

 

struct Deque<T> {
    private var enqueue: [T] = []  // 뒤쪽에서 요소를 추가/제거하는 배열
    private var dequeue: [T] = []  // 앞쪽에서 요소를 추가/제거하는 배열
    
    var count: Int {
        return enqueue.count + dequeue.count
    }
    
    var isEmpty: Bool {
        return enqueue.isEmpty && dequeue.isEmpty
    }
    
    var first: T? {
        return dequeue.isEmpty ? enqueue.first : dequeue.last
    }
    
    var last: T? {
        return enqueue.isEmpty ? dequeue.first : enqueue.last
    }
    
    mutating func pushFirst(_ n: T) {
        dequeue.append(n)
    }
    
    mutating func pushLast(_ n: T) {
        enqueue.append(n)
    }
    
    mutating func popFirst() -> T? {
        if dequeue.isEmpty {
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()
    }
    
    mutating func popLast() -> T? {
        if enqueue.isEmpty {
            dequeue.reverse()
            let returnValue = dequeue.popLast()
            dequeue.reverse()
            return returnValue
        } else {
            return enqueue.popLast()
        }
    }
}

 

위 코드에서는 Dequeue의 기본 동작을 구현했습니다.

1. pushFirst(_:): 앞쪽에 요소를 추가합니다. 시간 복잡도는 O(1)입니다.
2. pushLast(_:): 뒤쪽에 요소를 추가합니다. 요소를 배열의 첫 번째 위치에 삽입하므로, 시간 복잡도는 O(n)입니다.
3. popFirst(): 앞쪽에서 요소를 제거하고 반환합니다. 시간 복잡도는 평균 O(1), 최악의 경우 O(n)입니다.
4. popFront(): 뒤쪽에서 요소를 제거하고 반환합니다. 시간 복잡도는 평균 O(1), 최악의 경우 O(n)입니다.

이 Dequeue 구조체는 다음과 같이 사용할 수 있습니다

var deque = Deque<Int>()
deque.pushLast(1)
deque.pushLast(2)
deque.pushFirst(0)
print(deque.popFirst() ?? -1)  // 출력: 0
print(deque.popLast() ?? -1)   // 출력: 2
print(deque.count)             // 출력: 1
print(deque.isEmpty)           // 출력: false

 

이렇게 Dequeue를 사용하면, 큐와 스택의 기능을 모두 수행할 수 있는 유연한 자료구조를 만들 수 있습니다.