[리트코드(LeetCode)] 225번, 232번 Stack, Queue

문제

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

Implement Stack using Queues - LeetCode

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

Implement Queue using Stacks - LeetCode

큐를 이용해 스택을 구현하는 문제와 스택을 이용해 큐를 구현하는 문제로 같이 풀어보도록 하겠습니다.

 

💡 문제 풀기 전 스택과 큐에 대한 간단한 설명

스택 : Last-In-First-Out(후입선출)로 가장 마지막에 쌓은 데이터를 제일 먼저 꺼내는 자료구조.
큐 : First-In-First-Out(선입선출)로 가장 먼저 삽입한 데이터를 제일 먼저 꺼내는 자료구조. 

풀이

from collections import deque

class MyStack:

    def __init__(self):
        self.q = 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

stack = MyStack()
# 확인해보는 코드
stack.push(1)
stack.push(2)
stack.push(3)
print("pop: ", stack.pop()) # pop:  3
print("top: ", stack.top()) # top:  2
while not stack.empty():
    print("Popped element: ", stack.pop()) # Popped element:  2 / Popped element:  1
print("Is stack empty?", stack.empty()) # Is stack empty? True

 

- 스택은 후입선출의 구조이기 때문에 push를 구현할 때, x를 추가 후 x가 맨 앞으로 갈 수 있게 재정렬을 한다.

- 재정렬을 하면 큐에서 앞에 있는 요소를 꺼낼 때(popleft()) 스택처럼 가장 마지막에 추가한 요소가 나올 수 있다.

 

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

my_queue = MyQueue()
# 확인해보는 코드
my_queue.push(1)
my_queue.push(2)
my_queue.push(3)
print("peek: ", my_queue.peek()) # peek:  1
print("pop: ", my_queue.pop()) # pop:  1
while not my_queue.empty():
    print("Popped element: ", my_queue.pop()) # Popped element:  2 / Popped element:  3
print("Is queue empty?", my_queue.empty())  # Is queue empty? True

 

- 큐는 선입선출의 구조이므로 하나의 스택를 이용해서 풀 수 없어 두 개의 스택이 필요하다.

- peek를 사용해 input에 들어온 요소들을 output으로 추가하면서 재정렬을 한다.

- 재정렬을 하면서 input 스택에 먼저 쌓인 데이터가 output 스택에 마지막에 쌓여 가장 먼저 추가한 요소가 나올 수 있다.

 

참조 : 박상길, 파이썬 알고리즘 인터뷰  https://github.com/onlybooks/algorithm-interview