자료구조/Python3) 스택 2개로 큐 구현하기

스택과 큐는 출력되는 순서가 정반대다. 스택은 가장 나중에 들어간 요소가 가장 먼저 나오고, 큐는 가장 먼저 들어간 요소가 가장 먼저 나온다. 이러한 특성을 이용해서 스택 2개로 큐를 구현할 수도 있다. 

 

---

스택은 미리 구현해 둔 클래스를 사용했다. 일단 스택 두개를 가지고 있어야 한다. 

import linked_list_stack

class Queue:

    def __init__(self):
        self.in_stack = linked_list_stack.Stack()
        self.out_stack = linked_list_stack.Stack()
        
 ...

enqueue

데이터 삽입은 그냥 스택 둘 중 하나에 넣으면 된다. 이 스택은 나는 In_stack이라고 선언했다. 

...
    def enqueue(self, data) -> None:
        self.in_stack.push(data)
...

dequeue

데이터 pop에 별도의 조작이 필요하다. 일단 스택에 데이터가 차례대로 쌓여있고, in_stack에서 그냥 Pop 하면 가장 나중에 들어간 요소가 나오게 된다. 하지만 큐는 여기서 가장 먼저 들어간 요소를 dequeue해야 한다. 그러므로 in_stack에 요소가 1개 남을 때까지 pop하면서 준비된 다른 스택(=out_stack)에 push한다. 마지막 남은 1개는 in_stack에 가장 먼저 들어가서 가장 bottom에 있었던 요소로 이것을 반환하면 된다. 그러면 가장 먼저들어갔던 요소를 반환하는 dequeue를 스택으로도 구현할 수 있다. 반환할 값을 구한 다음에는 원래대로 순서를 돌려놓기 위해 in_stack과 out_stack을 swap해준다. 

전체

import linked_list_stack

class Queue:

    def __init__(self):
        self.in_stack = linked_list_stack.Stack()
        self.out_stack = linked_list_stack.Stack()
    
    def enqueue(self, data) -> None:
        self.in_stack.push(data)

    def dequeue(self) -> int or None:
        if self.in_stack.is_empty():
            print("Queue is Empty")
            return None
        
        while self.in_stack.stack_size() != 1:
            self.out_stack.push(self.in_stack.pop())
        
        result = self.in_stack.pop()

        self.in_stack, self.out_stack = self.out_stack, self.in_stack
        return result