[java] Stack 2개로 Queue 만들기

stack 2개로 Queue 를 구현해보도록 하겠습니다.

 

처음 들었을땐 약간 난감하지만 차근차근 생각해보면 크게 어렵지 않습니다.

 

스택은 마지막에 저장된 데이터가 가장 먼저 출력되기 때문에 마지막에 저장된 데이터 부터 다음 스택으로 옮겨주고 

그때 다시 출력하면 제일 처음에 저장한 데이터를 출력 할 수 있게 된다.

즉 큐 형태가 된다.

 

Stack 1에 먼저 데이터를 A,B,C 순서대로 넣으면 아래와 같이 데이터는 쌓인다. 

 

Stack 1

C

B

A

출력할때는 아래 Stack 2에 데이터를 옮겨서 출력해야 한다. Stack 1의 데이터를 순서대로 출력하면,

C,B,A 순으로 출력되며 순서대로 다시 Stack 2에 저장하면 아래와 같이 저장된다.

그럼 이제 Stack2 데이터를 출력하면 A,B,C 순서대로 출력이 가능하며 즉, Queue와 동일하게 FIFO(First in First out)이 가능해진다. 

 

Stack 2

A

B

C

 

코드로 구현해보겠습니다.

 

Queue클래스에는 데이터가 String, Integer 여러 타입이 들어올 수 있도록 제네릭타입으로 선언해줍니다.

public class StackToQueue {

  public static void main(String[] args) {

    Queue<Integer> queue = new Queue<>();
    queue.enQueue(1);
    queue.enQueue(2);
    queue.enQueue(3);
    System.out.println(queue.deQueue());
    queue.enQueue(4);
    System.out.println(queue.deQueue());
    queue.enQueue(5);
    System.out.println(queue.deQueue());
    System.out.println(queue.deQueue());
    System.out.println(queue.deQueue());
  }
}

class Queue<T>{
  Stack<T> inner = new Stack<>();
  Stack<T> outer = new Stack<>();

  public void enQueue(T data){
    inner.add(data);
  }

  public T deQueue(){
    if(outer.isEmpty()){
      while(!inner.isEmpty()){
        outer.push(inner.pop());
      }
    }
    return outer.pop();
  }
}

 

#출력결과

1 2 3 4 5