[Algorithm] 스택 두 개로 큐 만들기 (Implementing a Queue Using Two Stacks)

 

문제

 

스택 두 개를 이용하여 큐를 만들어라.

 

풀이

 

큐 인터페이스는 offer(넣고), poll(빼고), peek(확인) 메소드를 제공합니다. 

 

이를 구현하기 위해서 스택 2개 각각에 enStack, deStack이라고 명칭을 부여하고 시작하겠습니다.

 

구현 절차는 다음과 같습니다.

 

아래 샘플 데이터로 offer, offer, poll, offer, poll 순으로 요청이 들어왔다고 가정하겠습니다.

 

샘플 데이터

* poll 요청왔을 때 enStack에 있는 데이터 모두를 pop해서 deStack으로 모두 넘겨줍니다.

 

 

* poll 요청왔을 때 deStack이 비어있지 않다면 enStack에서 값을 넘기지 않습니다.

 

코드

 

import java.util.Stack;

public class TwoStacksQueue {	
	public static void main(String[] args) {		
		TwoStacksQueue twoStacksQueue = new TwoStacksQueue();
				
		twoStacksQueue.offer(1);		
		System.out.println("1. offer : 1");
		
		twoStacksQueue.offer(2);		
		System.out.println("2. offer : 2");
		
		System.out.println("3. poll : " + twoStacksQueue.poll());
		
		twoStacksQueue.offer(3);
		System.out.println("4. offer : 3");
		
		System.out.println("5. poll : " + twoStacksQueue.poll());
		
		System.out.println("6. peek : " + twoStacksQueue.peek());		
	}
	
	private Stack<Integer> enStack = new Stack<>();
	private Stack<Integer> deStack = new Stack<>();
	
	public void offer(int data) {
		enStack.add(data);
	}
	
	public int poll() {
		if(deStack.isEmpty()) {
			while (!enStack.empty()) {
				deStack.add(enStack.pop());
			}
		}			
		return deStack.pop();
	}
	
	public int peek() {				
		if(deStack.isEmpty()) {
			while (!enStack.empty()) {
				deStack.add(enStack.pop());
			}	
		}		
		return deStack.peek();
	}
}

 

결과

 

1. offer : 1
2. offer : 2
3. poll : 1
4. offer : 3
5. poll : 2
6. peek : 3