[자료구조] (4) Stack 두 개로 Queue 구현하기

2개의 Stack으로 Queue 구현해보기

큐는 FIFO(First In, First Out) 방식으로 작동하는 대표적인 자료구조다. 반면 스택은 LIFO(Last In, First Out) 구조다. 얼핏 보면 정반대의 구조처럼 보이지만, 두 개의 스택을 적절히 조합하면 큐와 같은 동작을 흉내 낼 수 있다.

 

Stack이란?

스택은 데이터를 "쌓는" 방식으로 관리하는 자료구조다. 가장 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last In, First Out) 구조로 작동한다. 마치 책을 한 권씩 쌓아 올리고, 맨 위에 있는 책부터 꺼내는 방식과 같다.

 

→ 연산

스택에서 지원하는 기본 연산은 다음과 같다.

• push(item) : 스택의 맨 위에 데이터를 추가한다.
• pop() : 스택의 맨 위 데이터를 제거하고 반환한다.
• peek() : 스택의 맨 위 데이터를 제거하지 않고 확인한다.
• isEmpty() : 스택이 비어 있는지를 확인한다.

→ 사용 예시

스택은 구조가 단순하고 직관적이어서 다양한 분야에서 활용된다.

• 함수 호출 스택 : 재귀 함수 호출 시, 호출 정보를 쌓고 되돌아올 때 꺼낸다.
• 괄호 유효성 검사 : 여는 괄호를 스택에 저장하고, 닫는 괄호와 매칭을 검사한다.
• 문자열 뒤집기 : 문자열의 각 문자를 스택에 넣었다가 꺼내면 역순이 된다.
• Undo/Redo 기능 : 작업 이력을 스택으로 저장하고 되돌리거나 복원할 수 있다.

Queue란?

큐는 먼저 들어온 데이터가 먼저 나가는 FIFO (First In, First Out) 구조의 자료구조다. 줄 서기처럼 순서를 지키는 방식으로 동작하며, 가장 앞에 들어온 데이터부터 순차적으로 처리된다.

 

→ 연산

큐에서 지원하는 기본 연산은 다음과 같다.

• enqueue(item) : 큐의 뒤쪽(Rear)에 데이터를 추가한다.
• dequeue() : 큐의 앞쪽(Front)의 데이터를 제거하고 반환한다.
• peek() : 가장 앞에 있는 데이터를 제거하지 않고 확인한다.
• isEmpty() : 큐가 비어 있는지를 확인한다.

→ 사용 예시

큐는 순차적 처리나 흐름 제어가 필요한 상황에서 자주 사용된다.

• 프로세스 스케줄링 : 운영체제에서 태스크나 프로세스를 순서대로 처리할 때 사용된다.
• BFS(너비 우선 탐색) : 그래프 탐색 알고리즘에서 탐색 순서를 저장하는 데 쓰인다.
• 프린터 대기열 : 인쇄 요청을 받은 순서대로 처리한다.
• 네트워크 패킷 처리 : 수신한 데이터를 순서대로 처리할 때 사용된다.

왜 스택 2개로 큐를 만들 수 있을까?

스택과 큐는 동작 방식이 정반대이기 때문에, 단일 스택만으로는 큐의 동작(FIFO)을 흉내내기 어렵다. 하지만 스택을 두 개 사용하면 데이터의 순서를 뒤집는 트릭을 통해 큐처럼 동작하게 만들 수 있다.

 

→ 핵심 아이디어

1. 첫 번째 스택(inStack) 에는 데이터를 그대로 쌓는다.
2. 데이터를 꺼내야 할 때(outStack) 가 비어 있으면, inStack에 있는 데이터를 모두 꺼내 outStack에 순서대로 옮긴다.
   이 과정에서 데이터의 순서가 반전된다.
3. 이제 outStack에서 pop하면, 가장 먼저 들어온 데이터부터 꺼낼 수 있게 된다.
4. 이후에는 outStack이 빌 때까지 그대로 사용하고, 다시 비면 inStack에서 옮기는 식으로 반복한다.

import java.util.Stack;

public class MyQueue {
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    // 큐에 데이터 추가 (enqueue)
    public void push(int x) {
        inStack.push(x);
    }

    // 큐에서 맨 앞 데이터 제거하고 반환 (dequeue)
    public int pop() {
        moveIfNeeded();
        return outStack.pop();
    }

    // 큐의 맨 앞 데이터 확인 (peek)
    public int peek() {
        moveIfNeeded();
        return outStack.peek();
    }

    // 큐가 비어있는지 확인
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    // outStack이 비어있으면 inStack의 데이터를 모두 옮김
    private void moveIfNeeded() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
}

 

→ 예시

초기 상태:
inStack: [1, 2, 3]
outStack: []

→ dequeue() 실행
→ inStack → outStack 옮김 (순서 뒤집힘)
outStack: [3, 2, 1]

→ pop() → 1

→ push(4)
inStack: [4]
outStack: [3, 2]

→ dequeue() 실행 → outStack.pop() = 2