[자료구조] Queue

Queue

Queue란, 한쪽 끝에서 삽입, 한쪽 끝에서 삭제가 이루어지는 유한 순서 리스트이다

• First-in-First-out의 선입선출 방식
• 먼저 들어간 원소가 먼저 나가게 되는 구조
• 음식점 대기줄, CPU의 테스크 스케줄링등이 Queue의 방식의 예
• BFS에서도 Queue를 사용하여 탐색해야 하는 노드의 리스트로 사용한다

Swift에서 Queue 구현하기

swift에서 Queue를 쉽게 구현하려면 queue를 배열로 놓고 enqueue는 append()함수로, dequeue는 removeFirst함수로 대체할 수 있다

struct Queue<T> {
    private var queue: [T] = []

    public var count: Int {
        return queue.count
    }

    public var isEmpty: Bool {
        return queue.isEmpty
    }

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

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

하지만 위와 같은 queue는 dequeue()시 O(N)의 시간복잡도가 걸린다는 것을 알 수 있다.
그러므로 stack을 두 개 이용해 queue처럼 사용하는 방법을 사용한다.
inbox & outbox 두 개의 Stack으로, inbox 스택에서는 삽입만, outbox 스택에서는 삭제 연산만이 이루어지도록 한다.

• 삽입 연산
  enqueue시에는 inout 스택에 append()를 해준다
• 삭제 연산
  • 삭제 연산의 경우 살짝 복잡한데, outbox 스택이 비어있을 경우, inbox 값들을 거꾸로 뒤집어(reversed()) outbox 스택에 넣어준 후, outbox 스택의 맨 마지막 값을 pop해줍니다.
  • outbox 스택이 비어있지 않을 경우 outbox 스택의 맨 마지막 값을 pop해준다

 

class Queue<T> { 
    var inbox: [T] 
    var outbox: [T] = []
    var count: Int {
        return inbox.count + outbox.count
    }

    var isEmpty: Bool {
        return inbox.isEmpty && outbox.isEmpty
    }

    init(_ queue: [T]) {
        inbox = queue
    }

    func pushLast(_ element: T) {
        inbox.append(element)
    }

    func pushFirst(_ element: T) {
        outbox.append(element)
    }

    func popLast() -> T {
        if inbox.isEmpty {
            inbox = outbox.reversed()
            outbox.removeAll()
        }
        return inbox.popLast()!
    }

    func popFirst() -> T {
        if outbox.isEmpty {
            outbox = inbox.reversed()
            inbox.removeAll()
        }
        return outbox.popLast()!
    }
}