1. 구현 원리 및 로직
선입선출(FIFO) 구조인 Queue 2개를 사용하여 후입선출(LIFO) 방식의 Stack을 재현하는 기법.
- q1 (메인 저장소): 데이터 삽입(Push) 시 사용하는 주 저장소 역할.
- q2 (임시 저장소): 데이터 추출(Pop) 시 가장 최근 데이터를 제외한 나머지 원소들을 잠시 보관하는 용도.
- 핵심 메커니즘: 마지막에 들어온 데이터를 추출하기 위해 나머지 데이터를 옮긴 후 두 Queue의 이름을 바꾸는(Swap) 방식 사용.
2. 주요 연산 절차
① Push (데이터 추가)
- 메인 저장소인
q1에enqueue()를 수행하여 데이터를 단순 저장하는 절차.
② Pop (데이터 추출)
- 데이터 이전:
q1에 원소가 1개 남을 때까지 모든 데이터를 추출하여q2에 삽입하는 과정. - 이름 교체(Swap): 최근 데이터를 처리하기 전,
q1과q2를 맞바꾸어 다음 연산을 준비하는 단계. - 최종 추출: 마지막에 남아있던
q1(이름 교체 전 기준)의 원소를 반환하여 후입선출(LIFO) 결과 도출.
3. Python 코드 예시
import queue
class Stack(object):
def __init__(self):
# 두 개의 큐 초기화
self.q1 = queue.Queue()
self.q2 = queue.Queue()
def push(self, element):
# 메인 큐에 데이터 삽입
self.q1.put(element)
def pop(self):
# 마지막 원소만 남을 때까지 q2로 데이터 이동
while self.q1.qsize() > 1:
self.q2.put(self.q1.get())
# 두 큐의 참조를 교체 (Swap)
temp = self.q1
self.q1 = self.q2
self.q2 = temp
# q2에 남은 마지막 원소(가장 최근 데이터) 반환
return self.q2.get()
4. 시간 복잡도 분석 (Time Complexity)
각 연산 수행 시 발생하는 데이터 이동 과정에 따른 성능 분석 결과.
| 연산 | 시간 복잡도 | 비고 |
|---|---|---|
| Push | O(1) | q1에 데이터를 한 번 삽입하는 것으로 완료. |
| Pop | O(n) | q1에 저장된 n개의 원소 중 n-1개를 q2로 옮기는 과정이 필요. |
핵심 정리
- 구현 방식: 큐 두 개의 이름을 서로 바꾸는(Swap) 기법을 활용하여 후입선출(LIFO)을 구현.
- 성능 특징: 데이터 삽입(Push)은 효율적이나, 추출(Pop) 시에는 원소 수에 비례하여 시간이 소요되는 비효율성이 존재.
- 결론: Stack의 구조적 특성을 Queue의 선입선출 원칙을 이용해 풀어내는 논리적 사고 과정을 평가하는 것이 주된 목적.
추가 정리
Q. 이 질문에 답변할 때의 주안점은?
- 구현 알고리즘을 단순 암기하여 답하기보다, 큐의 특성을 어떻게 활용하여 데이터의 순서를 뒤집을지 고민하는 과정을 보여주는 것이 좋음.
- 특히 q1에서 q2로 데이터를 옮긴 뒤 마지막 하나를 추출하고, 다시 q1과 q2의 참조를 바꾸는 로직을 명확히 설명하는 것이 핵심.
Q. 이 자료구조의 실질적인 활용도는?
- 일반적인 Stack에 비해 Pop 연산의 비용이 O(n)으로 높기 때문에 실제 프로덕션 환경에서 사용되는 경우는 드묾.
- 다만, 가용 가능한 자원이 Queue뿐인 특수한 제약 상황에서의 문제 해결 능력을 검증하는 용도로 적합.