[CS 노트] : Stack으로 Queue를 구현하기

두 개의 Stack를 통해 Queue를 구현할 수 있다. 데이터를 종이컵이라고 생각하고 종이컵 쌓기로 설명을 해 본다.

 

종이컵1,2,3,4를 A스택과 B스택을 사용해 큐를 만들어야 한다. 먼저, 큐는 종이컵이 1-2-3-4로 들어가고 1-2-3-4로 나오게 된다. 스택으로 큐를 구현하는 방법은 간단하다. 먼저 A스택에 종이컵을 push하여 1-2-3-4순서대로 넣는다. 그리고 다시 A스택에 있는 종이컵을 POP하여 B스택에 PUSH를 해 준다. 그럼 A스택에서 종이컵4가 먼저 나오게 되고 B스택에는 종이컵4가 맨 아래에 들어간다. 그 다음은 종이컵3이 pop되고 B스택에서는 종이컵3이 PUSH된다.

 

결국 B스택에는 종이컵4-3-2-1 순서로 쌓이게 되고 이 상태에서 pop을하면 1-2-3-4 순서대로 나오게 되고 결국 이것은 큐를 재현한 것이 되게 된다,

---

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

 

​