💥 Queue 구현하기

• Queue를 구현할 경우, 필수적으로 구현해야될 메소드가 몇가지 있다.
  • enqueue
  • dequeue
  • count
  • isEmpty
  • …
• 일반 array로 구현하는 것보다 double stack으로 구현할 경우 dequeue시, 시간 복잡도면에서 이득을 볼 수 가 있다.

☀️ Array를 통한 Queue 구현

• 일반 array로 queue를 구현해보면 아래와 같이 구현할 수 있다.

struct QueueArray<T>: Queue {
  private var array: [T] = []
  var isEmpty: Bool {
    return array.isEmpty
  }
  var peek: T? {
    return array.first
  }
  
  mutating func enqueue(_ element: T) {
    array.append(element)
  }
  
  @discardableResult
  mutating func dequeue() -> T? {
    return isEmpty ? nil : array.removeFirst()
  }
}

☀️ Double stack을 통하여 queue를 구현

• Double stack을 통하여 queue를 구현해주면 아래와 같이 구현해 줄 수 있다.
• 해당 방법은 일반 array일 때보다, dequeue시에 큰 이득을 얻을 수 있다.
  • 일반 array - dequeue ⇒ removeFirst() ⇒ O(n)
  • Double stack - dequeue ⇒ O(1)

struct QueueStack<T>: Queue {
  private var dequeueStack: [T] = []
  private var enqueueStack: [T] = []
  
  var isEmpty: Bool {
    return dequeueStack.isEmpty && enqueueStack.isEmpty
  }
  var peek: T? {
    return !dequeueStack.isEmpty ? dequeueStack.last : enqueueStack.first
  }
  
  mutating func enqueue(_ element: T) {
    enqueueStack.append(element)
  }
  
  @discardableResult
  mutating func dequeue() -> T? {
    if dequeueStack.isEmpty {
      dequeueStack = enqueueStack.reversed()
      enqueueStack.removeAll()
    }
    return dequeueStack.popLast()
  }
}

• 나머지 연산은 동일한 시간 복잡도(O(1))을 갖지만, dequeue시에는 Double stack으로 queue를 구현하는 것이 시간복잡도면에서 더 유리하다.

---

📚 참고자료

Swift로 구현한 Queue 와 더블스택