[Rust] VecDeque 사용법: 예제와 시간복잡도 완벽 가이드

VecDeque: 효율적인 양방향 큐를 위한 Rust의 선택

Rust의 표준 라이브러리에서 제공하는 VecDeque는 효율적인 양방향 큐(double-ended queue)를 구현하기 위한 강력한 자료구조입니다. VecDeque는 **링 버퍼(ring buffer)**를 사용해 메모리를 관리하며, 큐의 앞(front)과 뒤(back) 모두에서 요소를 추가하거나 제거하는 작업을 효율적으로 처리할 수 있도록 설계되었습니다.

---

1. VecDeque의 주요 특징

1. 양방향 삽입 및 제거:
   • push_back과 push_front를 통해 큐의 뒤와 앞에 요소를 추가할 수 있습니다.
   • pop_back과 pop_front를 사용하여 큐의 뒤와 앞에서 요소를 제거할 수 있습니다.
2. 고정된 크기 없이 동적 확장 가능:
   • 필요 시 내부 버퍼의 크기를 조정하여 더 많은 데이터를 저장할 수 있습니다.
3. 효율적인 메모리 사용:
   • 링 버퍼 구조를 활용해 메모리 재활용과 연속적인 할당 없이 요소를 관리합니다.
4. 비연속적인 메모리 관리:
   • 내부적으로 요소가 비연속적으로 배치될 수 있으나, make_contiguous 메서드를 통해 연속 메모리로 정렬할 수 있습니다.

---

2. VecDeque의 생성 방법

기본 생성

use std::collections::VecDeque;

let mut deque: VecDeque<i32> = VecDeque::new();

설명: 빈 VecDeque를 생성합니다.

초기 용량 지정

let mut deque: VecDeque<i32> = VecDeque::with_capacity(10);

설명: 초기 용량이 10인 VecDeque를 생성합니다.

배열로부터 생성

let deque: VecDeque<_> = VecDeque::from([1, 2, 3, 4]);

설명: 배열을 기반으로 VecDeque를 초기화합니다.

---

3. VecDeque의 주요 메서드

요소 추가 및 제거

• push_back(value): 뒤에 요소 추가
• push_front(value): 앞에 요소 추가
• pop_back(): 뒤에서 요소 제거
• pop_front(): 앞에서 요소 제거

예제

let mut deque = VecDeque::new();
deque.push_back(10);
deque.push_front(20);
assert_eq!(deque.pop_back(), Some(10));
assert_eq!(deque.pop_front(), Some(20));

요소 접근

• get(index): 해당 인덱스의 요소를 참조
• get_mut(index): 해당 인덱스의 요소를 변경 가능한 참조로 가져오기

예제

let mut deque = VecDeque::from([1, 2, 3]);
assert_eq!(deque.get(1), Some(&2));
if let Some(elem) = deque.get_mut(1) {
    *elem = 10;
}
assert_eq!(deque[1], 10);

크기 관리

• len(): 현재 저장된 요소의 개수 반환
• is_empty(): 큐가 비어 있는지 여부 확인
• shrink_to_fit(): 사용되지 않는 메모리를 반환하여 용량을 줄임

예제

let mut deque = VecDeque::with_capacity(10);
deque.extend(1..=5);
assert_eq!(deque.len(), 5);
deque.shrink_to_fit();

---

4. 고급 메서드

요소 회전

• rotate_left(n): 요소를 왼쪽으로 n번 회전
• rotate_right(n): 요소를 오른쪽으로 n번 회전

예제

let mut deque: VecDeque<_> = (0..5).collect();
deque.rotate_left(2);
assert_eq!(deque, [2, 3, 4, 0, 1]);

deque.rotate_right(2);
assert_eq!(deque, [0, 1, 2, 3, 4]);

범위 작업

• range(range): 지정된 범위의 요소에 접근하는 반복자를 반환
• drain(range): 지정된 범위의 요소를 제거하며 반환

예제

let mut deque: VecDeque<_> = (1..=5).collect();
let drained: VecDeque<_> = deque.drain(1..4).collect();
assert_eq!(drained, [2, 3, 4]);
assert_eq!(deque, [1, 5]);

---

5. 실제 활용 예시

작업 스케줄 관리

VecDeque는 작업을 FIFO(First-In-First-Out) 또는 LIFO(Last-In-First-Out) 방식으로 처리해야 하는 스케줄링 시스템에 적합합니다.

use std::collections::VecDeque;

struct Task {
    id: usize,
    description: String,
}

let mut task_queue = VecDeque::new();

// 작업 추가
task_queue.push_back(Task { id: 1, description: "Setup environment".to_string() });
task_queue.push_back(Task { id: 2, description: "Implement feature".to_string() });

// 작업 처리
while let Some(task) = task_queue.pop_front() {
    println!("Processing task {}: {}", task.id, task.description);
}

브라우저의 뒤로 가기/앞으로 가기

use std::collections::VecDeque;

struct BrowserHistory {
    back: VecDeque<String>,
    forward: VecDeque<String>,
}

let mut history = BrowserHistory {
    back: VecDeque::new(),
    forward: VecDeque::new(),
};

// 뒤로 가기 및 앞으로 가기 시뮬레이션
history.back.push_back("google.com".to_string());
history.back.push_back("rust-lang.org".to_string());
let current = history.back.pop_back();
history.forward.push_back(current.unwrap());

println!("Back stack: {:?}", history.back);
println!("Forward stack: {:?}", history.forward);

---

6. 시간 복잡도 표

연산 시간 복잡도

push_back	O(1)
push_front	O(1)
pop_back	O(1)
pop_front	O(1)
get(index)	O(1)~O(n)
rotate_left/rotate_right	O(min(n, len-n))
drain(range)	O(k) (k: 범위의 길이)

---

F&Q

Q1: VecDeque와 Vec의 차이점은 무엇인가요?

• Vec은 한쪽 끝에서만 요소를 추가/제거하는 데 최적화된 반면, VecDeque는 앞뒤 양쪽 끝에서 효율적으로 작업할 수 있습니다.

Q2: VecDeque는 어디에 적합한가요?

• 양쪽 끝에서 빈번하게 요소를 추가하거나 제거하는 작업이 필요한 경우 이상적입니다.

Q3: VecDeque의 성능은 어떠한가요?

• 요소 추가/제거는 O(1) 시간 복잡도를 가지며, 중간 요소 접근은 O(1)~O(n) 범위입니다.

Q4: VecDeque의 용량은 어떻게 관리되나요?

• 내부적으로 링 버퍼를 사용해 자동으로 크기를 조정하며, 필요 시 메모리를 재할당합니다.

---

결론

VecDeque는 양방향 큐 작업을 효율적으로 처리할 수 있는 Rust의 강력한 자료구조입니다. 배열과 비슷하면서도 앞뒤에서의 요소 삽입/삭제가 빈번한 상황에서 뛰어난 성능을 제공합니다. 적절히 활용하면 메모리 관리와 성능에서 큰 이점을 얻을 수 있습니다.