[Algorithm] 스택을 이용한 큐 구현

- 설계

 스택 두개를 이용하면 큐를 구현할 수 있습니다. 각각의 스택을 enQueue와 deQueue 연산에 맞게 구분해주면 간단하게 구현이 가능합니다. 

 enQueue 연산이 필요하면 먼저 deQueue 스택에서 모든 자료를 enQueue 스택으로 옮기고 enQueue 스택에 데이터를 Push 해줍니다. deQueue 연산이 필요하면 enQueue 슽개에서 모든 자료를 deQueue 스택으로 옮기고 deQueue 스택에서 데이터를 Pop 해주면 두개의 스택으로 큐를 구현할 수 있습니다.

 혹시 큐를 여러개 사용하면 스택 구현이 가능할까 생각을 해봤는데 큐는 넣는 순서대로 삭제 되기 때문에 맨 마지막에 있는 데이터를 꺼내는 것이 불가능하기 때문에 구현하지 못했습니다. 여기서 말하는 큐는 양방향큐가 아닌 일반 큐 입니다.

- 구현

import java.util.EmptyStackException;
import java.util.Stack;

public class QueueMadeByStack<T> {
	Stack<T> enQueueStack, deQueueStack;
	
	public QueueMadeByStack() {
		enQueueStack = new Stack<T>();
		deQueueStack = new Stack<T>();
	}

	public void enQueue(T inputValue) {
		while (deQueueStack.isEmpty() == false) {
			enQueueStack.push(deQueueStack.pop());
		}
		enQueueStack.push(inputValue);
	}
	
	public T deQueue(){
		T returnValue = null;
		while(enQueueStack.isEmpty() == false){
			deQueueStack.push(enQueueStack.pop());
		}
		try {
			returnValue  = deQueueStack.pop();
		} catch (EmptyStackException e) {
			System.err.println(e.getMessage());
			return null;
		}
		return returnValue;
	}

	public static void main(String[] args) {
		QueueMadeByStack<Integer> q = new QueueMadeByStack<Integer>();
		q.enQueue(1);
		q.enQueue(2);
		q.enQueue(3);
		q.enQueue(4);
		System.out.println(q.deQueue());
		System.out.println(q.deQueue());
		q.enQueue(1);
		q.enQueue(2);
		q.enQueue(5);
		q.enQueue(6);
		System.out.println(q.deQueue());
		System.out.println(q.deQueue());
		System.out.println(q.deQueue());
		System.out.println(q.deQueue());
		System.out.println(q.deQueue());
		System.out.println(q.deQueue());
	}

}