[리트코드] Implement Queue using Stacks(python)

리트코드, Implment Queue using Stakcs_스택을 활용하여 큐 구현하기

 

TL;DR

• 큐(Queue)에 대해 이해하고 있는지

문제 분석

1. 두 개의 스택을 활용하여 큐를 구현하라.
2. 구현된 큐는 기본적인 큐의 기능인 push, peek, pop, empty를 지원해야 한다.
3. 큐를 구현할 때는 stack의 기본 기능인 push to top, peek/pop from pop, size, is emtpy만 활용해야 한다.

 

- stack의 기본 기능만 사용하여 큐를 구현해야 한다.

- 큐는 First In, First Out(FIFO)의 자료구조이다.

   - push : 큐에 자료형을 집어넣는다.

   - peek : 큐의 가장 먼저 들어간 원소를 반환한다.

   - pop : 큐의 가장 먼저 들어간 원소를 제거하고 반환한다.

   - empty : 큐가 비어 있을 경우 true, 아닐 경우 false를 반환한다.

 

풀이

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.inputStack = []
        self.outputStack = []

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.inputStack.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        val = self.inputStack.pop(0)
        self.outputStack.append(val)
            
        return self.outputStack[-1]

    def peek(self) -> int:
        """
        Get the front element.
        """
        return self.inputStack[0]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return not self.inputStack

 

- 파이썬에서 리스트가 스택의 역할을 수행할 수 있기 때문에 두 개의 리스트를 활용하여 큐를 구현하였다.

- push : append를 통해 간단히 구현 가능하다.

- peek : 가장 처음 들어온 원소를 반환해야 한다. 따라서 inputStack의 0번째 인덱스를 반환한다.

- pop : inputStack의 가장 처음 들어온 원소가 먼저 pop되어야 하므로 inputStack에서 제거한다. 그리고 얻어낸 원소를 outputStack에 쌓는다. 이를 통해 inputStack에 순서대로 입력된 원소를 앞에서부터 뽑아 outputStack에 차곡차곡 입력할 수 있게 된다.

- empty : inputStack 자체가 큐의 역할을 하게 되므로 inputStack이 비어있는지 아닌지를 반환한다.