Implement Stack Using Queues

나의 논리

문제를 조금 잘못 이해한것 같기도 하고 아니면 애초에 논리 자체가 비효율적인것 같기도 하다. 일단.. 통과는 했다..

나는 2개의 큐를 이용해서 서로 요소들을 옮겨 담으며 채우는 방식으로 접근을 했다.

from collections import deque
class MyStack:

    def __init__(self):
        
        self.q = deque()
        self.tempq = deque()

    def push(self,x):
        self.q.append(x)

    def pop(self):

        for _ in range(len(self.q)-1):
            self.tempq.append(self.q.popleft())

        item = self.q.popleft()

        for _ in range(len(self.tempq)):
            self.q.append(self.tempq.popleft())

        return item

    def top(self):

        for _ in range(len(self.q)-1):
            self.tempq.append(self.q.popleft())

        item = self.q.popleft()

        for _ in range(len(self.tempq)):
            self.q.append(self.tempq.popleft())
        self.q.append(item)

        return item

    def empty(self):

        return len(self.q) == 0

pop을 할때는 제일 마지막 요소를 제외한 나머지를 tempq에 담고 마지막 요소를 popleft를 통해 얻은 뒤 리턴하고나서 다시 tempq의 원소들을 q에 담는다.

그리고 파이썬의 deque이 O(1)시간에 임의접근 할 수 있는지 몰랐다... q[n]으로 원소에 접근 할 수 있다.

정답 논리

훨씬 코드가 짧고 간결하다.

class MyStack:

    def __init__(self):
        self.q = collections.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 len(self.q) == 0

우선 deque자체를 스택으로 개조해서 이용하고 있다.
push 메서드를 보면 deque의 pop하는 부분이 스택의 top 부분이다. 그리고 push를 할때마다 요소들의 위치를 바꿔준다. 그렇게되면 나머지 연산들은 간단하게 해결된다.