[리트코드] Implement Stack using Queues(python)

리트코드, Implement Stack using Queues_큐로 스택 구현하기

 

TL;DR

• 스택(Stack)의 개념을 이해하고 있는지

문제 분석

1. 두 개의 큐를 사용하여 스택을 구현하여라.
2. 구현된 스택은 push, top, pop, empty 함수를 지원해야 한다.
3. 큐를 사용할 때 push to back, peek/pop from front, size, is empty와 같은 함수만 사용 가능하다.

 

- 큐를 활용하여 스택의 기능인 push, pop, top, empty를 구현하는 문제이다.

- 스택은 Last In, First Out(LIFO) 구조를 갖는 자료구조 형이다.

  - push는 스택의 새로운 원소를 추가하는 동작을 수행한다.

  - top은 가장 마지막에 추가된 스택의 원소를 반환한다.

  - pop은 가장 마지막에 추가된 스택의 원소를 스택에서 제거하며 반환한다.

  - empty는 스택이 비어 있을 경우 true, 아닐 경우 false를 반환한다.

풀이

class MyStack:

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

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.stack.append(x)

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.stack.pop()

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.stack[-1]
        
    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return not self.stack

 

- 파이썬에는 따로 큐를 나타내는 자료형이 없으므로 리스트를 활용하여 큐를 구현하였다.

- 초기화될 경우 비어 있는 리스트를 할당한다.

- push : stack에 가장 마지막에 입력받은 원소를 집어넣는다.

- pop : stack의 가장 마지막 원소를 반환해야 하므로 리스트의 pop 연산을 그대로 사용하였다.

- top : stack의 가장 마지막 원소를 반환한다.

- empty : stack이 비어 있는 경우를 반환한다. `len(self.stack) == 0를 반환해도 상관없다.

 

다른 풀이

- 파이썬의 리스트가 어느 정도 큐와 스택의 역할을 하기 때문에 굉장히 쉽게 구현할 수 있다. 만약 리스트를 쓰지 않고, 덱(deque)와 같은 자료형을 사용해야 할 경우는 또 다르게 해결할 수 있을 것이다.