[리트코드] 225. 큐를 이용한 스택 구현 (Python)

Implement Stack using Queues - LeetCode

문제

큐를 이용해 다음 연산을 지원하는 스택을 구현하라.

• push(x): 요소 x를 스택에 삽입한다.
  
• pop(): 스택의 첫 번째 요소를 삭제한다.
• top(): 스택의 첫 번째 요소를 가져온다.
• empty(): 스택이 비어 있는지 여부를 리턴한다.

과정

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

 

입력

["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

출력

[null, null, null, 2, 2, false]

 

풀이

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())        

    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

 

한 줄씩 코드 해석해보기

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

• 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())

• push 명령을 할 경우 q에 append를 통해 값 추가
• 값 추가시 맨 뒤에 추가가 되기 때문에 popleft를 활용해 앞에 값들을 뒤로 하나씩 보내줌

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

• 단순히 왼쪽을 제거하면 되므로 popleft() 

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

• 인덱스를 이용해 맨 앞에 있는 값 return

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

• len()을 이용해 q의 길이가 0인지 확인