[LeetCode] 232. Implement Queue using Stacks

스택을 사용한 큐의 구현

스택은 기본적으로 LIFO, 가장 나중에 들어온 데이터가 가장 먼저 출력되는 자료구조이다. 반대로 큐는 가장 먼저 들어온 데이터가 가장 먼저 출력된다. 스택을 사용해서 큐를 구현할 때 가장 주의할 점은 스택 입장에서는 가장 먼저 들어와 가장 아래에 있는 데이터가 출력될 땐 제일 먼저 출력되어야 한다는 점이다.

이를 구현하기 위해서는 기본적으로 2개의 스택이 필요하다. 스택1에 데이터를 입력하면 데이터들이 들어온 순서대로 쌓이게 되는데 출력될 때는 거꾸로 모든 데이터를 빼서 가장 아래의 데이터를 꺼내야 한다. 이때 꺼낸 데이터들을 다시 저장해둘 공간이 필요하기 때문에 스택이 추가로 하나 더 필요해진다.

꺼내진 데이터들을 모아둘 공간도 스택인 이유는 스택1에서 꺼낸 데이터들을 스택2에 쌓게 되면 가장 나중에 들어온 데이터가 아래에 위치하게 되는데 만약 이 자료구조가 큐가 된다면 가장 나중에 들어온 데이터가 제일 먼저 출력되는 아이러니가 발생하기 때문이다. 즉 입출력이 모두 한곳에 이루어져야 하므로 역시 스택이 필요하다.

내 코드

pop

가장 먼저 들어온 데이터(스택1의 가장 아래에 위치한 데이터)를 꺼내기 위해 스택2로 옮기는 과정을 진행한다. 모든 데이터를 스택2로 옮겼다면 꺼내야 할 데이터는 스택2의 가장 위(top)에 위치한 데이터이므로 이 데이터를 저장해둔다.

다시 스택2의 데이터들을 스택1로 옮긴다.

class MyQueue:

    def __init__(self):
        self.stack1 = list()
        self.stack2 = list()

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

    def pop(self) -> int:
        for _ in range(len(self.stack1)):
            self.stack2.append(self.stack1.pop())
        
        last = self.stack2.pop()

        for _ in range(len(self.stack2)):
            self.stack1.append(self.stack2.pop())
        return last

    def peek(self) -> int:
        return self.stack1[0]

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


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

교재 풀이

두 개의 스택을 사용하지만 pop을 할 때 모든 데이터를 두 번 옮기는 과정을 반복하지 않았다. 일단 pop이 호출되면 가장 첫 번째 데이터를 찾는 peek함수롤 호출했다.

s2는 기본적으로 s1의 데이터들을 거꾸로 갖고 있게 되기 때문에 가장 최근의 데이터가 상단에 위치하게 된다. peek() 함수가 호출되었을 때 s2 함수가 비어있지 않다면 이 값의 최상단(s2[-1]) 값을 출력하면 된다.

s2가 비어있다면 s1의 데이터들을 하나씩 pop()해서 s2로 옮기게 된다. 이후에 다시 s2의 데이터를 s1으로 옮기지는 않는다. s1에는 계속 데이터를 입력받게 되겠지만 어차피 s2에 있는 모든 데이터가 출력되지 않는이상 둘이 합쳐지는 일은 없기 때문에 원래 하던대로 데이터들을 입력받다가 출력 요청이 왔고 s2가 비어 있을 때 데이터를 꺼낼 수 있기만 하면 된다.

class MyQueue:

    def __init__(self):
        self.s1 = list()
        self.s2 = list()

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

    def pop(self) -> int:
        self.peek()
        return self.s2.pop()

    def peek(self) -> int:
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2[-1]

    def empty(self) -> bool:
        return len(self.s1) == 0 and len(self.s2) == 0


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