자바(Java)에서 큐(Queue)를 활용해 스택(Stack) 구현하기

스택(Stack)은 Vector 클래스의 하위 클래스로, 객체들을 후입선출(LIFO, Last-In-First-Out) 방식으로 저장하는 자료구조입니다. 즉, 스택의 맨 위에 가장 마지막에 추가된 요소(In)가 가장 먼저 제거(Out)되는 구조입니다.

반면 큐(Queue)는 Collection 인터페이스를 확장한 인터페이스로, 선입선출(FIFO, First-In-First-Out) 방식으로 삽입(insert)과 제거(remove) 연산을 지원합니다. 두 자료구조의 동작 방식은 서로 반대이지만, 큐를 적절히 활용하면 스택을 구현할 수 있습니다.

동작 원리

핵심 아이디어는 push 연산 시 새로 추가된 요소가 항상 큐의 맨 앞에 위치하도록 재배열하는 것입니다. 새 요소를 큐에 추가한 뒤, 기존에 있던 요소들을 순서대로 꺼내서 다시 뒤에 삽입하면 가장 최근에 추가된 요소가 맨 앞에 오게 됩니다. 이후 remove()를 호출하면 스택과 동일하게 가장 나중에 들어간 요소가 먼저 반환됩니다.

예제 코드

import java.util.*;
public class StackFromQueueTest {
    Queue queue = new LinkedList();

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

    public void pop() {
        System.out.println("An element removed from a stack is: " + queue.remove());
    }

    public static void main(String[] args) {
        StackFromQueueTest test = new StackFromQueueTest();
        test.push(10);
        test.push(20);
        test.push(30);
        test.push(40);
        System.out.println(test.queue);
        test.pop();
        System.out.println(test.queue);
    }
}

실행 결과

[40, 30, 20, 10]
An element removed from a stack is: 40
[30, 20, 10]

코드 설명

• push(int value): 새 값을 큐에 추가한 후, 기존 요소의 개수(queueSize)만큼 요소를 꺼내었다가 다시 뒤에 삽입하여 새 요소를 맨 앞으로 보냅니다.
• pop(): 큐의 맨 앞에 있는 요소, 즉 가장 마지막에 push된 요소를 제거하고 출력합니다.
• 시간 복잡도: push는 기존 요소를 모두 재배열하므로 O(n), pop은 단순 제거이므로 O(1)입니다.

실행 결과에서 확인할 수 있듯이, 10 → 20 → 30 → 40 순서로 push한 값이 40부터 역순으로 제거되며, 일반적인 스택의 LIFO 동작과 완전히 동일하게 작동합니다.