Queue 2개로 Stack 만들기

2025.03.12 - [면접대비 CS/데이터 구조] - Stack 2개로 Queue 구현하기

Stack 2개로 Queue 구현하기

위에 쓴 Stack 2개로 Queue 만들기보다 훨씬 간단하다.

Queue는 선입선출(FIFO) 구조이고 Stack은 후입선출(LIFO) 구조이다.
---------------------------------------------------------------
push 1, push 2, pop, push 3, push 4, pop, push 5, pop, pop, pop
---------------------------------------------------------------
Stack을 이용하면 순서는 아래처럼 된다. [] < 오른쪽이 스택의 입구이다.
1. push 1, push 2 = [1, 2]
2. pop = [1], 2
3. push 3, push 4 = [1, 3, 4]
4. pop = [1, 3], 4
5. push 5 = [1, 3, 5]
6. pop, pop, pop = [], 5, 3, 1
pop된 순서대로 적어보면  2, 4, 5, 3, 1 순서이다
큐 2개를 q1, q2로 구성한다. queue는 < [] < 오른쪽으로 들어가서 왼쪽으로 나간다.
1. push 1, push 2
q1 = [1, 2]
q2 = []
2. pop
q2가 비어있으니 q1에서 q2로 데이터를 전부 옮기고, 마지막 하나 남은 데이터가 있을 시 출력 후 pop한다.
q2의 데이터를 다시 q1으로 옮긴다.
q1 = [2]
q2 = [1]
q1.pop(), 2, []
q1 = [1]
q2 = []
3. push 3, push 4
q1가 비어있으니 q1에 전부 삽입
q1 = [1, 3, 4]
q2 = []
4. pop
q1에서 q2로 원소가 하나 남을 때 까지 이동시키고 출력 후 pop한다.
q1 = [4]
q2 = [1, 3]
q1.pop() 4, []
다시 q2의 모든 원소를 q1로 이동한다.
q1 = [1, 3]
q2 = []
5. push 5
q1 = [1, 3, 5]
q2 = []
6. pop, pop, pop
위 작업을 그대로 반복한다. q1에 데이터가 하나 남을때까지 q2로 옮기고 출력 후 pop
q1 = [5]
q2 = [1, 3]
q1.pop() 5, [] pop 후 q2의 모든 원소 q1로 이동

q1 = [1, 3]
q2 = []

q1 = [3]
q2 = [1]
q1.pop() 3, [] pop 후 q2의 모든 원소 q1로 이동

q1 = [1]
q2 = []
q1.pop() 1, []

최종 출력 : 2, 4, 5, 3, 1