다음과 같은 숙제가 있습니다.

두 개의 큐를 사용하여 스택 메소드 push (x) 및 pop ()을 구현하십시오.

이것은 나에게 이상하게 보입니다.

• 스택 은 (LIFO) 대기열입니다
• 구현하기 위해 두 개의 대기열이 필요한 이유를 모르겠습니다.

나는 주변을 검색했다 :

• GeeksForGeeks
• 스택 오버플로

몇 가지 해결책을 찾았습니다. 이것이 내가 끝낸 것입니다.

public class Stack<T> {
    LinkedList<T> q1 = new LinkedList<T>();
    LinkedList<T> q2 = new LinkedList<T>();

    public void push(T t) {
        q1.addFirst(t);
    }

    public T pop() {
        if (q1.isEmpty()) {
            throw new RuntimeException(
                "Can't pop from an empty stack!");
        }

        while(q1.size() > 1) {
            q2.addFirst( q1.removeLast() );
        }

        T popped = q1.pop();

        LinkedList<T> tempQ = q1;
        q1 = q2;
        q2 = tempQ;

        return popped;
    }
}

그러나 단일 대기열을 사용하는 것의 이점이 무엇인지 이해하지 못합니다. 두 대기열 버전은 무의미하게 복잡해 보입니다.

우리가 푸시를 2보다 효율적으로 선택하고 (위에서 한 것처럼) push동일하게 유지하고 pop단순히 마지막 요소를 반복하고 반환해야한다고 가정 해보십시오. 두 경우 모두는 push것 O(1), 그리고이 pop될 것이다 O(n); 그러나 단일 대기열 버전은 훨씬 간단합니다. 단일 for 루프 만 필요합니다.

뭔가 빠졌습니까? 여기에 대한 통찰력이 있으면 감사하겠습니다.

답변

Queue<T> q1 = new LinkedList<T>();
Queue<T> q2 = new LinkedList<T>();