[자료구조][Python] : Queue with 2 Stacks(스택으로 큐 구현하기)

자료구조 with Python : 스택 2개로 큐 구현하기

---

큐를 구현하는 방법 중 하나는 스택을 두 개 사용하는 것이다. 여기서는 스택 자료구조를 직접 사용하지 않고 파이썬 내장 리스트를 사용하여 스택을 대신한다.

큐의 구조

• enqueue : 뒤 쪽으로 원소를 삽입하는 함수
• dequeue : 가장 앞에 위치한 원소를 제거하면서 반환하는 함수
• is_empty : 큐가 비어있는지 확인하는 함수
• transfer : in_stack의 원소들을 모두 out_stack으로 옮기는 함수

---

스택 2개를 사용한 큐의 구현

---

class Queue(object):
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def isEmpty(self):
        return not(bool(self.in_stack) or bool(self.out_stack))

    def transfer(self):
        while self.in_stack:
            self.out_stack.append(self.in_stack.pop())

    def enqueue(self, item):
        return self.in_stack.append(item)

    def dequeue(self):
        if not self.out_stack:
            self.transfer()
        if not self.isEmpty():
            return self.out_stack.pop()
        else:
            print("Queue is empty!")

    def __repr__(self):
        tmp = []
        tmp += self.out_stack[::-1]
        tmp += self.in_stack
        if tmp:
            return repr(tmp)
        else:
            return "Queue is empty!"

enqueue를 하게 되면 in_stack 리스트에 데이터를 입력한다. 그러다 dequeue를 실행했을 때 out_stack이 비어있으면 in_stack의 모든 원소들을 pop하여서 가져온다. 이후에 out_stack의 원소들을 pop하게 되면 큐의 동작처럼 FIFO로 데이터가 출력되는 것을 확인할 수 있다.

확인코드

queue = Queue()
for i in range(1, 4):
    queue.enqueue(i)
print(queue)
print("dequeue: {0}".format(queue.dequeue()))
print("dequeue: {0}".format(queue.dequeue()))
queue.enqueue(4)
queue.enqueue(5)
print(queue)
print("dequeue: {0}".format(queue.dequeue()))
print(queue)

---

고찰

가장 중요한 아이디어는 in_stack의 데이터들은 모두 out_stack보다 늦게 들어온 데이터라는 것이다. out_stack에 원소가 있다면 in_stack에서 원소를 가져오지 않고 pop을 해야했다. LIFO를 두 번 사용해서 FIFO로 만드는 게 꽤 흥미로웠다.