[leetcode 225.python] 큐를 이용한 스택 구현 (Implement Stack using Queues) 풀이

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

Implement Stack using Queues - LeetCode

---

문제

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

오직 2개의 queue를 사용해서 stack을 구현해라. 구현되는 스택은 일반적인 것으로, push, top, pop, empty의 기본 기능을 지원한다.

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.  / 요소 x를 스택에 삽입해라.
• int pop() Removes the element on the top of the stack and returns it. / 스택의 첫 번째 (맨 위의 요소)를 삭제(pop)해라.
• int top() Returns the element on the top of the stack. / 스택의 첫 번째 요소를 가져와라.
• boolean empty() Returns true if the stack is empty, false otherwise. / 스택이 비어있는지의 여부를 반환해라.

Notes:

• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

---

문제 이해

먼저, queue와 stack의 컨셉을 알아보자.

queue의 컨셉

식당에서 줄서기를 생각하면 쉽게 이해할 수 있다. 빨리 온 사람이 빨리 먹는거야 !!!

stack의 컨셉

빨래통을 생각하면 쉽게 이해할 수 있다. 나중에 넣은 빨래가 제일 먼저 꺼내진다.

 

큐를 이용해서 스택 구조를 만들어야 하는 문제다.

 

마지막에 들어온 값을 큐의 가장 앞단 (top)에 위치시킬 수 있다면, 큐 하나로도 스택 구조를 유지할 수 있다.

 

즉, 스택에 값을 push할 때, 해당 값을 우선 큐에 push한다. 그 다음 마지막 원소를 제외한 나머지를 꺼내서 다시 큐에 차례대로 push하게 되면 (재정렬) 가장 나중에 들어온 값이 큐의 첫 번째 자리에 위치하게 된다.

요렇게

---

문제 풀이

1. push/pop 연산이 빈번한 알고리즘에서 리스트보다 월등한 속도를 자랑하는 양방향 큐 deque(데크)를 사용할 것이다.

 def __init__(self):
        self.q = deque()

 

2.  append로 요소 x를 삽입해준다. 요소 삽입 후 맨 앞에 두는 상태로 재정렬해준다. 마지막 원소를 제외한 나머지를 꺼내야하기 때문에 - 1을 해준다.

 def push(self, x: int) -> None:
        self.q.append(x)
        # 맨 앞에 두는 상태로 재정렬
        for i in range(len(self.q) -1):
        	self.q.append(self.q.popleft())

 

3. 스택의 첫 번째 요소를 삭제(popleft)해준다. 

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

 

4. 스택의 첫 번째 요소(q[0])를 리턴해준다.

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

 

5. 스택이 비어있는지의 여부를 리턴해준다. len 함수로 글자수가 0이면 (비어있으면) true, 0이 아니면 (비어있지 않으면) false를 리턴하도록 만들어준다.

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

 

---

문제 답

class MyStack:

    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for i 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

---

마치며

데크로 앞, 뒤 양쪽 방향에서 값을 추가하거나 제거할 수 있다니 흥미로웠다. 속도도 훨씬 빠르고! 배우면 배울수록 몰랐던 게 튀어나오니 갈 길이 멀게 느껴지면서도 재밌다 :-)