Queue 2개로 Stack 만들기

구현 방법

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

1. 2개의 Queue를 할당한다.

2. Queue A에 데이터를 추가한다.

3. Pop 연산 수행시 Queue A의 마지막 데이터를 제외하고 이동한다.

4. Queue A에 있는 데이터를 Dequeue한다.

5. Queue A와 Queue B를 스왑한다.

위 과정을 통해 Pop 연산 수행 전 Queue A에 있는 마지막 데이터를 제외한 모든 데이터에 대하여 Queue B에 다시 Enqueue 작업을 수행하면, Queue A에 가장 마지막에 들어온 데이터만 존재하는 것을 알 수 있습니다. 또한, Push 연산의 경우 Enqueue 연산과 동일하게 수행되므로 O(1)의 시간 복잡도를 가지지만, Pop 연산의 경우 N-1개의 데이터를 옮겨야 하므로 O(N)의 시간 복잡도를 가집니다.