[java] 스택을 이용한 큐 구현하기

05 Dec 2023

java

개요

스택과 큐는 자료구조의 기본적인 개념 중 하나입니다. 스택은 LIFO (Last-In-First-Out) 방식으로 동작하며, 큐는 FIFO (First-In-First-Out) 방식으로 동작합니다.

이번에는 스택을 이용하여 큐를 구현하는 방법에 대해 알아보겠습니다. 스택을 하나 이용하여 큐의 동작과 같은 결과를 얻을 수 있습니다.

스택으로 큐 구현하기

필요한 자료구조

스택을 구현하기 위해서는 다음과 같은 자료구조가 필요합니다:

입력 스택 (inputStack): 데이터를 입력하는 스택입니다.
출력 스택 (outputStack): 데이터를 출력하는 스택입니다.

큐 메소드 구현

다음은 큐의 주요 메소드를 구현하는 방법입니다:

Enqueue (데이터 입력)

public void enqueue(int data) {
    inputStack.push(data);
}

Enqueue 메소드는 입력 스택인 inputStack에 데이터를 push하는 역할을 합니다.

Dequeue (데이터 출력)

public int dequeue() {
    if (outputStack.isEmpty()) {
        while (!inputStack.isEmpty()) {
            outputStack.push(inputStack.pop());
        }
    }
    return outputStack.pop();
}

Dequeue 메소드는 출력 스택인 outputStack에서 데이터를 pop하여 가져오는 역할을 합니다. 다만, 출력 스택이 비어있는 경우에는 입력 스택의 데이터를 출력 스택으로 옮겨줍니다.

isEmpty (비어있는지 확인)

public boolean isEmpty() {
    return inputStack.isEmpty() && outputStack.isEmpty();
}

isEmpty 메소드는 입력 스택과 출력 스택이 모두 비어있는지를 확인하는 역할을 합니다.

사용 예시

이제 위에서 구현한 스택을 이용한 큐를 사용하는 예시를 살펴보겠습니다:

public static void main(String[] args) {
    QueueUsingStacks queue = new QueueUsingStacks();
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    
    System.out.println(queue.dequeue());  // 출력: 1
    System.out.println(queue.dequeue());  // 출력: 2
    
    queue.enqueue(4);
    
    System.out.println(queue.dequeue());  // 출력: 3
    System.out.println(queue.dequeue());  // 출력: 4
}

위 예시에서는 큐에 순서대로 1, 2, 3을 입력한 후 dequeue를 연속해서 호출하였습니다. 출력 결과는 순서대로 1, 2, 3을 출력하였습니다.

결론

이렇게 스택을 이용하여 큐를 구현할 수 있습니다. 스택과 큐는 많은 알고리즘과 자료구조에서 사용되므로, 이렇게 구현하는 방법을 알아두면 유용할 것입니다.

개요