[LeetCode]225. Implement Stack using Queues, 232. Implement Queue using Stacks

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

큐로 스택을 스택으로 큐를 구현하세요.

✍️ 풀이

---

• 큐로 스택 구현하기
  현재 값 앞에 있는 것들을 큐에서 빼서 현재 값 뒤로 삽입한다.

• 스택으로 큐 구현하기
  스택 두 개를 이용해 push는 저장만을 수행하는 input 스택에 넣고
  pop행동을 통해 output스택에 값이 없다면 input의 반대로 값을 받아오도록 한다.

🛠 코드

---

• 큐로 스택 구현하기

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.q = collections.deque()
        

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
        

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.q.popleft()

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.q[0]

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return len(self.q) == 0
        

• 스택으로 큐 구현하기

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack = []
        

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.tmp = []
        while self.stack:
            self.tmp.append(self.stack.pop())
        self.stack.append(x)
        while self.tmp:
            self.stack.append(self.tmp.pop())
        return self.stack

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        return self.stack.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        return self.stack[-1]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.stack) == 0

---

📝 정리

---

🎈 참고

---

Book 링크