[스택, 큐] 23 큐를 이용한 스택 구현(Implement Stack using Queues) - 작성중

<LeetCode 문제>

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

Implement Stack using Queues - LeetCode

큐를 이용해 스택의 push, pop, top, empty 연산을 구현하는 문제입니다.

<풀이>

deque에서 append와 popleft만 이용해서 FIFO인 queue로 이용합니다.

 

1. 큐를 하나만 이용(삽입시 O(N))

queue에서 append할때 새로 append한 값을 for문을 통해 제일 왼쪽에 위치하게 하여 스택을 구현합니다.

class MyStack:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        #deque 선언(append, popleft만 사용해서 queue로 이용)
        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() #문제에서 빈 경우는 고려안한다함(고려하면 len(self.q)로 확인)
        

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.q[0] #문제에서 빈 경우는 고려안한다함(고려하면 len(self.q)로 확인)

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        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()

 

2. 큐를 두개 이용(삽입시 O(N))

x가 삽입될 때, 기존에 있던 메인큐 item들을 서브큐로 옮기고
x가 입력된 후, 서브큐에 존재하는 item들을 다시 메인큐로 옮기는 방법을 이용합니다.

 

<학습내용>

1. deque에서의 연산자
2. range객체를 list로 변환했을 때, range(2)은 [0,1], range(1)은 [0], range(0)은 [], range(-1)은 []

<학습이 필요한 내용>

1. append, extend 차이