자료구조 · 알고리즘 기초집LESSON 07

큐와 덱: 대기열과 작업 순서 관리

난이도초급 → 중급 입문

예상 시간40분

선수지식이전 강의

07강. 큐와 덱: 대기열과 작업 순서 관리

1. 이번 강의에서 해결할 문제

먼저 대기한 플레이어를 먼저 처리하면서도 운영자 긴급 작업은 앞에 넣어야 하는 요구를 목록 인덱스 조작 없이 표현해야 합니다.

2. 학습 목표

3. 핵심 개념

큐는 먼저 들어온 값이 먼저 나가는 FIFO 구조이고, 덱은 양쪽 끝에서 추가·제거할 수 있습니다. Queue의 offer, poll, peek는 실패나 빈 상태에 특별 값을 반환하는 계열이고 add, remove, element는 예외 계열입니다. null을 저장하지 않는 ArrayDeque와 함께 쓰면 poll의 null을 빈 상태로 해석할 수 있습니다.

4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/MatchQueue.java

src/MatchQueue.java
import java.util.ArrayDeque;
import java.util.Deque;

public class MatchQueue {
    public static void main(String[] args) {
        Deque<String> players = new ArrayDeque<>();
        players.offerLast("P1");
        players.offerLast("P2");
        players.offerFirst("ADMIN_TEST");

        String player;
        while ((player = players.pollFirst()) != null) {
            System.out.println("매칭: " + player);
        }
        System.out.println("남은 인원: " + players.size());
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/MatchQueue.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/MatchQueue.java와 out 아래 생성되는 class 파일

Windows PowerShell
Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\MatchQueue.java
java -cp .\out MatchQueue

예상 결과: ADMIN_TEST, P1, P2 순서로 처리되고 남은 인원 0이 출력됩니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

5. 코드와 알고리즘이 동작하는 이유

일반 플레이어는 뒤에 넣고 앞에서 꺼내 FIFO를 유지합니다. 긴급 작업만 앞에 넣습니다. ArrayDeque 양끝 추가·삭제는 일반적으로 O(1)이고 전체 n명을 처리하므로 전체 루프는 O(n), 저장 공간은 O(n)입니다.

6. 자주 하는 실수와 해결법

7. 직접 실습

8. 이해 점검 질문 3개

9. 핵심 요약

MINI QUIZ