문제 정의

두 개의 큐를 활용하여 후입선출(LIFO) 방식의 스택을 구현해야 합니다. push, top, pop, empty 네 가지 기본 연산을 지원해야 하며, 큐의 기본 기능인 push to back, peek/pop from front, size 및 is empty만 사용할 수 있습니다.

해결 방법 1: 단일 큐 사용

스택의 마지막 요소를 큐의 맨 앞에서 제거해야 하는 점이 어려움입니다. 이는 큐의 끝 요소를 제거하는 것이 목표이므로, 해당 요소 앞의 모든 요소를 순차적으로 이동시키고 최종적으로 맨 앞에 위치한 요소를 제거합니다.

코드 예시

import java.util.LinkedList;
import java.util.Queue;

public class MyStack {
    private Queue<Integer> stackQueue = new LinkedList<>();

    public void push(int x) {
        stackQueue.offer(x);
    }

    public int pop() {
        int count = stackQueue.size();
        for (int i = 0; i < count - 1; i++) {
            stackQueue.offer(stackQueue.poll());
        }
        return stackQueue.poll();
    }

    public int top() {
        int count = stackQueue.size();
        for (int i = 0; i < count - 1; i++) {
            stackQueue.offer(stackQueue.poll());
        }
        int peekValue = stackQueue.peek();
        stackQueue.offer(stackQueue.poll());
        return peekValue;
    }

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

    public static void main(String[] args) {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.top()); // 2 출력
        System.out.println(stack.pop()); // 2 출력
        System.out.println(stack.empty()); // false 출력
    }
}

실현 주의사항

top() 메서드에서는 요소를 제거하지 않고 단순히 확인하므로, 제거 후 다시 큐 끝으로 이동시켜 원래 순서를 유지해야 합니다.

해결 방법 2: 이중 큐 사용

두 개의 큐를 통해 데이터 이동을 처리합니다. 하나는 실제 데이터 저장용, 다른 하나는 임시 저장용으로 활용합니다.

코드 예시

import java.util.LinkedList;
import java.util.Queue;

public class MyStackDual {
    private Queue<Integer> mainQueue = new LinkedList<>();
    private Queue<Integer> tempQueue = new LinkedList<>();

    public void push(int x) {
        mainQueue.offer(x);
    }

    public int pop() {
        int size = mainQueue.size();
        for (int i = 0; i < size - 1; i++) {
            tempQueue.offer(mainQueue.poll());
        }
        int result = mainQueue.poll();
        for (int i = 0; i < size - 1; i++) {
            mainQueue.offer(tempQueue.poll());
        }
        return result;
    }

    public int top() {
        int size = mainQueue.size();
        for (int i = 0; i < size - 1; i++) {
            tempQueue.offer(mainQueue.poll());
        }
        int peekValue = mainQueue.peek();
        tempQueue.offer(mainQueue.poll());
        for (int i = 0; i < size; i++) {
            mainQueue.offer(tempQueue.poll());
        }
        return peekValue;
    }

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

실현 주의사항

pop() 메서드에서 데이터 이동 시 반복 횟수를 변수로 관리해야 하며, top() 메서드는 단순히 확인 후 데이터를 복구해야 합니다.

요약

데이터 구조의 이해와 알고리즘 설계 능력을 평가하기 위한 문제로, 실무에서 직접적인 활용 가치는 제한적이지만 핵심 개념을 익히는 데 유용합니다.