45. Implement Stack using Queues

문제

큐를 이용하여 스택을 구현하시오.

(push, top, pop, empty 메서드 구현)

 

해결 방식

큐 하나로 구현.

- push : 큐에 append.

- pop :

1) 큐의 길이 구하기

2) 큐의 길이 - 1만큼 iterate하면서 맨 앞요소를 pop해서 다시 append하기 => 삭제할 요소만 제일 앞에 남게 됨

3) 큐를 pop해서 제일 앞의 요소 삭제하고 반환.

ex) queue는 [1, 2, 3]. 여기서 pop하면 3을 반환해야 함.

      큐의 길이는 3이므로 2번 iterate.

      첫번째 iteration에서 queue는 [2, 3, 1]이 됨.

      두번째 iteration에서 queue는 [3, 1, 2]가 됨.

      queue를 pop하면 3이 나옴. 

 

- top :

1) 큐의 길이 구하기

2) 큐의 길이만큼 iterate하면서 맨 앞요소를 pop해서 item에 할당.

3) item을 큐에 append하기 

=> queue는 원래 상태와 똑같이 됨

=> item은 마지막 요소를 담게 됨

ex) queue는 [1, 2, 3]. 여기서 top하면 3을 반환해야 함.

      큐의 길이는 3이므로 3번 iterate.

      첫번째 iteration에서 queue는 [2, 3, 1], item은 1

      두번째 iteration에서 queue는 [3, 1, 2], item은 2

      세번째 iteration에서 queue는 [1, 2, 3], item은 3

      3이 된 item을 반환

class MyStack:

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

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

    def pop(self) -> int:
        if not self.queue:
            return []
        
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

        return self.queue.popleft()

    def top(self) -> int:
        item = 0
        for _ in range(len(self.queue)):
            item = self.queue.popleft()
            self.queue.append(item)

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