[Data Structures] Queue - Double-stack Implementation

Queue

링버퍼를 사용하는 방법도 보긴 해야하지만… 그건 추후에 보기로 하고 이번엔 스택 두 개로 큐를 구현하는 걸 확인해보자.

Stack 두 개로 Queue 구현해보기

개념은 간단하다. element를 넣을 때는 right stack 으로 넣는다. element를 빼야할 때는 left stack으로 모두 옮긴 뒤 top의 element를 제거한다. (FIFO를 지키기 위해 right stack의 바닥에 있는 element를 꺼내야 하므로)

struct QueueStack<T> : Queue {
  private var leftStack: [T] = []
  private var rightStack: [T] = []
  init() {}
}

Queue 프로토콜 구현

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

    mutating func enqueue(_ element: T) -> Bool {
        rightStack.append(element)
        return true
    }
    
    mutating func dequeue() -> T? {
        if leftStack.isEmpty {
            leftStack = rightStack.reversed()
            rightStack.removeAll()
        }
        
        return leftStack.popLast()
    }

• isEmpty를 판단하기 위해서는 left와 right가 둘 다 비어있어야 한다.
• peek을 판단하기 위해서는 left가 비어있지 않으면 가장 마지막 요소를, left가 비어있다면 right의 첫 요소를 반환하도록 한다.
• enqueue는 right 스택에 append 하는 걸로 끝이다. 배열에 추가하는 것이기 때문에 O(1)
• dequeue는 right 스택을 뒤집어 left 스택에 할당하고 left 스택의 last를 pop한다.

실행 결과 및 복잡도 정리

• 실행 결과

• 복잡도

dequeue가 O(1)이다. euqueue와 dequeue가 둘다 O(1)이라 가장 이상적인 구현인 것 같다.