[leetcode 2024/02/06] 232. Implementing Queue using Stacks

https://leetcode.com/problems/implement-queue-using-stacks/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법

stack에서 queue를 구현하기 위해서는 다음과 같은 과정이 필요하다. 

stack에서 맨 밑에 있는 4가 queue의 입장에서는 제일 먼저 출력되어야 하는 녀석이다. (FIFO)

따라서 stack에서 하나씩 pop을 하여 다른 stack에 옮겨담은 후, 다시 역순으로 된 stack을 pop을 하려 원래 저장되었던 순서로 다시 저장해 주어야 한다. 아래 그림이 해당 과정을 설명하는 그림이다.

 

Python의 경우 stack이 내부적으로 구현이 되어 있지 않기 때문에, 문제에서 제시되었던 것처럼 list를 이용해주었다. 

list를 stack 처럼 사용하려고 하니 조금 답답함이 느껴졌던 문제이다. ㅎㅎ 

 

pop과 peek에서 마지막 value를 처리하는 과정이 달랐다.

1. pop의 경우, self.q.append를 마지막 value에 대해서 처리하지 않았으며

2. peek의 경우, self.q.append를 마지막 value에 대해서 처리해주었다.

 

2. 코드

class MyQueue:

    def __init__(self):
        self.p = []
        self.q = []

    def push(self, x: int) -> None:
        self.p.append(x)

    def pop(self) -> int:
        while (len(self.p)!=0):
            inst = self.p.pop()
            if (len(self.p)!=0):
                self.q.append(inst)
        while (len(self.q)!=0):
            re = self.q.pop()
            self.p.append(re)
        return inst

    def peek(self) -> int:
        while (len(self.p)!=0):
            inst = self.p.pop()
            self.q.append(inst)
        while (len(self.q)!=0):
            re = self.q.pop()
            self.p.append(re)
        return inst

    def empty(self) -> bool:
        if (len(self.p)):
            return False
        return True