LeetCode 225(Implement Stack using Queues)

1. 문제 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

2. 문제 설명

• queue를 활용하여 stack을 구현하라.
  • 여기서 stack은 last-in-first-out (LIFO)를 의미
  • 일반적인 stack은 push, top, pop, empty 기능을 지원한다. 
• MyStack 클래스(해당 클래스의 함수를 채워나가야한다.)는 아래의 4가지 함수가 있다.
  • void push(int x): stack의 top에 x element를 push한다.
  • int pop(): stack의 top에 있는 element를 제거하고, 그 값을 반환한다. 
  • int top(): stack의 top에 있는 element를 반환한다.
  • boolean empty(): stack이 비어있으면 True를 그렇지 않으면 False를 반환 

3. 처음 풀이 

• 아주 처음에는 queue를 활용해서 stack을 구현하라는 의미가 이해가 안되서, 
  • MyStack 클래스의 각 함수별 설명을 그대로 구현하였다. 
  • 하지만 아래 풀이는 queue의 특징을 사용하고 있지 않아서, 돌아는 가나, 출제 의도에 맞는 풀이는 아니었다.

class MyStack:

    def __init__(self):
        self.temp = []

    def push(self, x: int) -> None:
        self.temp = [x] + self.temp
        # stack 의 가장 앞에 값을 넣어라

    def pop(self) -> int:
        # stack의 가장 앞에 있는 element를 제거하고, 그 값을 반환하라
        val = self.temp[0]
        self.temp.pop(0)
        return val

    def top(self) -> int:
        # stack의 가장 앞에 있는 elemnt를 반환하라
        return self.temp[0]

    def empty(self) -> bool:
        # 비어있으면, true 아니면 false를 반환하라. 
        return len(self.temp) == 0
        

# 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()

• 아래는 queue를 활용하여 stack을 구현한 풀이
  • 먼저 __init__ 함수에 self.queue = []로 빈 리스트로 셋팅을 해두고,
  • push 함수의 경우
    • self.queue에 값을 append한 후에, 
    • 해당 element를 제외한 elements에 대하여, pop하고 pop한 값을 다시 append하였다.
    • 예를 들어 queue = [1,2,3]일 때, 4가 push되는 상황이라면,
      • 우선은 4를 append해서 queue = [1,2,3,4]로 만든 뒤,
      • 기존의 [1,2,3]을 팝하면서 뒤로 옮겨서 [4,1,2,3]이 되도록 만든다. 
      • 이렇게 되면 나중에 pop을 할 때 Last In First Out으로 구현이 가능하다.
  • 따라서, pop함수의 경우
    • self.queue.pop(0)을 하면 가장 마지막에 넣은 값이 pop이 된다.
  • top함수의 경우도 마찬가지로, self.queue[0]을 반환하면, 가장 마지막에 넣은 값이 보여진다. 
  • 마지막으로 empty는 
    • len(self.queue)==0인지를 체크해줬다. 
    • 최근에 읽은 책에서 보니, 파이썬에서는 리스트가 비어있는지 체크할 때 굳이 len(list) == 0을 쓰지 않고,
      • not list를 써도, list가 비어있으면 False, 값이 있으면 True를 반환한다.
      • 그래서 return not self.queue로 변경해도 되겠다. 

class MyStack:

    def __init__(self):
        self.queue = []

    def push(self, x: int) -> None:
        self.queue.append(x)
        for i in range(len(self.queue)-1):
            self.queue.append(self.queue.pop(0))

    def pop(self) -> int:
        return self.queue.pop(0)

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

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

# 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()

4. 다른 풀이

• 아래처럼 self.queue = [] 리스트를 사용하는 대신
  • collections 라이브러리에 있는 deque()를 사용한 풀이가 많았다. 
• push시에는 그냥 append하고 
• pop함수에서 deque가 지원하는 popleft() 를 사용하여, 
  • 가장 앞의 element부터 뒤로 차곡 쌓은 뒤, self.q.popleft()를 return하면서 가장 마지막에 들어온 element를 return하는 구조로 작성되어있었다.

class MyStack:

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

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

    def pop(self) -> int:
        for i in range (0,len(self.q)-1):
            self.push(self.q.popleft())
        return self.q.popleft()
        

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

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


# 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()

5. 배운 점

• queue로 stack 구현하기.
• deque활용하기
• 알고리즘적인 코드라기보다, data structure를 이해하는데 도움이 되는 문제