[LeetCode] 225. Implement Stack using Queues

https://leetcode.com/problems/implement-stack-using-queues/description/

✅ 문제

Queue 2개를 활용하여 문제에서 주어진 Stack의 메서드를 모두 구현해야한다.

📌  접근방법

새로 들어온 값을 q1에 먼저 넣고, 기존에 q2에 있던 값들을 q1뒤에 모두 붙인다.

그런 다음, q1과 q2를 바꿔치기 해서, q2가 항상 최신 스택 상태를 유지하게 만든다.

즉, q2는 항상 스택처럼 작동하는 큐가 된다.

맨 앞에 항상 스택의 top이 있도록 유지된다.

🔑 풀이

import java.util.*;

class MyStack {

    Queue<Integer> q1;
    Queue<Integer> q2;


    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    
    public void push(int x) {
        q1.add(x);

        while(!q2.isEmpty()) {
            q1.add(q2.poll());
        }

        Queue<Integer> temp = q2;
        q2 = q1;
        q1 = temp;
    }
    
    public int pop() {
        return q2.poll(); // 항상 top이 앞에 있음
    }
    
    public int top() {
        return q2.peek();
    }
    
    public boolean empty() {
        return q2.isEmpty();
    }
}