Two Stack Reversal 구조를 통한 Queue의 Amortized O(1) 구현

Context

LIFO 구조인 Stack만을 사용하여 FIFO 특성을 가진 Queue를 구현해야 하는 제약 상황 분석. 단일 Stack 기반의 Brute Force 방식은 Dequeue 시마다 전체 데이터를 재배치하는 고비용 연산 발생으로 인한 성능 저하 문제 존재.

Technical Solution

• 데이터 입력 전용 st1과 출력 전용 st2로 역할을 분리한 Dual Stack 구조 설계
• Push 연산 시 st1에 즉시 저장하여 O(1) 시간 복잡도 달성
• st2가 비어있는 시점에만 st1의 모든 요소를 st2로 이동시켜 데이터 순서를 Reverse하는 Lazy Transfer 로직 적용
• Pop 및 Peek 연산 시 transfer() 메서드를 통한 데이터 정합성 보장
• 불필요한 데이터 이동을 최소화하여 전체적인 처리 효율 증대
• 두 Stack의 상태를 모두 확인하여 Queue의 빈 상태를 판별하는 empty() 로직 구현