Swift 자료구조 구현

Deque

struct Deque<T> {
    private var array: [T?]
    private var head: Int
    private var tail: Int
    private var capacity: Int
    
    init(capacity: Int) {
        self.capacity = max(1, capacity)
        self.array = Array<T?>(repeating: nil, count: self.capacity)
        self.head = 0
        self.tail = 0
    }
    
    var isEmpty: Bool {
        return head == tail
    }
    
    var isFull: Bool {
        return tail == capacity - 1
    }
    
    mutating func pushFront(_ element: T) {
        if isFull {
            resize()
        }
        head = (head - 1) % capacity
        array[head] = element
    }
    
    mutating func pushBack(_ element: T) {
        if isFull {
            resize()
        }
        array[tail] = element
        tail = (tail + 1) % capacity
    }
    
    mutating func popFront() -> T? {
        if isEmpty {
            return nil
        }
        let element = array[head]
        array[head] = nil
        head = (head + 1) % capacity
        return element
    }
    
    mutating func popBack() -> T? {
        if isEmpty {
            return nil
        }
        tail = (tail - 1) % capacity
        let element = array[tail]
        array[tail] = nil
        return element
    }
    
    private mutating func resize() {
        var newArray = Array<T?>(repeating: nil, count: capacity * 2)
        for i in 0..<capacity {
            newArray[i] = array[(head + i) % capacity]
        }
        head = 0
        tail = capacity
        capacity *= 2
        array = newArray
    }
}

deque에서의 resize 함수 -> 배열의 크기를 더 늘리는 것, 

배열의 크기를 무한정으로 하고 싶은데, 안되는 경우 -> isFull 일때 resize 함수를 사용해서 배열의 크기를 늘리자. 

Deque는 pushFront, pushBack, popFront, popBack을 포함하고 있어야한다.