How to implement a queue using two stacks?

https://stackoverflow.com/questions/69192/how-to-implement-a-queue-using-two-stacks

How to implement a queue using two stacks?

---

 

class Queue:
    def __init__(self):
        self.inbox = []
        self.outbox = []

    def enqueue(self, value):
        self.inbox.append(value)

    def dequeue(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

        return self.outbox.pop()

 

답지를 안 보고 계속 고민했는데, 정답에 도달하는 건 실패했다.

 

1. 어디까지 생각했나?

스택 하나에 데이터를 몰아 넣는다. 그리고 다시 pop해서 나머지 스택에 넣으면 반대가 되는 것 까진 생각했는데

이를 자료 구조로 구현하는 것에서 막혔다.

 

 

2. 무엇을 놓쳤는지?

항상 일관성을 유지해야하는 것에만 초점을 맞추다보니까 되려 어렵게 접근했다. 

스택 오버플로 코드를 보니까, 디큐할 때 outbox에 데이터가 존재하는지 체크가 포인트였다... 

 

1. 아웃박스에 데이터가 존재한다면 바로 디큐한다.

2. 그렇지 않다면 인박스에 있는 데이터를 처음 생각한 로직을 이용해서 스택을 뒤집는다.

 

조금 더 풀어서 정리를 해보자면, 아웃박스는 데이터를 내보내기 위한 스택이고 인박스는 데이터를 받는 스택이다.

아웃박스에 데이터가 없다면 인박스에서 데이터를 받아와서 내보낼 준비를 하고, 아웃박스에 데이터가 있으면 그대로 내보낸다.

위 과정에서 삽입되는 데이터는 인박스에 차곡차곡 쌓이고 내보내는 건 아웃박스에서 담당하니까 역할을 제대로 분리하는 접근이 필요했다.

 

머리가 말랑말랑 해진다!