2개의 스택(Stack) 을 이용하여 큐(Queue) 만들기

2개의 스택을 이용하여 큐를 구현하는 방법을 포스팅 해보겠습니다.

 

생각보다 아주 간단합니다.

 

 

 

 

<그림> 2개의 스택을 사용한 큐를 구현 하는 원리

 

 

알고리즘 내용

1. inBox 에 데이터를 push(삽입)한다. - A,B

2. inBox 에 있는 데이터를 pop(추출) 하여 outBox 에 push(삽입) 한다. - B,A

3. outBox 에 있는 데이터를 pop(추출) 한다. - A,B 순으로 출력됨

 

즉 inBox 스택에 A,B 순으로 데이터를 삽입하면 위에 처럼 inBox 스택에 위와 같은 순서로 쌓입니다.

그리고 inBox 스택에 있는 데이터를 pop 해서 outBox로 옮깁니다. 그렇게 되면

outBox 에는 B, A 순으로 쌓입니다.

그리고 다시 outBox 스택에 있는 데이터를 pop 하는경우 A,B 순으로 데이터가 출력 됩니다.

 

 

자바 소스코드로 보여드리겠습니다.

 

소스코드

public class Queue {

	private Stack inBox = new Stack();
	private Stack outBox = new Stack();
	
	public void enQueue(Object item) {
		inBox.add(item);
	}
	
	public Object deQueue() {
		
		if (outBox.isEmpty()) {
			while(!inBox.isEmpty()) {
				outBox.push(inBox.pop());
			}
		}
		return outBox.pop();
	}
	
	public static void main(String[] args) {
		Queue queue = new Queue();
		queue.enQueue("A");
		queue.enQueue("B");
		queue.enQueue("C");
		
		System.out.println(queue.deQueue());
		System.out.println(queue.deQueue());
		System.out.println(queue.deQueue());
	}

}

출력결과

A,B,C