Stack 2개로 Queue, Queue 2개로 Stack 만들기
Stack 2개로 Queue를, Queue 2개로 Stack을 만드는 방법과, 그 시간복잡도에 대해 알아보겠다. 1. Stack 2개로 Queue 만들기 아이데이션inStack과 outStack이 있다. inStack의 입구가 Qin이 되고, outStack의 출구가 Qout이 된다. enqueue 호출 시 1, 2, 3번 공이 순서대로 Stack1에 입력된다. 위에서부터 [3, 2, 1] dequeue 호출 시 outStack이 비어있으면, inStack의 모든 항목을 outStack으로 이동. inStack에서 하나씩 pop해서 outStack에 push한다. 완료되면 outStack은 위에서부터 [1, 2, 3]이 되고, dequeue 호출 시 가장 위에 있는 1부터 제거된다. (그 후의 dequ..
2024. 5. 7.
