[leetcode 2024/02/06] 225. Implement Stack using Queues

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

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법

stack 구현

Queue는 FIFO (first in first out) 을 특징으로 가지고 있기 때문에, stack의 pop이나 peek을 구현하기 위해서는, 하나하나 값을 빼서, 다른 queue에 넣어주는 것이었다.

 

만약, stack이 비어지게 되었다면, 저장해두었던 temp를 출력하는 방식으로 pop과 peek를 구현하였다.

pop의 경우, 출력을 한 후, 새로운 queue에 값을 넣어주지 않았으며, peek의 경우 새로운 queue에 값을 넣어주는 방식으로 구상하였다.

 

따라서 queue는 2개가 생기게 된다. 

1. 값을 지니고 있던 queue

2. 값을 옮겨 담을 빈 queue

 

하지만 옮겨 담게 되면,

1. 값을 지니고 있던 queue -> 빈 queue

2. 값을 옮겨 담을 빈 queue -> 값들이 채워져 있게 된다.

 

따라서 옮긴 이후, 두 queue 값을 대치시켜 다시 이용할 수 있도록 해야한다. 즉,

self.p, self.q = self.q, self.p

 

을 해준다.

 

2. 코드

from queue import Queue

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

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

    def pop(self) -> int:
        while not self.q.empty():
            inst = self.q.get()
            if not self.q.empty():
                self.p.put(inst)
        self.p, self.q = self.q, self.p
        return inst

    def top(self) -> int:
        while not self.q.empty():
            inst = self.q.get()
            self.p.put(inst)
        self.p, self.q = self.q, self.p
        return inst


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


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()