ch9-5(leetcode 232). 스택을 이용한 큐 구현

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 232번 ( https://leetcode.com/problems/implement-queue-using-stacks/ )

 

풀이방법 1. 

교재를 보지 않고 시도했던 방법이다. 이전 문제와 비슷하게, 스택에서 사용할 수 있는 메소드만 사용해서 큐를 구현하는 문제이다. 

 

이전의 큐는 원소를 빼낼 때는 앞에서, 원소를 넣을 때는 뒤에서 넣었다(FIFO). 반면 스택은 원소를 넣는 것과 빼는 작업이 모두 맨 뒤에서 일어난다(LIFO). 그래서 스택을 큐로 구현할 때처럼 큐의 앞에서 원소를 뺀 다음에 큐의 맨 뒤에 넣는 방식으로, 공간을 안 사용하고 풀 수는 없다. 스택에서 원소를 하나 빼서 하나를 다시 넣는다고 해서 스택의 값이 변하지 않기 때문이다. 

 

그래서 스택 하나를 더 사용해서 정렬 작업을 할 것이다. 

(여기서는 스택을 모두 리스트로 구현하였다.)

이제 push(), pop(), peek() 메소드를 구현해야 하는데, 어디서 정렬하는지는 상관없다. 이번 풀이에서는 push()할 때 정렬을 같이 진행했다. 

 

기존 스택을 stack, 순서를 바꾸는 데 필요한 새 스택을 reverse로 두었다.

1. 새 값이 들어오면 먼저 기존 stacl에 있던 원소들을 전부 reverse로 옮긴다.

2. 빈 스택에 새 값을 먼저 넣은 뒤, reverse에 있던 값들을 다시 stack으로 옮기면 된다. 

하노이 탑과 비슷한 원리이다. 

 

push()에서 정렬 작업을 모두 마쳤기 때문에 pop(), peek() 메소드는 간단하게 구현할 수 있다. 

peek()은 stack의 맨 마지막 원소를 리턴하면 되므로, 우선 원소가 있는지를 확인한 뒤 -1번째 인덱스를 리턴하면 된다. 

(비어 있는 리스트에서 인덱스를 참조할 경우 오류가 나므로 주의하자)

 

pop()의 경우, 리스트에서 기본으로 제공되는 메소드이므로 그냥 사용하면 된다. 

peek()과 마찬가지로 원소가 없는 리스트에서 pop()을 할 경우 오류가 발생하므로 길이를 확인한 뒤 실행하자. 

 

전체 코드는 다음과 같다. 

class MyQueue(object):

    def __init__(self):
        self.stack = []
        self.reverse = []

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        for _ in range(len(self.stack)):
            self.reverse.append(self.stack.pop())
        
        self.stack.append(x)
        for _ in range(len(self.reverse)):
            self.stack.append(self.reverse.pop())

        

    def pop(self):
        """
        :rtype: int
        """
        if len(self.stack) >= 1:
            return self.stack.pop()
        

    def peek(self):
        """
        :rtype: int
        """
        if len(self.stack) >= 1:
            return self.stack[-1]
        

    def empty(self):
        """
        :rtype: bool
        """
        return len(self.stack) == 0

 

풀이방법 2. 

교재에서 언급된 풀이방법이다. 두 개의 스택(리스트로 구현)을 사용한다는 점은 같은데, 시공간 복잡도가 더 효율적이다. 

 

이전 방법에서는 push()를 시행할 때마다 정렬을 진행하였는데, 이 경우 매번 stack에 있던 원소를 reverse로 옮긴 뒤, 새 원소를 넣고, 다시 reverse에서 stack으로 옮기면서 시간이 더 소요될 수 있다. 

 

여기서도 두 개의 스택을 사용하지만 각 스택을 그때그때 들어오는 원소를 담아두는 input, peek()나 pop()이 호출될 때 스택을 정렬하기 위한 output으로 구분하였다. 

즉 push()가 호출될 때마다 매번 정렬이 일어나지 않고, 정렬이 일어나더라도 모든 원소를 옮기지 않는 방식이다. 

 

peek()나 pop()이 호출되면 우선 output 스택에 원소가 있는지 확인한다. 만약 원소가 있다면, 이 원소들은 input 스택에 들어있는 원소보다 이전에 들어온 원소들이 이미 정렬된 상태이므로, 여기서 가장 위에 있는 것을 제거한다. 

 

만약 output 스택에 원소가 없다면, 그 때는 input 스택에 있던 원소를 output 스택으로 옮긴다. 이전 풀이에서의 하노이 탑과 같은 원리이기 때문에 input에서 가장 먼저 들어왔던 원소가 output 스택의 맨 위에 오게 된다. 

이후 또 peek()나 pop()이 호출된다면, 그 때는 input 스택에 원소가 있던 없던 상관없이 output 스택의 맨 위에 가장 먼저 들어온 원소가 있으므로, output 스택이 빌 때까지 차례대로 빼서 사용하면 된다. 

 

같은 원리이지만 불필요한 정렬을 줄인 방법이라고 볼 수 있겠다.