스택 두개로 큐 만들기

큐: FIFO(First in first out)

1,2 차례로 push하면 1,2 순서로 출력

스택 : LIFO(Last in first out) 

1,2 차례로 push하면 2,1 순서로 출력

 

스택은 마치 하노이탑과 같이 물건을 쌓아 올린 후에 빼는 것과 같고, 큐는 빨대에 구슬을 넣었을 때 나오는 순서와 같다.

두개의 스택으로 큐 만들기

stack 1은 push용 stack2는 pop용이라 생각하는 것이 편하다.

 

스택 두 개를 활용해서 큐를 만들 수 있다.

1. 스택에 enqueue 하는 경우 스택 1에 데이터를 넣는다.

 

2.  스택 2에서 dequeue 한다(pop 한다)

2-1. 만약 스택 2가 비워져 있는 경우 스택 1에 있는 모든 데이터를 스택 2로 옮긴다. (이 과정에서 stack의 값이 reverse 된다) 

 

3. 스택 2에서 pop 하여 반환한다.

 

쉽게 이야기하면 스택 1에서는 push만 하고 스택 2에서는 pop만 한다.(역할을 나눈다) 

하지만 이 과정에서 스택 2가 비워져 있어 pop() 하지 못하는 경우에만 스택 1에 있는 모든 데이터를 스택 2로 옮겨야 한다.

이렇게 하면 O(1)로 대부분의 과정을 수행할 수 있고, 스택 1에서 스택 2로 옮기는 과정에서 O(n)이 발생한다.