[Data Structure] Stack 두 개로 Queue 구현하기

Stack 두 개(First In First Out)로 Queue(Last In First Out) 구현하기

 

스택 두 개를 다음과 같은 용도로 분리하여 사용.

inStack : 데이터를 저장

outStack : 데이터를 꺼낼 때 임시 버퍼로 사용

 

[Queue.class]

package algo_datastructure.stack.queuebystack;
 
import java.util.Stack;
 
class Queue <T> {
    
    private Stack<T> inStack;
    private Stack<T> outStack;
    
    public Queue(){
        inStack = new Stack<T>();
    }
    
    public boolean add(T input) {
        return inStack.add(input);
    }
    
    public T poll() {
        if(!inStack.isEmpty()) {
            outStack = new Stack<T>();
        }
        while(!inStack.isEmpty()) {
            outStack.add(inStack.pop());
        }
        T topItem = outStack.pop();
        while(!outStack.isEmpty()) {
            inStack.add(outStack.pop());
        }
        return topItem;
    }
    
    public T peek() {
        if(!inStack.isEmpty()) {
            outStack = new Stack<T>();
        }
        while(!inStack.isEmpty()) {
            outStack.add(inStack.pop());
        }
        T topItem = outStack.peek();
        while(!outStack.isEmpty()) {
            inStack.add(outStack.pop());
        }
        return topItem;
    }
    
    public boolean isEmpty() {
        return inStack.isEmpty();
    }
    
}
 

[poll() 메소드 설명]

1. 데이터 입력

add(1);

add(2);

add(3);

inStack

3

2

1

2. poll(); 호출

if(!inStack.isEmpty()) {
   outStack = new Stack();
}

inStack	outStack
3
2
1

while(!inStack.isEmpty()) {
   outStack.add(inStack.pop());
}

inStack	outStack
	1
	2
	3

T topItem = outStack.pop();   //1

inStack	outStack
	2
	3

while(!outStack.isEmpty()) {
   inStack.add(outStack.pop());
}

inStack	outStack
3
2

 

[사용]

package algo_datastructure.stack.queuebystack;
 
public class Main {
 
    public static void main(String[] args) {
        
        Queue<Integer> q = new Queue<>();
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println("peek : "+q.peek());
        System.out.println("poll : "+q.poll());
        
        q.add(4);
        System.out.println("peek : "+q.peek());
        while(!q.isEmpty()) {
            System.out.println("poll : "+q.poll());
        }
        
    }
    
}
 

기술면접에서 단골 문제라고 하길래, 이렇게 구현하면 되지 않을까 하고 구현해보았습니다..