Rust VecDeque와 BinaryHeap: 큐와 우선순위 큐

카페에서 줄을 서는 장면을 떠올려 보세요. 새로 온 사람은 줄 맨 뒤에 서고, 바리스타는 맨 앞 사람부터 주문을 받아요. 이번엔 병원 응급실 대기실을 떠올려 볼까요? 거기서는 언제 왔는지와 상관없이 가장 위급한 환자가 먼저 진료를 받아요. 둘 다 “대기 줄”이지만 규칙이 달라요.

Rust에는 각각에 맞는 컬렉션이 있어요. VecDeque 타입은 양쪽 끝에서 넣고 뺄 수 있는 빠른 줄이에요. BinaryHeap 타입은 우선순위 큐(priority queue)로, 항상 가장 큰(또는 가장 급한) 항목을 먼저 꺼내 줘요. 벡터는 이미 알고 있고, HashSet 페이지에서 VecDeque도 살짝 봤죠. 이 페이지에서는 VecDeque를 더 깊이 살펴보고, 거기에 BinaryHeap까지 더해 볼게요.

Vec이 큐로 적합하지 않은 이유

Vec을 큐처럼 쓸 수는 있어요. push로 넣고, remove(0)으로 맨 앞에서 꺼내면 돼요. 잘 동작해요. 문제는 그 뒤에서 무슨 일이 일어나느냐예요.

Vec은 항목들을 0번 위치부터 빈틈없이 붙여서 저장해요. 그래서 첫 번째 항목을 빼면, 빈자리를 메우려고 나머지 항목이 전부 한 칸씩 왼쪽으로 옮겨져야 해요. 항목이 3개면 아무도 눈치채지 못해요. 하지만 10만 개라면 remove(0)을 할 때마다 99,999개의 값이 움직여요. 이게 바로 “O(n)“의 뜻이에요. 목록이 클수록 할 일도 늘어나요.

VecDeque(“벡덱”이라고 읽어요. double-ended queue, 즉 양방향 큐의 줄임말이에요)는 이 문제를 링 버퍼(ring buffer)로 해결해요. 번호가 붙은 의자가 있는 원형 테이블과, “줄은 여기서 시작해요”라고 적힌 작은 표지판을 떠올려 보세요. 첫 번째 사람이 떠나도 아무도 자리에서 일어나지 않아요. 표지판만 다음 자리로 옮기면 끝이에요. 새 사람이 왔는데 마지막 의자가 차 있으면, 0번 의자가 비어 있을 때 거기에 앉아요. 테이블을 한 바퀴 빙 돌아서요. 양쪽 끝에서 넣고 빼는 일은 “표지판 옮기기”나 “의자 하나 채우기”일 뿐이라서, 줄이 아무리 길어도 걸리는 시간이 아주 짧고 항상 같아요. 이게 “O(1)“이에요.

use std::collections::VecDeque;

fn main() {
    // Vec을 큐로 쓰기: 동작은 하지만 remove(0)이 모두를 왼쪽으로 옮겨요.
    let mut vec_line = vec!["민지", "준호", "서연"];
    let served = vec_line.remove(0);
    println!("Vec에서 꺼낸 사람: {served}, 남은 줄: {:?}", vec_line);

    // VecDeque: pop_front는 "시작" 표시만 옮겨요.
    let mut deque_line = VecDeque::from(vec!["민지", "준호", "서연"]);
    let served = deque_line.pop_front();
    println!("VecDeque에서 꺼낸 사람: {:?}, 남은 줄: {:?}", served, deque_line);
}

실행 결과:

Vec에서 꺼낸 사람: 민지, 남은 줄: ["준호", "서연"]
VecDeque에서 꺼낸 사람: Some("민지"), 남은 줄: ["준호", "서연"]

▶ 직접 실행해 보기

결과는 똑같아 보여요. 차이는 속도인데, 줄이 길어져야 비로소 드러나요. 하나 더 눈여겨볼 점이 있어요. pop_front는 Option을 반환해요. 줄이 비어 있으면 프로그램이 죽는 대신 None을 받아요.

VecDeque 기초

VecDeque는 std::collections에 있어서 use 한 줄이 필요해요. 그다음부터는 메서드 이름이 거의 영어 문장처럼 읽혀요. 앞(front)이나 뒤(back)에 push하거나 pop하는 거예요.

use std::collections::VecDeque;

fn main() {
    let mut deque: VecDeque<i32> = VecDeque::new();
    deque.push_back(2);
    deque.push_back(3);
    deque.push_front(1);
    println!("{:?}", deque);

    println!("맨 앞: {:?}, 맨 뒤: {:?}", deque.front(), deque.back());
    println!("길이: {}, 비었나요: {}", deque.len(), deque.is_empty());
    println!("deque[1] = {}", deque[1]);
    println!("get(9) = {:?}", deque.get(9));

    let first = deque.pop_front();
    let last = deque.pop_back();
    println!("꺼낸 값: {:?}, {:?} / 남은 값: {:?}", first, last, deque);
}

실행 결과:

[1, 2, 3]
맨 앞: Some(1), 맨 뒤: Some(3)
길이: 3, 비었나요: false
deque[1] = 2
get(9) = None
꺼낸 값: Some(1), Some(3) / 남은 값: [2]

▶ 직접 실행해 보기

front와 back은 꺼내지 않고 들여다보기만 해요. deque[1]처럼 인덱스로 접근하는 것도 Vec과 똑같아요. 인덱스가 너무 크면 패닉이 나니까, 확실하지 않을 때는 get을 쓰세요.

Vec으로 VecDeque를 만들고, 반복문으로 돌고, 다른 함수가 필요로 하면 다시 Vec이나 슬라이스로 바꿀 수도 있어요.

use std::collections::VecDeque;

fn main() {
    let mut playlist = VecDeque::from(vec!["인트로", "벌스", "코러스"]);
    playlist.push_front("카운트인");
    playlist.push_back("아웃트로");

    for (i, song) in playlist.iter().enumerate() {
        println!("{}. {}", i + 1, song);
    }

    // 평범한 슬라이스가 필요하다면? make_contiguous가 메모리에 한 줄로 정리해 줘요.
    let songs = playlist.make_contiguous();
    songs.sort();
    println!("정렬 후: {:?}", songs);

    // 아니면 통째로 다시 Vec으로 바꿔요.
    let as_vec: Vec<&str> = playlist.into();
    println!("Vec으로: {:?}", as_vec);
}

실행 결과:

1. 카운트인
2. 인트로
3. 벌스
4. 코러스
5. 아웃트로
정렬 후: ["벌스", "아웃트로", "인트로", "카운트인", "코러스"]
Vec으로: ["벌스", "아웃트로", "인트로", "카운트인", "코러스"]

▶ 직접 실행해 보기

make_contiguous는 왜 필요할까요? 원형 테이블을 떠올려 보세요. 한 바퀴 돌아서 앉다 보면 항목들이 메모리의 서로 떨어진 두 조각에 나뉘어 있을 수 있어요. make_contiguous는 이걸 한 조각으로 정리한 다음 평범한 슬라이스를 돌려줘요. 그래서 sort 같은 슬라이스 도구를 쓸 수 있어요. 자주 쓰지는 않겠지만, 이런 게 있다는 걸 알아 두면 좋아요. (참고로 한글 문자열은 가나다순으로 정렬돼요.)

VecDeque를 실제로 쓰는 곳

VecDeque가 딱 맞는 일상적인 작업 세 가지를 볼게요.

먼저 온 순서대로 처리하는 작업 큐. 인쇄 작업이 줄을 서서 기다려요. 새 작업은 뒤로 가고, 프린터는 앞에서부터 가져가요. 급한 작업은 push_front로 새치기할 수도 있어요.

use std::collections::VecDeque;

fn main() {
    let mut print_queue = VecDeque::new();
    print_queue.push_back("report.pdf");
    print_queue.push_back("photo.jpg");
    print_queue.push_back("invoice.pdf");

    // 급해요! 이 작업은 줄 맨 앞으로 끼어들어요.
    print_queue.push_front("boarding-pass.pdf");

    while let Some(job) = print_queue.pop_front() {
        println!("인쇄 중: {job} (대기 {}개)", print_queue.len());
    }
    println!("모두 끝났어요. 큐가 비었나요: {}", print_queue.is_empty());
}

실행 결과:

인쇄 중: boarding-pass.pdf (대기 3개)
인쇄 중: report.pdf (대기 2개)
인쇄 중: photo.jpg (대기 1개)
인쇄 중: invoice.pdf (대기 0개)
모두 끝났어요. 큐가 비었나요: true

▶ 직접 실행해 보기

while let Some(job) = ...pop_front()는 큐를 처리하는 전형적인 반복문이에요. pop_front가 None을 반환할 때까지, 즉 줄이 빌 때까지 계속 돌아요. (이 모양이 낯설다면 if let 페이지를 보세요.)

“최근 N개” 기록. 최근 검색어 3개를 기억하는 검색창이에요. 꽉 차면 가장 오래된 검색어가 앞에서 떨어져 나가요.

use std::collections::VecDeque;

const MAX_RECENT: usize = 3;

fn remember(recent: &mut VecDeque<String>, search: &str) {
    if recent.len() == MAX_RECENT {
        recent.pop_front(); // 가장 오래된 검색어를 잊어요
    }
    recent.push_back(search.to_string());
}

fn main() {
    let mut recent = VecDeque::with_capacity(MAX_RECENT);

    for search in ["러스트 책", "vecdeque", "바이너리 힙", "근처 피자집"] {
        remember(&mut recent, search);
        println!("{:?}", recent);
    }

    // 검색창처럼 최신 검색어부터 보여 줘요.
    let newest_first: Vec<&String> = recent.iter().rev().collect();
    println!("최신순: {:?}", newest_first);
}

실행 결과:

["러스트 책"]
["러스트 책", "vecdeque"]
["러스트 책", "vecdeque", "바이너리 힙"]
["vecdeque", "바이너리 힙", "근처 피자집"]
최신순: ["근처 피자집", "바이너리 힙", "vecdeque"]

▶ 직접 실행해 보기

이동 평균(sliding window). 온도계가 1분마다 측정값을 보내고, 여러분은 최근 3개의 평균을 알고 싶어요. 새 측정값은 뒤로 들어오고, 가장 오래된 값은 앞으로 나가요. 합계 sum을 계속 갱신해 두면 매번 창(window) 전체를 다시 더할 필요가 없어요.

use std::collections::VecDeque;

fn main() {
    let readings = [20.0, 22.0, 24.0, 23.0, 19.0, 21.0];
    let window_size = 3;
    let mut window: VecDeque<f64> = VecDeque::new();
    let mut sum = 0.0;

    for reading in readings {
        window.push_back(reading);
        sum += reading;

        if window.len() > window_size {
            sum -= window.pop_front().unwrap(); // 가장 오래된 측정값이 빠져요
        }

        if window.len() == window_size {
            let average = sum / window_size as f64;
            println!("{:?} -> 평균 {:.1}", window, average);
        }
    }
}

실행 결과:

[20.0, 22.0, 24.0] -> 평균 22.0
[22.0, 24.0, 23.0] -> 평균 23.0
[24.0, 23.0, 19.0] -> 평균 22.0
[23.0, 19.0, 21.0] -> 평균 21.0

▶ 직접 실행해 보기

여기서 unwrap()은 안전해요. 창에 항목이 3개보다 많을 때만 꺼내니까 비어 있을 수가 없거든요.

BinaryHeap: 항상 가장 큰 것부터

이제 응급실 대기실 차례예요. 누가 먼저 왔는지는 중요하지 않을 때가 있어요. 새 항목이 계속 들어오는 동안 “지금 가장 중요한 걸 줘”를 몇 번이고 하고 싶은 거예요.

모든 걸 Vec에 넣고 매번 정렬할 수도 있어요. 하지만 맨 위 항목 하나를 찾자고 전부 정렬하는 건 낭비가 커요. BinaryHeap 타입은 항목들을 느슨하게만 정리해 둬요. 가장 큰 항목이 항상 맨 위에 있을 만큼만요. 항목을 넣거나 맨 위 항목을 꺼내는 비용은 싸요. O(log n)인데, 아주 천천히 늘어나요. 항목이 10만 개여도 17단계 정도예요.

Rust의 BinaryHeap은 최대 힙(max-heap)이에요. pop은 항상 가장 큰 값을 줘요. 경매의 입찰가로 볼게요.

use std::collections::BinaryHeap;

fn main() {
    let mut bids = BinaryHeap::new();
    bids.push(120);
    bids.push(450);
    bids.push(80);
    bids.push(300);

    println!("최고 입찰가: {:?}", bids.peek());
    println!("입찰 수: {}", bids.len());

    while let Some(bid) = bids.pop() {
        println!("다음: {bid}");
    }

    let heap = BinaryHeap::from(vec![5, 1, 4, 2, 3]);
    println!("정렬: {:?}", heap.into_sorted_vec());
}

실행 결과:

최고 입찰가: Some(450)
입찰 수: 4
다음: 450
다음: 300
다음: 120
다음: 80
정렬: [1, 2, 3, 4, 5]

▶ 직접 실행해 보기

peek은 맨 위 항목을 꺼내지 않고 들여다봐요. pop은 꺼내요. into_sorted_vec은 힙을 소비해서, 작은 값부터 큰 값 순으로 정렬된 Vec을 줘요. VecDeque처럼 peek과 pop도 Option을 반환하니까, 힙이 비어 있어도 프로그램이 죽지 않아요.

Reverse로 만드는 최소 힙

가장 작은 값부터 받고 싶다면요? 가장 가까운 배송지, 가장 싼 항공권, 가장 빠른 마감일처럼요. 다른 컬렉션은 필요 없어요. 값을 std::cmp::Reverse로 감싸기만 하면 돼요. Reverse는 비교를 뒤집을 뿐이에요. 가장 컸던 것이 이제 가장 작은 것이 돼요.

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    // 배송지까지의 거리(km). 항상 가장 가까운 곳으로 먼저 가요.
    let mut stops = BinaryHeap::new();
    for km in [12, 3, 8, 5] {
        stops.push(Reverse(km));
    }

    if let Some(Reverse(closest)) = stops.peek() {
        println!("가장 가까운 배송지: {closest}km");
    }

    while let Some(Reverse(km)) = stops.pop() {
        println!("{km}km 이동");
    }
}

실행 결과:

가장 가까운 배송지: 3km
3km 이동
5km 이동
8km 이동
12km 이동

▶ 직접 실행해 보기

Reverse(km)는 아주 작은 래퍼 구조체예요. Some(Reverse(km)) 패턴은 두 겹을 한 번에 벗겨 내서 평범한 숫자를 돌려줘요.

구조체로 만드는 우선순위 큐

실제 작업은 숫자 하나로 끝나지 않아요. 이름도 있고, 우선순위도 있고, 도착 시각이 있을 수도 있죠. 직접 만든 구조체를 BinaryHeap에 넣으려면 Rust가 두 값을 어떻게 비교할지 알아야 해요. 즉 구조체가 Ord를 구현해야 해요(자주 쓰는 트레이트 참고).

가장 빠른 방법은 derive예요. 한 가지 알아 둘 점이 있어요. derive는 필드를 위에서 아래 순서로 비교해요. 첫 번째 필드를 비교하고, 그 값이 같을 때만 두 번째 필드를 봐요. 그러니 정렬 기준으로 쓸 필드를 맨 앞에 두세요.

use std::collections::BinaryHeap;

// 필드 순서가 중요해요: derive는 `priority`를 먼저, 그다음 `name`을 비교해요.
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Task {
    priority: u8,
    name: String,
}

fn main() {
    let mut todo = BinaryHeap::new();
    todo.push(Task { priority: 2, name: "이메일 답장하기".to_string() });
    todo.push(Task { priority: 5, name: "서버 장애 고치기".to_string() });
    todo.push(Task { priority: 1, name: "화분에 물 주기".to_string() });
    todo.push(Task { priority: 2, name: "치과 예약하기".to_string() });

    while let Some(task) = todo.pop() {
        println!("[{}] {}", task.priority, task.name);
    }
}

실행 결과:

[5] 서버 장애 고치기
[2] 치과 예약하기
[2] 이메일 답장하기
[1] 화분에 물 주기

▶ 직접 실행해 보기

두 필드의 순서를 바꿔서 name이 앞에 오면, 힙은 작업을 이름의 가나다순으로 정렬하고 우선순위는 거의 무시해 버려요. 하기 쉬운 실수인데, 에러도 없이 조용히 생기는 버그예요.

우선순위가 2인 두 작업을 보세요. 동점은 name으로 갈렸어요. “치과”가 “이메일”보다 가나다순으로 뒤에 있어서 “더 크다”고 판단됐고, 그래서 먼저 나왔어요. 예측은 가능하지만, 아마 원하던 결과는 아닐 거예요. 먼저 들어온 건 “이메일 답장하기”였으니까요. 보통은 동점일 때 먼저 도착한 작업이 먼저 나와야 해요. 이런 나만의 규칙이 필요하면 Ord를 직접 작성하세요.

use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(Debug, PartialEq, Eq)]
struct Job {
    priority: u8,
    id: u32, // 도착 순서: id가 작을수록 먼저 도착했어요
    name: String,
}

impl Ord for Job {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority
            .cmp(&other.priority) // 우선순위가 높은 쪽이 이겨요
            .then_with(|| other.id.cmp(&self.id)) // 동점이면 id가 작은 쪽이 이겨요
    }
}

impl PartialOrd for Job {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut jobs = BinaryHeap::new();
    jobs.push(Job { priority: 2, id: 1, name: "이메일 답장하기".to_string() });
    jobs.push(Job { priority: 5, id: 2, name: "서버 장애 고치기".to_string() });
    jobs.push(Job { priority: 1, id: 3, name: "화분에 물 주기".to_string() });
    jobs.push(Job { priority: 2, id: 4, name: "치과 예약하기".to_string() });

    while let Some(job) = jobs.pop() {
        println!("[{}] #{} {}", job.priority, job.id, job.name);
    }
}

실행 결과:

[5] #2 서버 장애 고치기
[2] #1 이메일 답장하기
[2] #4 치과 예약하기
[1] #3 화분에 물 주기

▶ 직접 실행해 보기

비결은 then_with에 있어요. 우선순위가 같으면 id를 거꾸로(self.id가 아니라 other.id를 기준으로) 비교해요. 그러면 id가 작은 쪽이 “더 큰” 것으로 취급되어 최대 힙에서 먼저 나와요. 이 부분이 바로 이해되지 않아도 괜찮아요. 비교를 뒤집는 건 Reverse가 해 주는 일과 똑같은데, 그걸 손으로 쓴 것뿐이에요. PartialOrd 블록은 늘 똑같은 상용구(boilerplate)예요. 여러분의 cmp를 호출하기만 해요.

실전 알고리즘: 상위 3개 점수

게임 점수가 엄청나게 많은데 상위 3개만 필요하다고 해 볼게요. 전체 목록을 정렬해도 되지만, 항목을 딱 3개만 들고 있는 깔끔한 방법이 있어요.

크기가 3인 최소 힙을 쓰는 거예요. 점수를 하나씩 넣고, 힙에 항목이 4개가 되면 하나를 꺼내요. 최소 힙이니까 버려지는 건 가장 작은 점수예요. 끝까지 하고 나면 가장 높은 3개만 남아요.

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let scores = [72, 95, 64, 88, 91, 55, 99, 80];
    let mut top = BinaryHeap::new(); // 최소 힙: 가장 작은 점수가 맨 위에 있어요

    for score in scores {
        top.push(Reverse(score));
        if top.len() > 3 {
            top.pop(); // 4개는 하나가 많아요: 가장 작은 걸 버려요
        }
    }

    let best: Vec<u32> = top
        .into_sorted_vec()
        .into_iter()
        .map(|Reverse(score)| score)
        .collect();
    println!("상위 3개: {:?}", best);
}

실행 결과:

상위 3개: [99, 95, 91]

▶ 직접 실행해 보기

덤으로 좋은 점도 있어요. into_sorted_vec은 Reverse 값을 “작은 것”부터 “큰 것” 순으로 정렬하는데, 실제 점수로 보면 큰 것부터 작은 것 순이에요. 그래서 따로 정렬하지 않아도 최고 점수가 맨 앞에 와요. 이 패턴은 점수가 백만 개여도 메모리에는 항상 4개만 들고 있으면서 동작해요.

무엇을 써야 할까요?

한눈에 보는 정리표예요. “빠름”은 컬렉션이 아무리 커져도 시간이 거의 같다는 뜻이고, “느림”은 크기에 따라 시간이 늘어난다는 뜻이에요.

컬렉션	잘하는 일	넣기	앞 / 맨 위에서 꺼내기	아무 항목이나 찾기
Vec<T>	위치로 읽는 목록, 스택	끝에서 빠름	느림 (remove(0)이 전부 옮김)	느림 (하나씩 확인)
VecDeque<T>	큐: 양쪽 끝에서 넣고 빼기	양쪽 끝에서 빠름	양쪽 끝에서 빠름	느림 (하나씩 확인)
BinaryHeap<T>	“가장 큰 것 / 가장 급한 것부터 줘”	꽤 빠름 (O(log n))	꽤 빠름: 항상 가장 큰 값	느림, 정렬된 순서도 없음
BTreeSet<T>	중복 없는 값을 항상 정렬된 상태로	꽤 빠름 (O(log n))	꽤 빠름: 가장 작은 값과 가장 큰 값	꽤 빠름 (O(log n))

잘 모르겠으면 Vec으로 시작하세요. 앞에서 꺼내는 일이 생기면 VecDeque를 쓰세요. “지금 가장 중요한 게 뭐지?“를 계속 묻는다면 BinaryHeap을 쓰세요. 정렬되고 중복 없는 값이 필요하고, 맨 위 하나만 꺼내는 게 아니라 항목을 찾아보기도 해야 한다면 BTreeSet을 쓰세요.

자주 하는 실수

BinaryHeap의 .iter()가 정렬되어 있을 거라고 기대하기. 힙은 느슨하게만 정리되어 있어요. 가장 큰 항목은 맨 앞에 있지만, 나머지는 힙에게만 쓸모 있는 뒤죽박죽 순서예요. 여러분에게는 쓸모가 없어요.

use std::collections::BinaryHeap;

fn main() {
    let heap = BinaryHeap::from(vec![1, 5, 2, 8, 3, 9]);

    println!("iter:   {:?}", heap.iter().collect::<Vec<_>>());
    println!("sorted: {:?}", heap.clone().into_sorted_vec());

    let mut heap = heap;
    print!("popped:");
    while let Some(n) = heap.pop() {
        print!(" {n}");
    }
    println!();
}

실행 결과:

iter:   [9, 8, 2, 5, 3, 1]
sorted: [1, 2, 3, 5, 8, 9]
popped: 9 8 5 3 2 1

▶ 직접 실행해 보기

(이 예제의 레이블은 공백으로 줄을 맞춰 두었기 때문에 영어 그대로 두었어요. 한글은 화면에서 두 칸을 차지해서 줄이 어긋나거든요.)

힙을 {:?}로 출력할 때도 마찬가지로 내부의 뒤죽박죽 순서가 보여요. 순서대로 필요하다면 pop으로 하나씩 꺼내거나 into_sorted_vec을 호출하세요.

Ord가 없는 구조체를 BinaryHeap에 넣기. 힙은 어떤 항목을 맨 위에 둘지 알려고 항목끼리 비교해야 해요. 구조체를 비교할 수 없으면 Rust가 막아요.

use std::collections::BinaryHeap;

struct Ticket {
    urgency: u8,
    title: String,
}

fn main() {
    let mut tickets = BinaryHeap::new();
    tickets.push(Ticket { urgency: 3, title: "로그인 안 됨".to_string() });
}

error[E0277]: the trait bound `Ticket: Ord` is not satisfied
  --> src/main.rs:10:13
   |
10 |     tickets.push(Ticket { urgency: 3, title: "로그인 안 됨".to_string() });
   |             ^^^^ the trait `Ord` is not implemented for `Ticket`
   |
help: consider annotating `Ticket` with `#[derive(Ord)]`

컴파일러 메시지는 영어로 나와요. “Ticket에 Ord 트레이트가 구현되어 있지 않다”는 뜻이고, #[derive(Ord)]를 붙여 보라고 도움말도 줘요. 해결 방법은 구조체 위에 #[derive(PartialEq, Eq, PartialOrd, Ord)]를 붙이고(Ord는 나머지 세 개도 필요로 해요), urgency를 첫 번째 필드로 두는 거예요. 아니면 위의 Job 예제처럼 Ord를 직접 작성하세요.

연습 문제

1. 차례대로 돌아가기

세 친구 민지, 준호, 서연이 보드게임에서 차례를 돌아가며 해요. 세 사람을 VecDeque에 넣고, 1번째부터 5번째 차례까지 누가 하는지 출력하세요. 차례가 끝난 사람은 줄 맨 뒤로 가요. 힌트: pop_front로 사람을 꺼내 출력한 다음, 같은 사람을 push_back하세요.

정답 보기

use std::collections::VecDeque;

fn main() {
    let mut players = VecDeque::from(vec!["민지", "준호", "서연"]);

    for turn in 1..=5 {
        let player = players.pop_front().unwrap();
        println!("{turn}번째 차례: {player}");
        players.push_back(player); // 다시 줄 맨 뒤로
    }
}

실행 결과:

1번째 차례: 민지
2번째 차례: 준호
3번째 차례: 서연
4번째 차례: 민지
5번째 차례: 준호

▶ 직접 실행해 보기

VecDeque는 앞과 뒤가 모두 빠르니까, 사람이 아무리 많아도 줄을 돌리는 데 드는 비용은 거의 없어요.

2. 응급실

환자들이 1부터 5까지의 위급도를 가지고 도착해요. 가장 위급한 환자가 먼저 진료를 받아요. 위급도가 같으면 먼저 도착한 사람이 먼저예요. 튜플을 담은 BinaryHeap을 써서 진료 순서를 출력하세요. 환자는 지아(위급도 2, 1번째 도착), 도윤(5, 2번째), 하준(2, 3번째), 유나(4, 4번째)예요. 힌트: 튜플은 derive한 구조체처럼 필드 하나하나를 차례로 비교해요. (severity, Reverse(arrival), name)을 써 보세요.

정답 보기

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    // (위급도, Reverse(도착 순서), 이름)
    let mut waiting = BinaryHeap::new();
    waiting.push((2, Reverse(1), "지아"));
    waiting.push((5, Reverse(2), "도윤"));
    waiting.push((2, Reverse(3), "하준"));
    waiting.push((4, Reverse(4), "유나"));

    while let Some((severity, Reverse(arrival), name)) = waiting.pop() {
        println!("{name} (위급도 {severity}, {arrival}번째 도착)");
    }
}

실행 결과:

도윤 (위급도 5, 2번째 도착)
유나 (위급도 4, 4번째 도착)
지아 (위급도 2, 1번째 도착)
하준 (위급도 2, 3번째 도착)

▶ 직접 실행해 보기

위급도를 먼저 비교하니까 도윤이 가장 먼저예요. 지아와 하준은 위급도가 같아서 Reverse(arrival)가 순서를 정하고, 먼저 도착한 지아가 이겨요. 도착 번호가 모두 다르니까 동점을 가르는 데 이름까지 쓰일 일은 없어요.

정리

• Vec은 큐로 쓰기에 좋지 않아요. remove(0)이 나머지 항목을 전부 옮기거든요. VecDeque는 링 버퍼라서 양쪽 끝의 push/pop이 빨라요.
• VecDeque는 먼저 온 순서대로 처리하는 큐, “최근 N개” 기록, 이동 평균 같은 슬라이딩 윈도우에 써요.
• BinaryHeap은 최대 힙이에요. pop과 peek은 전부 정렬하지 않고도 항상 가장 큰 항목을 줘요.
• 값을 std::cmp::Reverse로 감싸면 최소 힙(가장 작은 것부터)이 돼요.
• 힙에 넣는 구조체에는 Ord가 필요해요. derive를 쓰면 필드를 위에서 아래로 비교하니까 우선순위 필드를 맨 앞에 두세요. 동점 처리 규칙을 직접 정하려면 Ord를 손으로 작성하세요.
• 힙의 .iter()는 정렬되어 있지 않아요. 하나씩 pop하거나 into_sorted_vec을 쓰세요.

이해도 점검

이해도 점검

1. 긴 목록에서 VecDeque::pop_front가 Vec::remove(0)보다 빠른 이유는 무엇일까요?

VecDeque는 항목을 더 적게 저장해서 Vec::remove(0)은 나머지 항목을 전부 왼쪽으로 옮기지만, VecDeque는 시작 위치만 옮겨서 VecDeque는 먼저 항목을 정렬해서 차이가 없어요

2. BinaryHeap에 4, 9, 2를 넣었어요. 첫 번째 pop()은 무엇을 반환할까요?

Some(4) Some(2) Some(9) None

3. BinaryHeap이 가장 작은 값부터 주게 하려면 어떻게 해야 할까요?

각 값을 std::cmp::Reverse로 감싸요 힙에 .reverse()를 호출해요 pop 대신 pop_front를 써요 불가능해요. Vec을 써야 해요

4. 어떤 구조체가 name, priority 순서의 필드로 Ord를 derive했어요. BinaryHeap에서 순서를 정하는 건 무엇일까요?

priority만 Rust가 가장 쓸모 있는 필드를 골라요 항목을 넣은 순서 name이 먼저, priority는 동점일 때만

점수: 0 / 4

더 알아보기

• std::collections — 표준 라이브러리 문서 (영어): “어떤 컬렉션을 언제 써야 할까?“를 다루는 공식 안내로, 모든 컬렉션의 속도 비교표가 있어요.
• VecDeque — 표준 라이브러리 문서 (영어): rotate_left, range, retain, as_slices까지 모든 메서드가 있어요.
• BinaryHeap — 표준 라이브러리 문서 (영어): 힙의 모든 메서드와, Reverse로 만드는 최소 힙과 peek_mut 예제가 있어요.
• Reverse — 표준 라이브러리 문서 (영어): 어떤 비교든 뒤집어 주는 작은 래퍼예요. 역순 정렬 예제도 있어요.
• 일반적인 컬렉션 — The Rust Programming Language 한국어판: 이 페이지의 컬렉션과 함께 쓰게 될 벡터, 문자열, 해시맵을 다루는 장이에요.