[Algorithm] Queue

오늘은 Queue에 대해 알아보자

Queue

Queue는 FIFO(First In First Out)의 특성을 가지고 있다.

즉 먼저 들어간 순서대로나가는 것이다

구조

public struct Queue<T> {
    private var data = [T]()
    public init() {}
    
    public mutating func enqueue(element: T) {
        data.append(element)
    }
    public mutating func dequeue() -> T?{
        return isEmpty ? nil : data.removeFirst()
    }
    
    public var size : Int {
        return queue.count 
    }

    public var isEmpty : Bool {
        return queue.isEmpty
    }
}

기본적인 함수

• Enqueue : Queue의 맨 뒤에 원소를 추가한다.
• Dequeue : Queue의 맨 앞에 원소를 삭제한다.
• Peek : Queue의 맨앞 데이터를 읽는다.
• Front : Queue의 맨 앞 index
• Back : Queue의 맨 뒤 index

삽입 — Enqueue

public mutating func enqueue(element: T) {
        data.append(element)
    }

삭제 — Dequeue

public mutating func dequeue() -> T?{
        return isEmpty ? nil : data.removeFirst()
    }

비효율적인 removeFirst()

removeFirst()는 값을 삭제하고 이동시키므로, O(n)의 시간복잡도를 가진다.

따라서 좀더 효율성이 좋은 코드를 만들어봤다.

배열을 가리키는 변수를 두어서, 한 칸씩 이동하는 것이다.

2개의 Stack을 사용한 Queue

public struct Queue<T> {
    private var leftStack = [T]() // dequeue stack 용
    private var rightStack = [T]() // enqueue stack 용
    public init() {}
    
    public mutating func enqueue(element: T) {
        rightStack.append(element)
    }
    public mutating func dequeue() -> T?{
        if leftStack.isEmpty {
          leftStack = rightStack.reversed()
           rightStack.removeAll()
        }
        return leftStack.popLast()
    }
    
    public var size : Int {
        return queue.count 
    }

    public var isEmpty : Bool {
        return leftStack.isEmpty && rightStack.isEmpty
    }

    public var peek : T? {
        return leftStack.empty ? rightStack.first : leftStack.last
    }
}

원리는 다음과 같다

i) enqueue, dequeue 할 Stack 2개를 만든다

ii) dequeue Stack이 비어있을 경우 enqueue Stack에 있는 값들을 dequeue Stack에 reverse 해서 넣는다.

iii) 이후 dequeue를 할 경우, 마지막값을 리턴한다.

이런식으로 하면 기존 dequeue가 O(n)인 것이 O(1)이 된다.