[알고리즘] 스택2개로 큐 구현하기

스택 2개로 큐 구현하기

 

 

이번시간에는 스택2개로 하나의 큐를 구현하는 방법을 알아보겠습니다.

 

생각보다 쉽습니다.

 

예를 들어, 1 2 3 4 를 큐에 넣으면 순서대로 1 2 3 4 가 나오겠죠?

 

이를 선입선출이라고 합니다. 하지만 스택은 1 2 3 4 를 넣고 뽑으면, 4 3 2 1 이 나옵니다.

 

스택은 큐와 다르게 선입후출입니다. 하지만!! 스택을 2개를 잘 이용하면

 

선입후출을 이용해, 마치 선입선출처럼 동작하게끔 할 수 있습니다. 아래 그림을 통해 이해해봅시다.

 

이해되시나요???

 

여기서 중요한건... 2번째 스택에 아무것도 없는 상태에서 pop을 수행하려고 할 때 첫번째 스택에 쌓여있는 값들을 전부 2번째 스택으로 이관시키는 것이 포인트입니다!

 

무조건 첫번째 스택에 쌓인 값을 두번째 스택에 옮기는 것이 아니고, 두번째 스택에 아무것도 없는 상태에서 pop을 한 경우에만 이관작업이 이뤄져야 합니다.

 

왜냐구요??... 순수하게 값을 1, 2, 3, 4 넣고 1, 2, 3, 4 를 뽑으면 상관없지만, 1, 2 를 넣고 뽑고 다시 3을 넣고 뽑고 4를 넣고 뽑고 뽑고...식의 입력 출력을 번갈아하는 경우에 제대로 값이 출력되지 않기 떄문입니다. 왜인지는 단계별로 그림을 그리면서 이해해보세요~ ㅎㅎ

 

아래는 전체 소스입니다.

 

package COMMON;

import java.util.Stack;

public class MyQueue {

	public static void main(String[] args) {
		StackQueue q = new StackQueue();
	
		
		q.inQueue(1);
		q.inQueue(2);
		
		System.out.println(q.outQueue());
		
		q.inQueue(3);
		
		System.out.println(q.outQueue());
		System.out.println(q.outQueue());
		
	}

	
	static class StackQueue{
		Stack inqueue;
		Stack outqueue;
		
		StackQueue(){
			this.inqueue = new Stack<>();
			this.outqueue = new Stack<>();
			
		}
		
		void inQueue(int v){
			inqueue.add(v);
			
		}
		
		int outQueue(){
			if(outqueue.isEmpty())//** point **
			while(!inqueue.isEmpty()){
				outqueue.add(inqueue.pop());
			}
			return outqueue.pop();
		}
		
		
	}
}