Queue는 선입선출(FIFO) 구조이고 Stack은 후입선출(LIFO) 구조이다.
Stack은 Reverse구조이기 때문에 1 > 2 > 3으로 들어간 값이 나올땐 3 > 2 > 1이 된다.
하지만 두개의 스택을 이용하면 Reverser를 두번 하기 때문에 원래 상태로 돌아간다.
Stack1 [1, 2, 3]에 들어간 원소를 Stack2에 담으면 [3, 2, 1]이 되고 이를 다시 순서대로 꺼내면 1 > 2 > 3이 된다.
push, pop을 순서대로 하면 input stack, output stack을 구분해서 데이터만 옮겨주면 되지만
push, pop이 섞이게 될 경우 어려워지게 된다.
아래 예시를 보자. []에서 오른쪽이 스택의 입구이다
---------------------------------------------------------------
push 1, push 2, pop, push 3, push 4, pop, push 5, pop, pop, pop
---------------------------------------------------------------
Queue를 이용하면 순서는 아래처럼 된다.
1. push 1, push 2 = [1, 2]
2. pop = 1, [2]
3. push 3, push 4 = [2, 3, 4]
4. pop = 2, [3, 4]
5. push 5 = [3, 4, 5]
6. pop, pop, pop = 3, 4, 5, []
2개의 스택을 이용하면 아래처럼 해야한다.
1. push 1, push 2
is = [1, 2]
os = []
2. pop
pop 연산을 하게 될 경우 os이 비어있으면 is의 데이터를 os으로 전부 옮겨야 한다.
is = []
os = [2, 1]
os = [2], 1(pop)
3. push 3, push 4
is = [3, 4]
os = [2]
4. pop
os의 데이터가 남아있으니 os의 데이터를 pop한다
is = [3, 4]
os = [], 2(pop)
5. push 5
is = [3, 4, 5]
os = []
6. pop, pop, pop
os가 비어있으니 is의 데이터를 전부 os로 옮긴다.
is = []
os = [5, 4, 3]
pop 연산밖에 없으니 순서대로 pop 한다
os = [], 3, 4, 5(pop pop pop)