자료구조 - 큐(Queue)

1. 줄 서기의 미학, 큐(Queue)

큐의 핵심 규칙은 선입선출(First-In, First-Out)이다. 먼저 온 사람이 먼저 업무를 본다는 원칙이다.

• 예시 : 맛집 웨이팅, 고속도로 톨게이트, 은행 창구
• 또 다른 예시 : 프린터 인쇄 대기열, 키보드 입력 버퍼(먼저 친 글자가 먼저 찍혀야 하기에)

---

2. 큐를 지키는 두 문지기 : Front와 Rear

스택은 구멍이 하나이기 때문에 Top이라는 포인터만 있으면 됐지만, 큐(터널)는 입구와 출구가 달라서 두 개의 포인터를 관리해야 한다. 이게 스택보다 구현이 조금 더 까다로운 이유이기도 하다.

• Rear (꼬리) : 데이터가 들어오는 곳 (가장 최근 데이터)
  • "새로운 데이터가 들어오면 어디에 줄을 세울까?"를 가리킨다.
  • 데이터가 들어올 때마다 (Enqueue) 뒤로 한 칸씩 물러난다.

• Front (머리) : 데이터가 나가는 곳 (가장 오래된 데이터)
  • "이제 누구 차례지?"를 가리킨다.
  • 데이터가 나갈 때마다 (Dequeue) 뒤로 한 칸씩 따라간다.

---

3. 그림으로 보는 데이터의 흐름

빈 배열 [ , , ] 이 있다고 상상해 보자. (크기 3)

1. 초기 상태: Front와 Rear는 둘 다 시작점(-1 혹은 0)에 있다.
2. Enqueue(10): 10이 들어옵니다. Rear가 한 칸 움직여 자리를 잡는다.
   • [ 10 , , ] (Rear: 0, Front: 0)
3. Enqueue(20): 20이 들어옵니다. Rear가 또 움직인다.
   • [ 10 , 20 , ] (Rear: 1, Front: 0)
4. Dequeue(): 데이터가 나갑니다. 누가 나갈까요? Front가 가리키는 10이 나간다. 나가고 나서 Front는 그 다음 Rear가 가는 방향으로 쫓아간다.
   • [ (삭제) , 20 , ] (Rear: 1, Front: 1로 이동)

핵심: 데이터가 쌓일수록 Rear는 오른쪽으로 도망가고, Front는 그 뒤를 쫓아갑니다.

package step03;

public class MyLinearQueue {
    private int[] queue;
    private int front; // 출구: 나갈 차례인 녀석의 위치
    private int rear;  // 입구: 가장 마지막에 들어온 녀석의 위치
    private int maxBufferSize;

    public MyLinearQueue(int size) {
        this.maxBufferSize = size;
        this.queue = new int[size];
        this.front = 0;
        this.rear = -1; // 아무것도 없는 상태
    }

    // 1. 데이터 넣기 (줄 서기)
    public void enqueue(int value) {
        queue[++rear] = value;
    }

    // 2. 데이터 꺼내기 (입장 시키기)
    public int dequeue() {
        int value = queue[front];
        front++;
        return value;
    }

    // 테스트용
    public void printStatus() {
        System.out.printf("Front: %d, Rear: %d\n", front, rear);
    }

    public static void main(String[] args) {
        MyLinearQueue q = new MyLinearQueue(5);

        System.out.println("--- 데이터 3개 입력 ---");
        q.enqueue(10);
        q.enqueue(20);
        q.enqueue(30);
        q.printStatus(); // Front: 0, Rear: 2 예상

        System.out.println("--- 데이터 1개 삭제 ---");
        System.out.println("나간 값: " + q.dequeue()); // 10 예상
        q.printStatus(); // Front: 1, Rear: 2 예상 (Front가 따라감!)
    }
}

---

4. 선형 큐(Linear Queue)의 치명적 문제점

왜 그냥 배열로 큐를 만들면 안좋은가? 에 대한 이유를 설명해보려고 한다.

 

만약, 배열 크기가 5라고 가정했을때,

1. 데이터를 꽉 채웠다. (Rear가 끝까지 감)
2. 데이터를 전부 꺼냈다. (Front도 끝까지 따라 감)
3. 결과: 배열은 텅 비었지만, Front와 Rear가 이미 낭떠러지 끝(인덱스 4)에 가있는 상태다.

 

문제

• 컴퓨터: "어? Rear가 끝에 닿았네? 더 이상 못 넣어. (꽉 찼어)"
• 사용자: "아니, 앞쪽(0, 1, 2, 3)은 다 비어 있잖아! 앞으로 땡겨서 쓰면 안 돼?"

해결책

• 앞으로 땡기려면(Shift) 배열은 데이터 이동이 일어나 속도가 느려진다. (이전 포스트 참고: https://roajava.tistory.com/247) 그래서 등장한 것이 배열의 끝과 처음을 붙이자 라는 원형 큐(Circular Queue)이다.

 

다음 포스팅으로는 원형 큐(Circular Queue)에 대해 설명해보고자 한다.