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

두 개의 큐로 스택을 구현할 수 있다. 이때 큐는 이미 구현된 것 클래스를 사용했다. 

class Stack:
    def __init__(self) -> None:
        self.inq = linked_list_queue.Queue()
        self.outq = linked_list_queue.Queue()
        
...

 

push

큐 둘 중 하나에 값을 enqueue해주면 된다. 이건 일반적인 스택 push 방법과 동일하다. 

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

pop

이 부분에 조작이 필요하다. 일단 값을 추가한 큐(=inq)에 값이 1개 남을 때까지 dequeue에서 앞에 있는 값들을 모두 또 다른 큐(=outq)에 넣어준다. 그러면 먼저 들어간 요소들이 순차적으로 나와서 그대로 outq에 들어간다. inq에 마지막 남은 요소는 큐에 가장 마지막에 들어간 요소이다. 이것을 반환하고 outq에서 값들을 다시 dequeue해서 inq로 다시 enqueue해주면 된다. (두 큐를 스왑하는 것과 같은 결과이다) 그러면 가장 마지막에 삽입한 요소를 반환하는 stack pop을 구현할 수 있다.  

...
    def pop(self) -> int or None:
        if self.is_empty():
            return None
        
        while self.inq.queue_size() != 1:
            self.outq.enqueue(self.inq.dequeue())
        
        result = self.inq.dequeue()
        self.inq, self.outq = self.outq, self.inq

        return result
...

전체 

push와 pop이외에도 top 값을 확인하는 메소드와 전체 스택을 프린트하는 메소드를 추가로 구현하였다. 

import linked_list_queue

class Stack:
    def __init__(self) -> None:
        self.inq = linked_list_queue.Queue()
        self.outq = linked_list_queue.Queue()

    def is_empty(self) -> bool:
        if self.inq.queue_size() == 0:
            return True
        else:
            return False

    def push(self, data) -> None:
        self.inq.enqueue(data)
    
    def pop(self) -> int or None:
        if self.is_empty():
            return None
        
        while self.inq.queue_size() != 1:
            self.outq.enqueue(self.inq.dequeue())
        
        result = self.inq.dequeue()
        self.inq, self.outq = self.outq, self.inq

        return result

    def check_top(self) -> int or None:
        if(self.is_empty()):
            return None
        while self.inq.queue_size() != 0:
            self.outq.enqueue(self.inq.dequeue())

        result = self.outq.tail.data
        self.inq, self.outq = self.outq, self.inq
        return result

    def print_stack(self) -> None:
        while self.inq.queue_size() != 0:
            self.outq.enqueue(self.inq.dequeue())
        
        print("BOTTOM [ ", end="")
        while self.outq.queue_size() != 0:
            popped = self.outq.dequeue()
            self.inq.enqueue(popped)
            print(popped, end=" -> ")
        print(" ] TOP")