스택 두 개로 큐 만들기

모 회사 입사 코딩 테스트에도 나왔던 문제이다. 기본적인 자료구조 활용이라 심플하고도 중요하고, 또 재미있는 문제라고 생각한다.

아이디어

기본 아이디어는 스택 두 개를 하나는 enqueue 전용, 하나는 dequeue 전용으로 두는 것이다.

enqueue 되는 값은 무조건 1번 스택에 push 한다.

dequeue를 할 때는 2번 스택이 비었는지 체크하여 

1. 비지 않았다면 그대로 2번 스택에서 pop 한다.

2. 비어있다면 1번 스택의 모든 요소를 pop하여 2번 스택에 차례로 push한다. 이렇게 하면 1번 스택에 있었던 요소들이 역순으로 2번 스택에 들어간다. 그 후에 pop 하면 된다.

코드

스택을 직접 구현하는 것도 좋지만, 좋은 라이브러리가 있기 때문에 감사히 사용했다.

import java.util.Stack;
 
class Queue {
    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();
 
    public void enqueue(Integer num) {
        stack1.push(num);
    }
 
    public int dequeue() {
        if (!stack2.isEmpty()) {
            return stack2.pop();
        } else {
            while(stack1.size() > 0) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }
    
    public int size() {
        return stack1.size() + stack2.size();
    }
}
 
public class TwoStackToQueue {
    public static void main(String[] args) {
        Queue q = new Queue();
        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);
        
        while(q.size() > 0) {
            System.out.print(q.dequeue() + " ");
        }
    }
}