LeetCode 232(Implement Queue using Stacks)

1. 문제 링크

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

Implement Queue using Stacks - LeetCode

2. 문제 설명

• 큐(Queue)는 선입선출(FIFO, First-In-First-Out) 구조, 스택(Stack)은 후입선출(LIFO, Last-In-First-Out) 구조
• 스택을 사용하여 큐를 구현하는 방법을 구현하는 것이 문제
• 구체적으로 다음 동작을 할 수 있어야 함. 
  • push(x): 큐의 뒤에 요소 x를 삽입
  • pop(): 큐의 앞에서 요소를 제거하고 반환
  • peek(): 큐의 앞에 있는 요소를 반환
  • empty(): 큐가 비어 있는지 여부를 반환

3. 처음 풀이

• submit 통과는 되었으나 내장함수를 어디까지 쓰는 것이 정석이고 어디부터 치팅인 지 모르겠다.
• list는 append, pop()이 원래 후입선출 구조인데 pop()대신 pop(0)을 하거나 그냥 list[0]을 리턴하면 선입선출이 된다. 그런데 pop(0)을 쓰는 것이 문제의 출제 의도가 맞는 지 모르겠음.

class MyQueue:

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

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

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

    def peek(self) -> int:
        return self.stack[0]

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


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

4. 다른 풀이

• 이게 의도한 풀이인 듯.
• pop(0)을 쓰지 않고 pop()만 사용하되 두 개의 stack을 이용하여 풀 수 있음.
• 한 스택은 요소를 삽입하는 데 사용되고, 다른 스택은 요소를 꺼내는 데 사용
• 한 스택에서 후입선출로 다른 스택으로 요소를 옮기면 새로운 스택에는 먼저 넣은 요소가 마지막에 위치하게 됨. 이를 pop()하면 전체적으로 선입선출 구조가 됨.

class MyQueue(object):
    def __init__(self):
        self.in_stk = []
        self.out_stk = []
	# Push element x to the back of queue...
    def push(self, x):
        self.in_stk.append(x)
	# Remove the element from the front of the queue and returns it...
    def pop(self):
        self.peek()
        return self.out_stk.pop()
	# Get the front element...
    def peek(self):
        if not self.out_stk:
            while self.in_stk:
                self.out_stk.append(self.in_stk.pop())
        return self.out_stk[-1]
	# Return whether the queue is empty...
    def empty(self):
        return not self.in_stk and not self.out_stk

5. 배운 점

• collections.deque에 대해 찾아보게 됨.