[알고리즘/Stack/Queue] Stack으로 Queue 구현, Queue로 Stack 구현

스택 2개로 큐를 만들 수 있고, 큐 2개로 스택을 만들 수 있다. 개인적으로 이 알고리즘을 처음 알았을 때 참신함에 소름이 돋았던 기억이 난다.

스택은 LIFO형태이고, 큐는 FIFO형태 이므로 들어오고 나갈때 저장된 순서를 뒤집을 수 있다면 스택으로 큐를 구현할 수 있고, 큐로 스택을 구현할 수 있다. 그래서 2개가 필요한것이다.

 

# Stack으로 Queue 구현 (뺄때 다른 스택으로 옮겨서 빼자!)

두개의 스택인 A, B 스택이 있다.

- enQueue : A스택에 push

- deQueue : B 스택에 남은게 있다면 B에 있는 것을 pop하고, 남은게 없다면 A스택에 있는 것을 모두 pop해서 B로 push하고 B에 있는 것을 pop한다.

public class Queue {
     Stack<Integer> stackA;
     Stack<Integer> stackB;
     public Queue(){
         stackA = new Stack<>();
         stackB = new Stack<>();
     }
 
     public void enQueue(int v) {
         stackA.push(v);
     }
     public int deQueue() {
         if (stackB.isEmpty()) {
                 while (!stackA.isEmpty()) {
                    stackB.push(stackA.pop());
                }
         }
 
         return stackB.pop();
     }
}