---
title: "큐: FIFO 순서에서 bounded backpressure까지 설계하는 Java 구현"
slug: "java-queue"
category: "CS"
topic: "cs"
subtopic: "data-structures"
tags: ["Java","Queue","ArrayDeque","Backpressure","FIFO"]
status: "published"
created: "2026-08-06"
updated: "2026-08-06"
summary: "FIFO 불변식과 head/tail 상태를 추적하고, ArrayDeque 기반 bounded queue에서 overflow·empty 계약·메모리와 실제 backlog 운영 지표를 연결한다."
kind: "Deep Dive"
evidence: "Java SE 21 Queue/Deque/ArrayDeque/BlockingQueue API를 대조하고 QueueDemo의 FIFO·overflow·empty 경계를 OpenJDK 21.0.11에서 실행"
series: "Java Essential Algorithms"
---

큐는 먼저 도착한 원소를 먼저 꺼내는 FIFO ADT다. 그러나 운영 시스템에서 더 중요한 질문은 “가득 찼을 때 무엇을 할 것인가”다. 무한히 자라는 queue는 overload를 해결하지 않고 heap에 숨긴다.

## 1. 문제 계약: bounded job queue

예제는 capacity가 고정된 in-memory job queue다. `offer`는 빈자리가 있으면 tail에 넣고 true, 가득 차면 block하지 않고 false를 반환한다. `poll`은 head를 제거해 반환하고 비면 null이다. null job은 허용하지 않는다.

이 계약은 producer가 rejection을 보고 retry, drop, upstream throttling 중 하나를 선택하게 한다. `add`/`remove`처럼 예외를 쓰는 Queue method와 `offer`/`poll`처럼 특수값을 쓰는 method를 의도 없이 섞지 않는다.

## 2. head/tail 표현 불변식

capacity 2에서 job 1, 2, 3을 넣고 두 번 꺼낸다.

| 연산 | 반환 | head → tail | 설명 |
| --- | --- | --- | --- |
| `offer(1)` | true | `[1]` | 첫 원소가 head/tail |
| `offer(2)` | true | `[1,2]` | 2는 tail |
| `offer(3)` | false | `[1,2]` | capacity 보존 |
| `poll()` | 1 | `[2]` | 가장 오래된 원소 제거 |
| `poll()` | 2 | `[]` | FIFO 보존 |
| `poll()` | null | `[]` | empty 계약 |

**표현 불변식:** `0 <= size <= capacity`이며 iteration 순서는 성공한 offer 중 아직 poll되지 않은 원소의 도착 순서다. 가득 찬 offer를 거절하면 상태가 바뀌지 않는다. poll은 첫 원소만 제거하므로 남은 상대 순서가 보존된다.

### 처리율 예시로 capacity의 의미를 계산한다

비어 있는 queue에 producer가 초당 120개를 넣고 consumer가 초당 100개를 처리한다고 하자. 평균적으로 backlog는 초당 20개씩 늘어난다. capacity가 1,000이면 약 50초 뒤 가득 찬다. capacity를 10,000으로 키우면 장애가 해결되는 것이 아니라 거절 시점을 약 500초 뒤로 미루고, 오래된 작업의 대기 시간을 키운다.

| 경과 시간 | 누적 유입 | 누적 처리 | 예상 backlog |
| ---: | ---: | ---: | ---: |
| 10초 | 1,200 | 1,000 | 200 |
| 30초 | 3,600 | 3,000 | 600 |
| 50초 | 6,000 | 5,000 | 1,000 |

따라서 bounded queue의 `false` 반환은 단순 실패값이 아니라 overload 신호다. 호출자는 즉시 drop할지, 제한된 횟수만 retry할지, upstream에 429/503을 돌려보낼지 정해야 한다. retry가 다시 arrival rate를 높이면 queue 앞에서 재시도 폭풍이 생기므로 지수 backoff만 넣고 끝내지 말고 rejection rate와 oldest age를 함께 경보로 묶는다.

## 실행 재현

아래 코드는 설명용 조각이 아니라 `main`에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.

```java
import java.util.ArrayDeque;
import java.util.Deque;

public final class QueueDemo {
    record Job(long id, String payload) {}

    static final class BoundedQueue {
        private final int capacity;
        private final Deque<Job> jobs = new ArrayDeque<>();

        BoundedQueue(int capacity) {
            if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
            this.capacity = capacity;
        }

        boolean offer(Job job) {
            if (job == null) throw new IllegalArgumentException("job must not be null");
            if (jobs.size() == capacity) return false;
            jobs.addLast(job);
            return true;
        }

        Job poll() { return jobs.pollFirst(); }
        int size() { return jobs.size(); }
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        BoundedQueue queue = new BoundedQueue(2);
        check(queue.offer(new Job(1, "A")), "first offer");
        check(queue.offer(new Job(2, "B")), "second offer");
        check(!queue.offer(new Job(3, "C")), "backpressure");
        check(queue.poll().id() == 1, "FIFO first");
        check(queue.poll().id() == 2, "FIFO second");
        check(queue.poll() == null, "empty poll");
        System.out.println("order=1,2; overflow rejected; empty=null");
    }
}
```

```bash
javac --release 21 QueueDemo.java
java QueueDemo
```

직접 실행한 출력은 다음과 같다.

```text
order=1,2; overflow rejected; empty=null
```

컴파일러와 런타임은 `javac 21.0.11`, OpenJDK `21.0.11`을 사용했다. `assert` 옵션에 의존하지 않고 실패 시 `AssertionError`를 던지므로 위 명령 그대로 검증된다.


## 3. 왜 배열 deque를 사용하는가

`ArrayDeque`는 양 끝 삽입·삭제를 대부분 amortized constant time에 제공한다. head에서 제거할 때 나머지를 모두 당기는 `ArrayList.remove(0)`와 달리 logical head를 이동할 수 있다. `LinkedList`도 Queue지만 원소별 node와 두 reference를 사용해 allocation/locality 특성이 다르다.

예제 wrapper는 `jobs.size()==capacity`를 확인한 뒤 `addLast`한다. 단일 thread 학습용 구현이며 thread-safe하지 않다. 여러 producer/consumer가 접근하면 check와 insert 사이에 race가 생기므로 `ArrayBlockingQueue` 같은 concurrent bounded queue의 atomic `offer`/`put` 계약을 써야 한다.

## 4. 시간·공간과 resize를 구분한다

wrapper의 offer/poll은 ArrayDeque 양 끝 연산을 사용하므로 amortized $O(1)$이다. 저장 원소가 $k$개면 보조 저장은 $O(k)$이고 bounded 조건에서 $k<=capacity$다. JVM에서 Queue object와 backing array, `Job` record instances는 heap에 있다. local references는 frame에 있지만 job payload가 frame으로 복사되지는 않는다.

generic collection은 reference를 보관한다. primitive job ID만 필요해도 `Queue<Long>`이면 boxing이 생길 수 있다. 정확한 object byte나 resize 시점은 Java API 보장이 아니므로 OpenJDK source/JOL로 사용하는 runtime을 확인한다.

## 5. Little's Law로 backlog를 운영 질문으로 바꾼다

안정 상태에서 평균 queue 길이 $L$, 처리율 $\lambda$, 평균 대기 시간 $W$는 다음 관계를 가진다.

$$
L=\lambda W
$$

알고리즘 복잡도만으로 대기 시간은 결정되지 않는다. arrival rate가 service rate를 넘으면 backlog가 지속적으로 증가한다. capacity는 메모리 한도이자 허용 대기 시간 정책이다. production에서는 queue depth뿐 아니라 **oldest message age**, enqueue rejection, processing rate, retry rate를 함께 본다.

## 6. Stack·PriorityQueue·blocking queue와 비교

| 선택 | 순서 | overload 계약 | 사용 예 |
| --- | --- | --- | --- |
| ArrayDeque Queue | FIFO | wrapper가 결정 | 단일 thread BFS |
| ArrayBlockingQueue | FIFO | block/timeout/reject | producer-consumer |
| PriorityQueue | comparator | 기본 unbounded | 우선순위 scheduler |
| Stack/Deque push | LIFO | capacity 별도 | DFS, undo |

긴급 job을 FIFO 앞에 끼워 넣기 시작하면 queue 계약이 바뀐다. priority queue나 별도 lane을 명시적으로 설계하고 starvation metric을 둔다.

## 7. 실제 도메인 적용

- **Backend worker**: capacity, oldest age, rejection, retry storm, dead-letter count를 본다.
- **Infrastructure deployment**: ready task FIFO가 fairness를 줄 수 있지만 resource priority가 필요하면 scheduler 계약을 분리한다.
- **BFS**: 같은 거리 layer 순서를 보존한다. frontier peak가 graph 폭만큼 커질 수 있으므로 visited 수와 max queue size를 기록한다.
- **Streaming**: event queue만으로 exactly-once가 생기지 않는다. offset commit, idempotency, durability가 별도 계약이다.

## 8. 이건 피한다

- **무제한 queue로 spike를 흡수한다.** 처리율 부족을 heap 증가와 긴 지연으로 바꾼다. bounded capacity와 rejection/backpressure 정책을 둔다.
- **`ArrayList.remove(0)`를 FIFO로 쓴다.** 뒤 원소 이동이 반복돼 총비용이 커진다. deque의 head/tail 연산을 쓴다.
- **`size` 확인 후 insert를 동시 코드에 쓴다.** race로 capacity를 넘거나 상태가 어긋난다. atomic concurrent queue API를 쓴다.
- **null을 job과 empty sentinel로 동시에 쓴다.** 결과를 구분할 수 없다. ArrayDeque처럼 null을 금지하거나 명시적 result type을 쓴다.
- **queue depth만 감시한다.** 낮은 처리율에서 작은 depth도 오래된 job을 숨긴다. oldest age와 처리율을 함께 본다.

## Reference

- Oracle, [Queue — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Queue.html)
- Oracle, [Deque — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Deque.html)
- Oracle, [ArrayDeque — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/ArrayDeque.html)
- Oracle, [BlockingQueue — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/concurrent/BlockingQueue.html)
- John D. C. Little, [A Proof for the Queuing Formula: L = λW](https://doi.org/10.1287/opre.9.3.383)
- Robert Sedgewick, Kevin Wayne, [Algorithms, 4th Edition — Stacks and Queues](https://algs4.cs.princeton.edu/13stacks/)