LeetCode 225. Implement Stack using Queues

파이썬 알고리즘 인터뷰 문제 23번(리트코드 225번) Implement Stack using Queues
https://leetcode.com/problems/implement-stack-using-queues/

나의 풀이

class MyStack:

    def __init__(self):
        self.queue = collections.deque([])
        self.temp = collections.deque([])

    def push(self, x: int) -> None:
        self.queue.append(x)

    def pop(self) -> int:
        if not self.queue:
            return None
        while len(self.queue) > 1:
            self.temp.append(self.queue.popleft())
        result = self.queue.popleft()
        while self.temp:
            self.queue.append(self.temp.popleft())
        return result

    def top(self) -> int:
        if not self.queue:
            return None
        while len(self.queue) > 1:
            self.temp.append(self.queue.popleft())
        result = self.queue.popleft()
        while self.temp:
            self.queue.append(self.temp.popleft())
        self.queue.append(result)
        return result

    def empty(self) -> bool:
        return len(self.queue) == 0

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

• temp queue를 하나 더 만들어서 잠시 보관했다가 다시 옮겨 담는 방법.
• 다른 풀이에 비해 메모리 사용이 많다.
• push는 상대적으로 빠르다.
• pop과 top은 상대적으로 느리다.

다른 풀이

class MyStack:

    def __init__(self):
        self.queue = collections.deque([])

    def push(self, x: int) -> None:
        self.queue.append(x)
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

    def pop(self) -> int:
        return self.queue.popleft()

    def top(self) -> int:
        return self.queue[0]

    def empty(self) -> bool:
        return len(self.queue) == 0

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

• push할 때부터 순서를 뒤집어 놓는 방법
• 나의 풀이에 비해 메모리 사용이 적다.
• push는 상대적으로 느리고, pop, top은 빠르다.