[리트코드(LeetCode)] 큐로 스택 구현하기, 스택으로 큐 구현하기 - Python

leetcode.com/problems/implement-queue-using-stacks

Implement Queue using Stacks - LeetCode

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

Implement Stack using Queues - LeetCode

 

- <파이썬 알고리즘 인터뷰>를 학습하면서 수록된 코드를 참고하였습니다. - 

 

큐로 스택을 구현하거나, 스택으로 큐를 구현하는 문제는 개발자 면접 때 손코딩 문제로 자주 출제되는 유형이다. (실제로 면접 때 스택으로 큐를 구현하는 손코딩 문제를 받은 적이 있다.)

 

 

큐로 스택을 구현

스택에 값을 push()하는 경우, 해당 값을 우선 큐에 push()한다. 그 다음 마지막 원소를 제외한 나머지를 꺼내서 다시 큐에 차례대로 push하게 되면 가장 나중에 들어온 값이 큐의 첫 번째 자리에 위치하게 된다. top()이나 pop() 메소드를 호출할 때 큐의 첫 번째 값을 참조하면 된다.

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
        

 

 

 

스택으로 큐를 구현

스택으로 큐를 구현하기 위해서는 2개의 스택이 필요하다.

큐에 값을 push()하는 경우, 하나의 스택에 차례로 값을 push()한다. 이후 큐에서 pop()메소드를 호출하는 경우, 쌓여 있는 스택의 원소들을 pop하여 나머지 다른 스택에 push한다. 이렇게 되면 첫 스택에 담겨 있는 요소들이 두 번째 스택에 반대로 쌓이게 된다. 이렇게 거꾸로 쌓인 요소들을 차례대로 pop()하면 큐의 기능처럼 선입선출 구조로 값을 리턴하게 된다.

class MyQueue:

    def __init__(self):
        self.input = []
        self.output = []

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

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

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

    def empty(self) -> bool:
        return not self.input and not self.output
        

 

 

머리로는 금방 그려지더라도 막상 면접 자리에 가면 떨려서 실수를 할 여지가 있다. 직접 구현하는 훈련을 통해 체화시키는 것이 중요하다.

 

 

www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9791189909178

파이썬 알고리즘 인터뷰 - 교보문고