Stack & Queue 변환: 두 개로 하나 만들기

송윤재·2025년 3월 17일

❓Stack 2개로 Queue 구현

💡아이디어

Stack은 LIFO 이므로 FIFO인 Queue를 구현하기 위해서는 뒤집은 상태로 저장한 Stack이 필요하다
뒤집힌 Stack에 새로운 데이터를 넣을 수 없으니 입력 받을 Stack이 필요하다
데이터를 뒤집힌 Stack에 저장할 타이밍을 정해야 한다

구현

class QueueWithStacks {
	Stack<Integer> forwardStack;
    Stack<Integer> reverseStack;
    
    public QueueWithStacks(){
    	forwardStack = new Stack<>();
        reverseStack = new Stack<>();
    }
    
    public void offer(int data){
    	forwardStack.push(data);
    }
    
    public int poll(){
    	if(reverseStack.isEmpty()){
        	while(!forwardStack.isEmpty()){
            	reverseStack.push(forwardStack.pop());
            }
        }
        
        if(reverseStack.isEmpty()){
        	// 예외처리
        }
        	
        return reverseStack.pop();
    }
}

정리

forwardStack로는 data를 입력 받는다.
reverseStack로는 data를 pop한다.
reverseStack가 비어 있다면 forwardStack에서 reverseStack로 data를 옮긴다.

❓Queue 2개로 Stack 구현

💡아이디어

Queue는 LIFO이므로 2가지 큐를 써서 데이터를 이동해도 순서를 뒤집을 수 없다
Stack의 pop에서 원하는 마지막 요소는 Queue에서 빠질 때 마지막에 위치한다
Queue에서 Queue로 이동할 때 순서가 유지가 되니 Queue를 옮기면서 마지막 데이터만 빼준다
- (굉장히 비효율적인 방법 같다)

구현

class StackWithQueues {
	Queue<Integer> mainQueue;
    Queue<Integer> tempQueue;
    
    public StackWithQueues(){
    	mainQueue = new LinkedList<>();
        tempQueue = new LinkedList<>();
    }
    
    public void push(int data){
    	mainQueue.offer(data);
    }
    
    public int pop(){
    	int ret;
    	if(mainQueue.isEmpty()){
        	// 예외 처리
        }
        
        while(mainQueue.size() != 1){
        	tempQueue.offer(mainQueue.poll());
        }        
        ret = mainQueue.poll();
        
        while(!tempQueue.isEmpty()){
        	mainQueue.offer(tempQueue.poll());
        }
        return ret;
    }
}