[Swift 자료구조] 5. Queue 큐

Data Structure in Swift (Queue) - Part 5

swift-algorithm-club/Queue at master · kodecocodes/swift-algorithm-club

이 글은 위의 글들을 참고하여 작성되었습니다.

Queue 큐

큐는 대기열을 뜻한다.

사람들이 버스를 타기 위해 줄을 선 것을 생각하면 된다 - 먼저 줄을 선 사람부터 순서대로 버스에 탄다.

• 선형 자료구조
• 삽입 및 삭제 : 선입선출, 즉 FIFO(First In, First Out)로 동작한다.
  • 스택과의 차이점 : 큐는 가장 예전에 들어온 것부터 삭제하고, 스택은 가장 최근에 들어온 것부터 삭제한다.

Queue의 연산자

• Enqueue : 맨 뒤에 새 요소 삽입
• Dequeue : 맨 앞의 요소 삭제
• Front : 첫 번째 요소 조회
• Rear : 마지막 요소 조회

Queue의 사용

• BFS 탐색에 사용됨
• 멀티프로레스의 CPU 스케줄링에 사용됨
• 많은 작업을 비동기로 수행할 때 사용됨 (e.g. NSOperationQueue)

Queue의 종류

• Priority Queue 우선순위큐
  • 큐의 확장 버전으로, 모든 요소가 연관된 우선순위를 갖는다.
  • 하나 이상의 요소가 같은 우선순위를 가질 때는, 큐에 추가된 순서에 따라 동작한다.
  • e.g. CPU 스케줄링, 다익스트라 알고리즘
• Deque (Double Ended Queue) 덱
  • 큐 자료구조의 일반화된 형태. 시작점과 끝점(Front&Rear) 모두에서 삽입과 삭제를 허용함.
  • 스택과 큐의 연산을 모두 사용 가능하다.
• Circular Queue 원형 큐
  • 큐의 확장 버전으로, 시작점과 끝점이 이어져 있는 형태이다 (마지막 요소의 다음 요소 = 처음 요소)
  • Ring Buffer라고 생각하면 된다.
  • 큐의 크기가 고정되어 있을 때 사용하기 좋다.

Queue 구현하기

Queue를 구현하는 방식에는 여러 가지가 있다.

여기에서는 4가지 방법들을 소개한다.

1. 배열
2. 연결리스트 (Singly Linked List)
3. Two Stack
4. head 사용하기

설명 없이 구현 코드만 보고 싶다면 여기를 참고해 주세요.

Queue 구현하기 - (1) 배열

struct Queue<T>: CustomStringConvertible {

    private var elements: [T] = []
    public init() {}

    var isEmpty: Bool {
        elements.isEmpty
    }

    var peek: T? {
        elements.first
    }

    var description: String {
        if isEmpty { return "Queue is empty..." }
        return "---- Queue start ----\n"
            + elements.map({"\($0)"}).joined(separator: " -> ")
            + "\n---- Queue End ----"
    }

    mutating func enqueue(_ value: T) {
        elements.append(value)
    }

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

배열에 제공되는 메서드들로 큐를 구현하는 방법이다.

사실 이 방법은 큐를 구현했다기보다, 큐의 동작을 흉내냈다고 보는 게 맞다. 실전(알고리즘, 개발)에 쓰기에 너무 느리고 비효율적이기 때문이다.

• enqueue는 append()를 사용하므로 O(1) 이라 괜찮다.
• 그러나 dequeue는 removeFirst() 를 사용하는데, 이는 O(n) 의 시간복잡도를 가진다.
  • 배열이라는 자료구조에 공부해 본 적이 있다면, 배열의 첫 요소를 삭제하는게 얼마나 비효율적인지 알 것이다 - 맨 앞의 요소가 삭제되면 그 자리를 채우기 위해 나머지 요소들이 모두 한칸씩 앞으로 당겨져야 하기 때문.
• 또, 배열의 경우 요소를 자신의 크기 이상으로 삽입하면, 기존 크기보다 2배정도의 새 배열을 만들어 옮기는 작업이 필요하다(= 메모리 재할당)

이러한 문제들이 있기 때문에 (1) 배열로 큐 구현하기 방법은 사용하지 않는 것이 좋다.

아래에 이 문제들을 극복한 다른 구현방식이 제시되어 있다.

Queue 구현하기 - (2) 연결리스트(Singly Linked List)

class Node<T>: CustomStringConvertible {

    var value: T
    var next: Node?

    var description: String {
        guard let next = next else { return "\(value)" }
        return "\(value) -> " + String(describing: next)
    }

    init(value: T, next: Node? = nil) {
        self.value = value
        self.next = next
    }
}

struct Queue<T>: CustomStringConvertible {

    var front: Node<T>?

    var rear: Node<T>?

    init() { }

    var isEmpty: Bool {
        return front == nil
    }

    var description: String {
        guard let front = front else { return "Empty Queue" }
        return String(describing: front)
    }

    var peek: T? {
        return front?.value
    }

        mutating private func push(_ value: T) {
        front = Node(value: value, next: front)
        if rear == nil {
            rear = front
        }
    }

    mutating func enqueue(_ value: T) {
        if isEmpty {
            self.push(value)
            return
        }

        rear?.next = Node(value: value)
        rear = rear?.next
    }

    mutating func dequeue() -> T? {
        defer {
            front = front?.next
            if isEmpty {
                rear = nil
            }
        }
        return front?.value
    }
}

• front : 맨 앞 노드를 나타냄
• rear : 맨 뒤 노드를 나타냄
• enqueue : 맨 뒤에 요소 추가. O(1)
  • rear 참조값을 활용해 그냥 맨 마지막에 새 요소를 노드로 만들어 추가하면 된다.
• dequeue : 맨 앞의 요소 삭제. O(1)
  • 역시 front 참조값을 활용해 그냥 맨 마지막에 새 요소를 노드로 만들어 추가하면 된다.

다만 enqueue작업에서 매번 동적 메모리할당 시간이 소요된다.

Queue 구현하기 - (3) Stack 두 개를 사용해 구현 (two stacks)

일명 투스택이라 불리는 방법이다.

왼쪽 스택과 오른쪽 스택을 가지고 큐를 구현한다.

• Left Stack 왼쪽 스택
  • 모든 dequeue 연산을 여기에서 처리한다.
• Right Stack 오른쪽 스택
  • 모든 enqueue 연산을 여기에서 처리한다.

투스택 방식의 특징

• 배열에 기반한 구현방식임
  • 배열은 연속적인 인덱스에 따라 모든 값이 저장됨
  • 따라서 많은 양의 데이터를 첫 액세스에 캐시에 로드할 수 있다
• Circular Queue와 달리 크기 제한이 없다

struct TwoStackQueue<T>: CustomStringConvertible {

    var leftStack: [T] = []
    var rightStack: [T] = []

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

    var peek: T? {
        leftStack.isEmpty ? rightStack.first : leftStack.last
    }

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

    mutating func dequeue() -> T? {

        if isEmpty {
            return nil
        }

        if leftStack.isEmpty {
            leftStack = rightStack.reversed()
            rightStack.removeAll()
        }

        return leftStack.removeLast()
    }
}

extension TwoStackQueue {

    var description: String {

        if isEmpty {
            return "Queue is empty..."
        }
        var allElements: [T] = []
        if leftStack.isEmpty == false {
            allElements.append(contentsOf: leftStack.reversed())
        }
        allElements.append(contentsOf: rightStack)

        return "---- Queue start ----\n"
            + allElements.map({"\($0)"}).joined(separator: " -> ")
            + "\n---- Queue End ----"
    }
}

동작원리

• enqueue()
  • append(): Right Stack의 배열에 값을 추가한다. O(1) 의 시간복잡도를 가짐
• dequeue()
  • 만약 Left Stack과 Right Stack이 모두 비어있다면, 언더플로우 상황이 된다.
  • 만약 Left Stack이 비어있다면, Right Stack의 모든 요소를 순서를 뒤집어 Left Stack에 가져오고 Right Stack을 비운다.
  • removeLast() : Left Stack의 맨 끝 요소를 삭제한다.

Queue 구현하기 - (4) head를 사용해 구현

참고 : https://github.com/kodecocodes/swift-algorithm-club/tree/master/Queue#a-more-efficient-queue

(1)의 배열로 구현한 방식에서, dequeue에 해당하는 removeFirst() 가 O(n) 의 시간복잡도를 가지기 때문에 문제가 되었었다.

반대로 말하면 removeFirst() 대신 다른 방식으로 dequeue를 한다면 괜찮다는 이야기이다.

아래 구현방식은 배열로 만든 큐에서 앞의 요소를 직접 ‘지우는’ 대신, nil 을 할당하는 방식이다.

• 맨 앞의 요소의 인덱스를 나타내는 head 를 만든다
• 요소를 지우는 대신, 그 자리에 nil 을 할당하고 head 에 1을 더한다
  • O(1) 의 시간복잡도를 갖는다.
• 큐에서 head의 위치가 일정 인덱스 이상이 되면 (= nil이 어느정도 이상 많아지면), nil이 아닌 요소들을 앞으로 옮겨온다.
  • 이 작업은 O(n) 의 시간복잡도를 갖는다.

public struct Queue<T> {
      fileprivate var array = [T?]()
      fileprivate var head = 0

      public var isEmpty: Bool {
            return count == 0
      }

      public var count: Int {
            return array.count - head
      }

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

      public mutating func dequeue() -> T? {
            guard head < array.count, let element = array[head] else { return nil }

            array[head] = nil
            head += 1

            let percentage = Double(head)/Double(array.count)
            if array.count > 50 && percentage > 0.25 {
              array.removeFirst(head)
              head = 0
            }

            return element
      }

      public var front: T? {
            if isEmpty {
              return nil
            } else {
              return array[head]
            }
      }
}

• head : 배열에서 맨 앞에 있는 객체의 인덱스를 나타냄
  • head 는 array 의 전체 크기보다 작아야 한다
• enqueue() : 맨 뒤에 새 요소를 붙임. 달라진 점 없음. O(1)
• dequeue() : 가장 달라진 부분. O(1)
  • dequeue연산을 하면 배열의 맨 앞의 요소를 삭제해야 한다.
  • 이때 직접 삭제하는 대신, head 로 맨 앞 객체의 인덱스를 알아내고, 거기에 nil을 할당한다.
  • 그러면 삭제된 요소의 다음 요소가 첫 요소가 되므로 head += 1 을 해준다.

🤔 dequeue를 반복하면 nil이 점점 많아져서 array 에 사용하지 않는 공간이 커지는데 비효율적이지 않나요?

• 그래서 주기적으로 array 에서 nil들을 쳐내는 재배치 작업이 필요하다. 아래 코드가 그 역할을 한다.

let percentage = Double(head)/Double(array.count)
if array.count > 50 && percentage > 0.25 {
      array.removeFirst(head)
      head = 0
}

• 조건1 : array의 25% 이상이 사용되지 않고 있을 때
• 조건2 : array 의 크기가 50이 넘을 때
  • array 크기가 충분히 커졌을 때만 조건 확인 및 재배치하도록 함
  • 50이라는 숫자는 각자 상황에 따라 조정하면 된다.
• 재배치작업 : removeFirst(k:) 로, 배옆의 앞에서부터 head 개 만큼의 요소들을 없애고, head 를 0으로 재설정한다
  • 이렇게 하면 앞에 자리를 차지하던 nil 객체들이 사라진다.
  • head 는 첫 요소의 인덱스이면서 동시에 앞의 nil 인 요소들의 수를 나타내기도 하기 때문.

(참고) Circular Queue 구현하기 - Ring Buffer

일반Queue가 아닌 Circular Queue를 구현하는 방법이다.

만약 고정된 사이즈의 큐를 사용한다면, Circular Queue를 사용하는 것이 효율적이다.

struct RingBufferQueue<T>: CustomStringConvertible {

    private var elements: [T?]
    private var front = -1
    private var rear = -1

    init(count: Int) {
        elements = Array(repeating: nil, count: count)
    }

    var isEmpty: Bool {
        front == -1 && rear == -1
    }

    var isFull: Bool {
        ((rear + 1) % elements.count) == front
    }

    var description: String {
        if isEmpty { return "Queue is empty..." }
        return "---- Queue start ----\n"
            + elements.map({String(describing: "\($0)")}).joined(separator: " -> ")
            + "\n---- Queue End ----\n"
    }

    var peek: T? {
        if isEmpty { return nil }
        return elements[front]
    }
}

extension RingBufferQueue {

    // to enqueue an element
    mutating func enqueue(_ element: T) -> Bool {

        // if queue is empty
        if front == -1 && rear == -1 {
            front = 0
            rear = 0
            elements[rear] = element
            return true
        }

        if isFull {
            print("QUEUE IS FULL")
            return false
        }

        rear = (rear + 1) % elements.count
        elements[rear] = element
        return true
    }
}

extension RingBufferQueue {

    // to dequeue an element
    mutating func dequeue() -> T? {

        if isEmpty {
            print("QUEUE IS EMPTY")
            return nil
        }

        // if queue has only single element
        if front == rear {
            defer {
                elements[front] = nil
                front = -1
                rear = -1
            }
            return elements[front]
        }

        defer {
            elements[front] = nil
            front = (front + 1) % elements.count
        }
        return elements[front]
    }
}

• enqueue : O(1)
• dequeue : O(1)