[CS 노트] : Queue 2개를 사용해 Stack을 구현하라

두 개의 큐를 사용해 하나의 스택을 구현하려면 데이터가 두 개의 큐를 잘 왔다갔다 하게 만들면 된다.

 

1-2-3-4순으로 넣고 역시 FIFO이기 때문에 1-2-3-4순으로 나온다. 하지만 여기서 다 빼지 않고 1-2-3까지만 빼고 다른 큐에 넣어두고 4를 남겨두는 것이다.

 

그럼 A큐에는 4만 있고 B큐에는 1-2-3이 있는 상태인데 이때 A큐의 4를 POP해주면 된다. 이런 방식을 반복해서 하면 큐 2개로 스택을 구현하는 것과 같게 되는 것이다.

---

기출로 대비하는 개발자 전공면접 [CS 완전정복] 을 참고해서 공부하였습니다.