leetcode 225. Implement Stack using Queues 문제 풀이

문제

https://leetcode.com/problems/implement-stack-using-queues/description/

💬 문제는 두개의 큐로 스택을 구현하는 것이지만, 하나의 큐만으로 스택 구현이 가능한지에 대한 Follow-up을 시도하고자 작성한 코드입니다.

제출 코드 v1

class MyQueue<T> {
    private var input: [T] = []
    private var output: [T] = []

    init() {}
    
    func push(_ x: T) {
        input.append(x)
    }
    
    func pop() -> T {
        if output.isEmpty {
            output = input.reversed()
            input = []
        }
        return output.removeLast()
    }
    
    func peek() -> T {
        guard output.isEmpty else { return output.last! }
        return input.first!
    }
    
    func empty() -> Bool {
        input.isEmpty && output.isEmpty
    }
    
    func size() -> Int {
        input.count + output.count
    }
}

class MyStack {
    private var queue = MyQueue<Int>()
    
    init() {}
    
    func push(_ x: Int) {
        queue.push(x)
    }
    
    func pop() -> Int {
        let queueSize = queue.size()
        for _ in 0..<(queueSize-1) {
            queue.push(queue.pop())
        }
        return queue.pop()
    }
    
    func top() -> Int {
        let queueSize = queue.size()
        for _ in 0..<(queueSize-1) {
            queue.push(queue.pop())
        }
        let output = queue.peek()
        queue.push(queue.pop())
        return output
    }
    
    func empty() -> Bool {
        queue.empty()
    }
}

제출 코드 v2

class MyQueue<T> {
    private var input: [T]
    private var output: [T]

    init(_ input: [T] = []) {
        self.input = input
        self.output = []
    }
    
    func push(_ x: T) {
        input.append(x)
    }
    
    func pop() -> T {
        if output.isEmpty {
            output = input.reversed()
            input = []
        }
        return output.removeLast()
    }
    
    func peek() -> T {
        guard output.isEmpty else { return output.last! }
        return input.first!
    }
    
    func empty() -> Bool {
        input.isEmpty && output.isEmpty
    }
    
    func size() -> Int {
        input.count + output.count
    }
}

class MyStack {
    private var queue = MyQueue<Int>()
    
    init() {}
    
    func push(_ x: Int) {
        queue.push(x)
        let queueSize = queue.size()
        for _ in 0..<(queueSize-1) {
            queue.push(queue.pop())
        }
    }
    
    func pop() -> Int {
        queue.pop()
    }
    
    func top() -> Int {
        queue.peek()
    }
    
    func empty() -> Bool {
        queue.empty()
    }
}

어떤 점을 고민했을까?

1. 큐 순회 시점
   • v1에서는 stack의 pop()/top() 호출시 큐를 순회 및 재구성하고, v2에서는 stack의 push() 호출시 큐를 순회 및 재구성합니다.
   • 두 버전 모두 시간복잡도는 동일합니다. 큐 순회 및 재구성하는 부분은 큐의 크기만큼 반복문이 실행되기 때문에 O(n) 비용이 발생하고, 단순히 요소를 제거하거나 추가하는 부분은 O(1) 비용이 발생합니다.
   • push() 호출이 잦다면 pop()과 top()에서 큐 순회 및 재구성을 하는 것이, pop()이나 top() 호출이 잦다면 push()에서 큐 순회 및 재구성을 하는 것이 비용 최적화 측면에서 이롭다고 생각합니다.
2. 큐 객체 정의 여부
   • 실행결과와 문제풀이속도 측면에서 유리한 경우라면 “큐를 통해 스택을 구현하세요”라고 해도 큐 객체 정의없이 배열을 통해 스택을 구현해도 될 것 같다. 그러나 코드 리뷰를 통해 나의 코드 작성 방식과 고민, 견해 등 여러가지를 보여줄 수 있다면 객체 역할 분리와 유지보수성을 고려하는 점을 보여주기 위해 큐 객체 정의를 할 것 같다.
   • 이 부분은 의견이 분분할 수 있지만 개인적인 의견으로써는 그렇다!

⏱️ 시간복잡도

1. 큐 순회 : O(n)
2. 큐 요소 추가 or 제거 : O(1)
3. 전체 시간복잡도 : O(n)

📦 공간복잡도

1. MyQueue에서 Input, output 배열에서 저장되는 요소에 따라 O(n)
   1. MyQueue 객체 정의없이 스택 내에서 배열로만 기능을 처리해도 똑같이 배열을 통해 요소를 저장하기 때문에 동일함
2. 큐 순회 전 queueSize를 선언하면서 O(1)만큼의 추가 공간 소비
3. 전체 공간복잡도 : O(n)

💨 실행속도

• (리트코드 제출 기준) 런타임은 0ms로 모두 동일