[Swift] 백준풀이를 위한 Queue

백준을 풀고있는 어느날... 무수히 많은 시간초과를 겪은뒤 결국 Queue를 사용하기로 했다..

 

Queue란?

Queue를 구글에 쳐보니 대기줄이라는 뜻이 있다. Stack에서는 LIFO(Last In First Out) 즉, 제일 위에서만 데이터가 들어갔다 나갔다 한다고 보면 된다. 하지만 Queue는 FIFO(First In First Out)이다.

위의 그림과 같이 먼저 들어온 것이 먼저 나간다는 뜻이다. Queue에 넣는것을 enQueue, 꺼내는 것을 deQueue라고 한다. Stack에서와 달리 Queue는 앞부분과 뒷부분의 포인터가 필요하다.

 

Dequeue를 아래와 같이 만들어서 쓰는 이유는 Swift에서 배열을 사용할때 시간초과가 발생하기 때문... element를 모두 옮겨주는 과정이 있기 때문이라고 한다.

 

Queue

아래와 같은 원리가 있다.

enQueue에 순서대로 append하고, deQueue에서는 뒤로 append한다. 반대로 빼낼때는 enQueue, deQueue맨 뒤에서 빼낸다.

class Queue<T> {
    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 putLast(_ element: T) {
        enQueue.append(element)
    }
    
    func putFirst(_ element: T) {
        deQueue.append(element)
    }
    
    // 빈 배열에 removeLast()를 실행하면 컴파일 에러 발생
    // 빈 배열에 popLast()를 실행하면 nil이 return
    
    
    // popLast - deQueue를 enQueue로
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    // popLast - enQueue를 deQueue로
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
    
}