[LeetCode] #225. Implement Stack using Queues

리트코드 #225. 큐를 이용한 스택 구현

문제

문제 링크

큐를 사용해 스택의 기본 연산을 구현한다.

push() : 스택에 요소 삽입
pop() : 스택의 가장 마지막 요소 제거 및 반환
top() : 스택의 가장 마지막 요소 반환
empty() : 스택에 비어있으면 True

잘못된 방법

class MyStack2:
    def __init__(self):
        self.q = collections.deque()

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

    # 맨 위 요소를 제거하면서 반환
    def pop(self) -> int:
        return self.q.pop()

    # 맨 위 요소를 제거하지 않고 반환
    def top(self) -> int:
        return self.q[-1]

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

collections 모듈의 양방향 큐인 deque(데크)를 사용했다.
일반적인 큐는 오른쪽에서 데이터를 넣고 왼쪽에서 제거한다면, 데크는 양쪽에서 데이터를 넣고 제거할 수 있다.

push() : 큐의 오른쪽에 요소를 삽입한다.
pop() : 큐의 가장 오른쪽 요소 삭제
top() : 스택의 가장 마지막 요소 반환
empty() : 큐의 길이가 0이면 비어있는 것
=> 큐의 오른쪽에서 요소를 삽입하고 오른쪽부터 삭제한다면, 이건 큐가 아니라 스택이다!

python documentation
내가 이 코드를 짜면서 깜빡한데 deque.pop()을 하면 위의 그림처럼 왼쪽부터 요소를 제거하지 않고, 오른쪽부터 제거한다!!
결국 내가 짠 push(), pop() 함수는 큐로 스택을 구현한게 아니라, 스택으로 스택을 구현한 셈이다...
아래 수정한 push(), pop() 함수 코드가 있다.

올바른 방법

github link

import collections
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())
        print("정렬 후: ", self.q)

    # 맨 위 요소를 제거하면서 반환
    def pop(self) -> int:
        return self.q.popleft()
        
    def empty(self) -> bool:
        return len(self.q) == 0

push() : 스택은 선입선출이다. 새로운 요소를 삽입하면 삽입된 요소가 제거할 때 가장 앞에 있어야 한다.
다음과 같이 [2, 1]에 3을 삽입하면 3이 맨 앞에 오도록 정렬해야 한다.
[2, 1] -> push(3) -> [2, 1, 3] -> [3, 2, 1]로 정렬
pop() : 단순히 왼쪽에서 제거하면 되므로 queue.popleft()
=> 여기서 사용한 큐는 오른쪽에서 요소를 삽입하고, 왼쪽에서 제거한다.