23. Implement Stack using Queues

🎯 leetcode - 225. Implement Stack using Queues

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 23번 문제
- 큐를 이용하여 스택을 구현하라.

📌 날짜

2020.01.30

📌 시도 횟수

2 try

💡 Code

import queue

class MyStack:
    def __init__(self):
        self.q = queue.Queue()

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

    def pop(self) -> int:
        for _ in range(self.q.qsize() - 1):
            self.q.put(self.q.get())
        return self.q.get()

    def top(self) -> int:
        for _ in range(self.q.qsize() - 1):
            self.q.put(self.q.get())
        peek = self.q.get()
        self.q.put(peek)
        return peek

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

💡 문제 해결 방법

- 파이썬의 queue 라이브러리를 이용했다.
- queue는 기본적으로 put, get 함수를 지원한다.
- queue의 put, get은 FIFO 구조를 따른다. 즉, 먼저 넣은 순서대로 먼저 나온다.
- 반면, stack은 나중에 넣은게 가장 먼저 나온다.
- 따라서 넣는 방향이 stack, queue 둘다 동일하다고 했을 때...
구현하고자 하는 것은 "나오는 방향을 반대로" 하는 것이다.
- 따라서 pop, top 함수가 가장 "처음"의 요소에 대해 실행되도록 기존의 queue를 변형했다.
1. pop(x):
- 스택의 첫번째 요소는 queue의 마지막 요소이다.
- 즉, queue.get을 이용하여 queue의 맨 마지막 요소를 pop해야 된다.
- 따라서 마지막 요소에 도달할 때까지 queue의 맨 앞의 요소를 빼서 다시 맨 뒤로 집어넣는다.
- 마지막 요소에 도달하면 맨 뒤로 집어넣지 않고 마지막 값을 return한다.

2. top():
- top도 pop과 비슷한 방법을 이용했다.
- 마지막 요소에 도달할때까지 맨 앞의 요소를 빼서 다시 맨 뒤로 집어넣는다.
- 단, pop과는 다르게 맨 마지막 요소에 도달하면 따로 값을 보관해두고,
- 마지막 요소 또한 맨 뒤로 집어넣어 사실상 top()을 실행해도 스택에는 변화가 없도록 한다.
- 보관해둔 queue의 맨 마지막 값을 리턴한다.

내 방법 - 🌵이해가 안된다면🌵

• 참고로 queue 라이브러리가 없어서 deque를 queue처럼 사용했다.
• 그렇지만 원리는 똑같기 때문에 크게 상관은 없다.

💡 새롭게 알게 된 점

- python에서 queue를 사용하려면...
>> import queue를 하고 q = queue.Queue() 와 같이 사용하면 된다.

- 파이썬에서 queue의 길이를 구하려면, len을 사용할 수 없다.
>> qsize()라는 함수가 존재한다. 이것으로 큐의 길이를 구한다.

- 파이썬에서 queue의 값을 추가하려면 put(x), 빼려면 pop() 함수를 사용한다.

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 문제의 조건을 잘 이해해야 된다. 
- 처음 시도에 맞추긴 했지만 사실 그 방법은 오답이다!
>> You may simulate a queue using a list or deque (double-ended queue).
>> As long as you use only a queue's standard operations.
- deque를 사용할 수는 있지만 deque만의 유용한 함수를 못 사용하고,
- queue의 함수 기능들만 사용해야 된다는 문제의 조건을 잘 봐야 했다!

---

😉 다른 풀이

📌 하나. deque의 append, popleft 만을 이용한 풀이

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

    # 삽입한 요소를 맨 앞에 두는 상태로 전체를 재정렬함
    # 즉 [4, 3, 2, 1]에 5를 삽입하면...
    # [4, 3, 2, 1, 5] -> [3, 2, 1, 5, 4] -> [2, 1, 5, 4, 3] -> [1, 5, 4, 3, 2] -> [5, 4, 3, 2, 1]
    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 self.q.qsize() == 0

💡 새롭게 알게 된 점

- 내 방법은 1~5를 차례대로 push한다고 하면 사실상 [1,2,3,4,5] 이렇게 쌓인다.
- 그래서 기존의 queue.get()은 가장 첫번째인 1이므로, 5를 pop 하기 위해서는
[2, 3, 4, 5, 1] -> [3, 4, 5, 1, 2] -> [4, 5, 1, 2, 3] -> [5, 1, 2, 3, 4] => 5
이렇게 과정을 진행했다.

- 반면, 위의 다른 풀이의 경우에는 나와는 반대로 push를 반대로 했다.
- 따라서 애초에 [5, 4, 3, 2, 1]의 순서로 저장되므로
queue의 get연산을 했을 때 바로 스택 같은 결과값이 출력될 수 있는 것이다~

- 헷갈려서 한번 정리해봤다

방법 1 - 🌵이해가 안된다면🌵

---