[LeetCode] 225. Implement Stack using Queues (해석, Java 풀이)

문제

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

오직 두개의 queue만을 사용하여 후입선출(LIFO)의 stack을 구현하여라. 구현된 스택은 기본 스택의 함수(push, top, pop, empty)들을 지원하여야 한다.

 

MyStack 클래스를 구현하여라.

• void push(int x): 스택의 끝에 x를 넣는다.
• int pop(): 스택의 끝 값을 지우고, 이를 반환한다.
• int top(): 스택의 끝 값을 반환한다.
• boolean empty(): 스택이 비어있으면 true를 반환하고, 아니라면 false를 반환한다.

주의

• 오직 큐의 표준 operation만을 사용하여라. 이는 큐의 끝에서 요소를 추가하는 push, 앞에서 읽거나 제거하는 pop, size와 is empty operation만이 가능하다는 의미이다.
• 큐가 원래 지원되지 않는 경우에는 큐의 표준 작업만 사용한다면 리스트나 덱(양쪽 끝에서 추가/제거 가능한 큐)과 같은 다른 데이터 구조를 사용하여 큐를 시뮬레이션하여라.

 

풀이

class MyStack {
    Queue<Integer> queue;

    public MyStack() {
        queue = new ArrayDeque<>();
    }

    public void push(int x) {
        queue.add(x);
        for(int i = 0 ; i < queue.size() - 1 ; i ++) {
            queue.add(queue.remove());
        }
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

https://github.com/jeongum/java-algorithm/blob/master/stack/LeetCode_225_ImplementStackUsingQueues.java