Rust에서 큐(Queue) 자료구조 사용하기: VecDeque

Rust에서 큐(Queue) 자료구조 사용하기: VecDeque

큐(queue)는 먼저 들어온 데이터가 먼저 나가는 선입선출(First In First Out, 이하 FIFO) 자료구조입니다. 줄을 서서 기다리는 모습을 떠올리면 됩니다. 먼저 줄을 선 사람이 먼저 처리되죠. 작업 대기열, 메시지 버퍼, 너비 우선 탐색(BFS) 같은 곳에서 빠지지 않고 등장합니다.

그런데 Rust를 막 시작한 분들은 큐가 필요할 때 일단 Vec에 손이 갑니다. Vec의 끝에 push로 넣고, 앞에서 remove(0)으로 빼면 되니까요.

fn main() {
    let mut queue = vec![1, 2, 3];
    queue.push(4);
    let first = queue.remove(0); // 앞에서 제거 - O(n)
    println!("꺼낸 값: {first}, 남은 큐: {:?}", queue);
}
결과
꺼낸 값: 1, 남은 큐: [2, 3, 4]

동작은 하는데요, 문제가 하나 있습니다. Vec은 메모리에 데이터를 일렬로 붙여 저장하기 때문에 맨 앞 요소를 제거하면 뒤에 있는 모든 요소를 한 칸씩 앞으로 당겨야 합니다. 요소가 1만 개라면 하나 꺼낼 때마다 9999개를 옮기는 셈이라 O(n)이 걸리죠. 큐는 보통 앞에서 빼는 연산이 핵심인데, 그게 제일 느리다니 곤란합니다.

이럴 때 Rust 표준 라이브러리가 준비해 둔 정답이 바로 VecDeque입니다. 이번 글에서는 VecDeque로 큐를 다루는 방법을 처음부터 살펴보겠습니다.

VecDeque란?

VecDeque는 이름 그대로 벡터 기반의 덱(double-ended queue)입니다. 덱은 앞과 뒤 양쪽에서 모두 삽입과 삭제가 가능한 자료구조인데요, 양쪽 끝 연산이 모두 분할 상환(amortized) O(1)로 동작합니다. Vec처럼 앞에서 빼느라 전체를 밀어내는 일이 없습니다.

비결은 내부 구현에 있습니다. VecDeque는 링 버퍼(ring buffer) 구조를 씁니다. 연속된 메모리 블록을 원형으로 취급하면서 앞쪽과 뒤쪽을 가리키는 위치를 따로 관리합니다. 요소를 앞에서 빼더라도 데이터를 옮기는 대신 “시작 위치”만 한 칸 이동시키면 끝나기 때문에 O(1)이 나오는 것이죠.

std::collections 모듈에 들어 있으므로 먼저 가져와야 합니다.

use std::collections::VecDeque;

VecDeque 생성하기

빈 큐를 만드는 가장 기본적인 방법은 VecDeque::new()입니다. 여기에 push_back으로 뒤에서 요소를 채워 넣습니다.

use std::collections::VecDeque;

fn main() {
    let mut queue: VecDeque<i32> = VecDeque::new();
    queue.push_back(1);
    queue.push_back(2);
    queue.push_back(3);
    println!("{:?}", queue);
}
결과
[1, 2, 3]

이미 가지고 있는 배열이나 벡터로부터 만들고 싶다면 VecDeque::from이 편합니다.

use std::collections::VecDeque;

fn main() {
    let queue = VecDeque::from([10, 20, 30]);
    println!("{:?}", queue);
}
결과
[10, 20, 30]

담을 개수를 미리 알고 있다면 VecDeque::with_capacity(n)으로 용량을 확보해 두는 것이 좋습니다. 요소가 늘어나 버퍼가 가득 차면 더 큰 메모리를 새로 할당하고 복사하는 비용이 드는데, 미리 공간을 잡아두면 이 재할당을 줄일 수 있습니다.

큐로 사용하기 (FIFO)

큐의 핵심은 뒤에서 넣고 앞에서 빼는 것입니다. push_back으로 넣고 pop_front로 뺍니다.

use std::collections::VecDeque;

fn main() {
    let mut queue = VecDeque::from([1, 2, 3]);

    while let Some(x) = queue.pop_front() {
        println!("처리: {x}");
    }
    println!("비었나? {}", queue.is_empty());
}
결과
처리: 1
처리: 2
처리: 3
비었나? true

여기서 눈여겨볼 부분은 pop_front의 반환 타입입니다. 큐가 비어 있으면 꺼낼 값이 없으므로, 값이 있을 때는 Some(x)를, 없을 때는 None을 돌려주는 Option 타입을 반환합니다. 그래서 while let Some(x) = queue.pop_front() 패턴이 자연스럽게 어울립니다. 큐가 빌 때까지 꺼내다가 None이 나오면 반복문이 종료되죠.

양쪽 끝에서 다루기

VecDeque는 덱이기 때문에 앞쪽도 자유롭게 조작할 수 있습니다. push_front로 앞에 넣고, pop_back으로 뒤에서 뺄 수 있죠. 이 네 가지 메서드를 조합하면 큐든 스택이든 원하는 대로 쓸 수 있습니다.

use std::collections::VecDeque;

fn main() {
    let mut q = VecDeque::from([10, 20, 30]);

    q.push_front(5); // 앞에 추가
    q.push_back(40); // 뒤에 추가
    println!("{:?}", q);

    println!("pop_back={:?}", q.pop_back());   // 뒤에서 제거
    println!("pop_front={:?}", q.pop_front()); // 앞에서 제거
    println!("{:?}", q);
}
결과
[5, 10, 20, 30, 40]
pop_back=Some(40)
pop_front=Some(5)
[10, 20, 30]

제거하지 않고 양 끝의 값을 들여다보기만 하려면 front와 back을 씁니다. 다른 언어에서 큐의 peek에 해당하는 동작인데요, 이 역시 비어 있을 수 있으니 Option을 반환합니다.

use std::collections::VecDeque;

fn main() {
    let q = VecDeque::from([10, 20, 30]);
    println!("front={:?}, back={:?}", q.front(), q.back());
}
결과
front=Some(10), back=Some(30)

순회하기

VecDeque도 다른 컬렉션처럼 iter로 순회할 수 있습니다. 순서는 앞(front)에서 뒤(back) 방향입니다. 이터레이터를 반환하므로 sum, map, filter 같은 어댑터를 그대로 이어 붙일 수 있고요.

use std::collections::VecDeque;

fn main() {
    let q = VecDeque::from([1, 2, 3, 4]);

    let sum: i32 = q.iter().sum();
    println!("합계: {sum}");

    for (i, v) in q.iter().enumerate() {
        println!("  [{i}] = {v}");
    }
}
결과
합계: 10
  [0] = 1
  [1] = 2
  [2] = 3
  [3] = 4

실전 예제: 너비 우선 탐색

큐가 가장 빛을 발하는 곳이 바로 너비 우선 탐색(Breadth First Search, 이하 BFS)입니다. BFS는 시작 노드에서 가까운 노드부터 차례대로 방문하는 그래프 탐색 알고리즘인데요, “다음에 방문할 노드”를 큐에 넣어두고 앞에서부터 꺼내 처리하는 방식이라 VecDeque가 딱 맞습니다.

아래는 인접 리스트로 표현한 그래프를 BFS로 탐색하는 예제입니다. 방문 여부는 HashMap과 짝을 이루는 HashSet으로 관리했습니다.

use std::collections::{HashMap, HashSet, VecDeque};

fn bfs(graph: &HashMap<&str, Vec<&str>>, start: &str) -> Vec<String> {
    let mut visited = HashSet::new();
    let mut order = Vec::new();
    let mut queue = VecDeque::new();

    queue.push_back(start);
    visited.insert(start);

    while let Some(node) = queue.pop_front() {
        order.push(node.to_string());
        if let Some(neighbors) = graph.get(node) {
            for &next in neighbors {
                // insert가 false면 이미 방문한 노드
                if visited.insert(next) {
                    queue.push_back(next);
                }
            }
        }
    }
    order
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert("A", vec!["B", "C"]);
    graph.insert("B", vec!["A", "D", "E"]);
    graph.insert("C", vec!["A", "F"]);
    graph.insert("D", vec!["B"]);
    graph.insert("E", vec!["B", "F"]);
    graph.insert("F", vec!["C", "E"]);

    let order = bfs(&graph, "A");
    println!("방문 순서: {}", order.join(" -> "));
}
결과
방문 순서: A -> B -> C -> D -> E -> F

여기서 작은 Rust 관용구를 하나 짚고 넘어가겠습니다. HashSet의 insert는 값이 새로 추가됐으면 true, 이미 존재했으면 false를 반환합니다. 그래서 if visited.insert(next) 한 줄로 “아직 방문 안 했으면 방문 표시하고 큐에 넣기”를 동시에 처리할 수 있습니다. 방문 체크와 마킹을 따로 쓰지 않아도 되니 코드가 한결 깔끔해지죠.

슬라이딩 윈도우로 활용하기

양 끝 연산이 모두 빠르다는 특성 덕분에, 최근 N개의 데이터만 유지하는 슬라이딩 윈도우(sliding window)를 구현할 때도 VecDeque가 유용합니다. 새 값이 들어올 때 윈도우가 꽉 찼으면 가장 오래된 앞쪽 값을 빼고 뒤에 새 값을 넣으면 됩니다.

use std::collections::VecDeque;

fn main() {
    let mut window: VecDeque<i32> = VecDeque::with_capacity(3);

    for x in 1..=6 {
        if window.len() == 3 {
            window.pop_front(); // 가장 오래된 값 제거
        }
        window.push_back(x);
        println!("{:?}", window);
    }
}
결과
[1]
[1, 2]
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]
[4, 5, 6]

최근 측정값의 이동 평균을 구하거나, 최근 이벤트 로그만 유지하는 상황에서 이 패턴이 그대로 쓰입니다.

스레드 사이에서 큐가 필요하다면

여기서 한 가지 짚어둘 점이 있습니다. VecDeque는 단일 스레드용 자료구조입니다. 여러 스레드가 동시에 같은 VecDeque에 접근하려면 Mutex 같은 동기화 장치로 직접 감싸줘야 하죠.

하지만 한 스레드가 데이터를 만들어 보내고 다른 스레드가 받아 처리하는 생산자-소비자 패턴이라면, 표준 라이브러리의 채널(std::sync::mpsc)이 더 자연스럽습니다. 채널은 그 자체가 스레드 안전한 큐처럼 동작합니다.

use std::sync::mpsc;
use std::thread;

fn main() {
    let (tx, rx) = mpsc::channel();

    let producer = thread::spawn(move || {
        for i in 1..=3 {
            tx.send(i).unwrap();
        }
    });

    producer.join().unwrap();

    // 채널이 닫힐 때까지 받은 순서대로 처리 (FIFO)
    for received in rx {
        println!("받음: {received}");
    }
}
결과
받음: 1
받음: 2
받음: 3

mpsc는 multiple producer, single consumer의 약자로, 여러 생산자가 하나의 소비자에게 메시지를 보내는 구조를 의미합니다. 보낸 순서대로 받게 되니 FIFO 큐의 성질을 그대로 가지고 있죠.

한편 들어온 순서가 아니라 우선순위가 높은 데이터부터 꺼내고 싶다면 큐 대신 힙이 필요합니다. Rust 표준 라이브러리는 이를 위해 BinaryHeap을 제공합니다.

마치며

지금까지 Rust에서 큐를 다루는 표준 방법인 VecDeque를 살펴봤습니다. Vec으로 큐를 흉내 내면 앞에서 빼는 연산이 O(n)이라 비효율적이지만, 링 버퍼 기반의 VecDeque는 양 끝 연산이 모두 O(1)이라는 점이 핵심이었습니다. push_back과 pop_front로 FIFO 큐를, push_front와 pop_back까지 더하면 덱을 자유롭게 구현할 수 있고요.

큐가 필요한 상황을 만나면 일단 Vec에 remove(0)을 쓰던 습관 대신 VecDeque를 떠올려 보세요. 스레드 사이에서 데이터를 주고받아야 한다면 채널을, 우선순위가 중요하다면 BinaryHeap을 고려하면 됩니다.

더 자세한 메서드 목록과 동작은 VecDeque 공식 문서를 참고하세요.

This work is licensed under CC BY 4.0 CC BY

개발자를 위한 뉴스레터

달레가 정리한 AI 개발 트렌드와 직접 만든 콘텐츠를 전해드립니다.

관련 포스트

Rust 기초: Vec으로 동적 배열 다루기

Rust에서 배열([T; N])은 크기가 컴파일 시점에 고정됩니다. [i32; 5]라고 선언하면 딱 5개만 담을 수 있고, 나중에 6번째 요소를 추가할 수가 없죠. 사용자 입력을 모으거나 파일에서 데이터를 읽어오거나 API 응답을 파싱하는 상황처럼 실행 시점에 데이터 개수가 정해지는 경우에는 고정 크기 배열로 해결이 안 됩니다. 이럴 때 필요한 것이 Vec<T>입니다. Vec<T>는 힙에 데이터를 저장하는 동적 배열로, 요소를 자유롭게 추가하고 제거할 수 있습니다. Rust에서 가장 많이 쓰이는 컬렉션 타입이기도 하고요. 이 글에서

Rust 기초: HashMap으로 키-값 데이터 다루기

전화번호부를 떠올려보세요. 이름을 알면 전화번호를 바로 찾을 수 있죠. 프로그래밍에서도 이런 식으로 어떤 키를 가지고 그에 대응하는 값을 빠르게 찾고 싶을 때가 많습니다. 다른 언어에서는 딕셔너리(dictionary)나 맵(map)이라고 부르는 이 자료 구조를 Rust에서는 HashMap이라고 합니다. 이 글에서는 HashMap을 생성하고, 데이터를 넣고 꺼내고, 수정하고 삭제하는 기본 연산부터 Entry API와 소유권 이슈까지 정리해보겠습니다. HashMap 생성 HashMap은 표준 라이브러리의 std::collections

파이썬에서 큐(queue) 자료구조 사용하기

큐(queue)는 선입선출, FIFO(First In First Out) 기반의 매우 유명한 자료구조입니다. 큐를 사용하면 데이터를 추가한 순서대로 제거할 수 있기 때문에 비동기 메세징(asynchronous messaging), 스트리밍(streaming), 너비 우선 탐색(breath first search) 등 소프트웨어 개발에서 널리 응용되고 있습니다. 이번 포스팅에서는 파이썬에서 큐 자료구조를 어떻게 사용할 수 있는지 알아보도록 하겠습니다. list 파이썬에서 큐를 사용하는 가장 간단한 방법은 범용 자료구조인 list를 사

Rust tokio::sync: 채널과 동기화 도구 고르기

Tokio로 비동기 코드를 짜다 보면 생각보다 빨리 tokio::sync를 만나게 됩니다. 태스크 하나가 다른 태스크에게 일을 넘겨야 하고, 결과를 돌려받아야 하고, 여러 태스크에 종료 신호를 보내야 하고, 공유 상태를 잠가야 하니까요. 문제는 선택지가 꽤 많다는 점입니다. mpsc, oneshot, broadcast, watch, Mutex, RwLock, Semaphore, Notify가 한 모듈 안에 같이 있는데, 이름만 봐서는 언제 무엇을 써야 할지 헷갈립니다. mpsc로도 종료 신호를 보낼 수 있고, watch로도 보낼 수