Stack 2개로 Queue 만들기

구현 방법

우선, Queue를 구현하기 위해서 생각해 볼 것은 두 자료구조의 차이를 생각해야 합니다. Stack은 후입선출, Queue는 선입선출 방식을 가지고 있습니다. 즉, 조회/삭제 연산을 선입선출 방식으로 변환하면 됩니다.

이를 위해 다음과 같이 수행하고자 합니다.

1. In, Out 2가지 Stack을 할당한다.

2. In에 데이터를 추가한다.

3. Dequeue 연산 수행시 In에 있는 모든 데이터를 Out으로 이동한다.

4. Out에서 가장 우선 순위가 높은 데이터를 가져온다.

위 과정을 통해 Dequeue 연산 수행 전 In에 있는 모든 데이터에 대해 Pop을 수행하고, Out에 다시 Push 작업을 수행하면 가장 먼저 들어온 데이터의 우선순위가 높아지는 것을 확인할 수 있습니다. 또한, 다음 Dequeue 작업 수행시 Out에 데이터 존재 여부를 확인하면 옮기는 과정 수행 여부를 판단할 수 있기 때문에 O(1)의 분할 상환 시간 복잡도를 가지게 됩니다.