[LeetCode] 225. Implement Stack using Queues(Python/Queue)

자료구조 큐(Queue)

• 선입선출(FIFO First-In-First-Out)로 데이터를 처리하는 선형 자료구조
• 한쪽에서는 입력이, 한쪽에서는 출력이 이루어지는 양쪽을 모두 사용하는 데이터 자료구조
• 티켓을 사기 위해 기다리고 있는 줄을 생각하면 쉽다. 먼저 온 사람이 먼저 티켓을 사게 되는 구조와 같다.
• front : 큐의 가장 앞에 있는 데이터는 가장 먼저 삽입된 데이터
• rear : 큐의 가장 뒤에 있는 데이터로 가장 나중에 삽입된 데이터

큐를 이용한 스택 구현

일반적으로 큐는 왼쪽에서 데이터가 출력되고 오른쪽에서 데이터가 삽입된다. 반면에 스택은 오른쪽에서만 데이터의 입/출력이 이루어진다.

큐로 스택을 구현하게 된다면 가장 먼저 주의할 점은 가장 먼저 들어온 데이터가 가장 나중에 출력될 수 있도록 데이터들의 위치를 변경해주어야 한다는 점이다. 위치를 변경해주지 않으면 가장 먼저 들어온 데이터가 차례대로 쌓이게 되고, 큐는 가장 왼쪽에 위치해있을 가장 먼저 들어온 데이터를 먼저 출력하도록 되어 있는 자료구조이므로 결국 스택과 달리 FIFO 형태로 구현될 것이다.

😇 나의 코드

class MyStack:

    def __init__(self):
        self.stack = collections.deque()

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

    def pop(self) -> int:
        return self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def empty(self) -> bool:
        return len(self.stack) == 0
        
# from collections import deque

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

문제점
1. 데이터가 들어오고 데이터들의 위치를 바꿔주지 않음
2. 데이터의 입/출력이 한쪽에서만 이루어짐 -> 큐가 아니라 그냥 스택

변경된 코드

class MyStack:

    def __init__(self):
        self.stack = collections.deque()

    def push(self, x: int) -> None:
        self.stack.append(x) # when data is added, then we change the position 

        for _ in range(len(self.stack)-1):
            self.stack.append(self.stack.popleft())

    def pop(self) -> int:
        return self.stack.popleft()

    def top(self) -> int:
        return self.stack[0]

    def empty(self) -> bool:
        return len(self.stack) == 0


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()