LeetCode - 225. Implement Stack using Queues [Python]

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

Implement Stack using Queues - LeetCode

---

풀이 과정

큐로 스택을 구현하는 문제이다. 큐 2개로 스택을 구현하라고 하고 있고, 후속조치로 큐 1개로 스택을 구현해달라고 하고 있다.

 

1. 큐 2개로 구현하기

pop 할 때 스택에서 맨 처음 나오는 값이 큐에서는 제일 마지막에서 나오는 값일 것이므로, push 받을 때는 입력받은 값을 그냥 큐에 넣어주면 된다. pop 받을 때는 큐의 길이 - 1만큼 다른 큐에 원소들을 빼고 마지막 하나 남은 값을 pop 해주면 된다. top을 받았으면 마지막 하나 남은 값을 반환해주고 다시 큐에 넣어주면 된다. 스택이 비어있는지 판단하려면 큐 2개가 전부 비어있으면 스택도 비어있는 것이고, 아니면 스택에 원소가 있는 것이다.

 

2. 큐 1개로 구현하기

pop할 때 스택에서 맨 처음 나오는 값이 큐에서는 제일 마지막으로 나오는 값임을 생각하며 그냥 push 받을 때 push 받은 값이 큐의 맨 앞으로 가게 조작해주면서 스택의 기능을 하게 할 수 있다. 일단 입력받은 값을 큐에 넣고 큐의 사이즈 - 1번만큼을 앞에서 빼준 다음에 다시 뒤에 붙여주면 된다.

 

예시)

1, 2, 3이라는 큐에서 4를 입력받으면

1, 2, 3 -> 1, 2, 3, 4 -> 2, 3, 4, 1 -> 3, 4, 1, 2 -> 4, 1, 2 3

pop()하면 4가 나올 것이고 나중에 입력받으면 먼저 나오는 스택이 구현됨.

---

소스 코드

큐 1개로 구현한 코드이다.

class MyStack:
    def __init__(self):
        self.q = deque()

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

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

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

    def empty(self) -> bool:
        return True if len(self.q) == 0 else False