리트코드 225 큐를 사용해서 스택 구현하기

Implement Stack using Queues - LeetCode

 

2개의 큐를 사용해서 스택 구현.

 

push

요소 x를 스택의 맨위로 push

 

1. 안비어있으면 pop해서 순서대로 두번째 큐에 push.

2. 첫번째 큐에 x를 push

3.두번째큐에서 차례대로 pop하고 1번째큐에 차례로 push

 

 

pop

스택의 맨위 요소 제거하고 반환

pop하고 반환

 

top

스택의 맨위에 있는 요소 반환

 

 

empty

비어있으면 true, 아니면 false

 

 

 

방식

시뮬레이션 해보았을때,

선입선출로 들어온 값들을 이번에 집어넣을 요소 뒤로 차례대로 재 push하면 될 것 같았다.

 

import java.util.ArrayDeque;
import java.util.Queue;

class MyStack {

    private Queue<Integer> queue1 = new ArrayDeque<>();
    private Queue<Integer> queue2 = new ArrayDeque<>();

    public MyStack() {

    }

    public void push(int x) {
        if (!queue1.isEmpty()) {
            while (!queue1.isEmpty()) {
                queue2.add(queue1.poll());
            }
            queue1.add(x);
            while (!queue2.isEmpty()) {
                queue1.add(queue2.poll());
            }
        } else {
            queue1.add(x);
        }
    }

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

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

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

 

 

 

2번째 방식

Deque를 사용한다.

 

push를 하면 그냥 맨앞에서 추가하도록 하는 addFirst()를 사용.

나머지는 그대로.

이게 더 간단해 보인다.

class MyStack {

    private ArrayDeque<Integer> queue;

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

    public void push(int x) {
        //1. 맨앞에 넣는다.
        queue.addFirst(x);
    }

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

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

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