Rust의 대기열 및 스택 모음

Nilesh Katuwal 2023년6월21일

Rust Rust Stack

이 글은 Rust에서 큐와 스택 모음의 존재에 관한 것입니다.

러스트 컬렉션

Rust의 표준 컬렉션 라이브러리에는 범용 프로그래밍에서 가장 자주 사용되는 데이터 구조의 효율적인 구현이 포함되어 있습니다. 결과적으로 두 라이브러리는 표준 구현을 사용하는 경우 많은 데이터 변환 없이 통신할 수 있어야 합니다.

시작하려면 Vec을 사용해야 합니다. 이 두 컬렉션은 일반 데이터에 대한 대부분의 스토리지 및 처리 시나리오를 다룹니다.

그들은 그들이 하는 일에 뛰어납니다. 표준 라이브러리의 다른 모든 컬렉션에는 최적의 선택인 특정 사용 사례가 있지만 이러한 사용 사례는 틈새 시장에 불과합니다.

Vec과 HashMap이 기술적으로 좋지 않더라도 시작점으로 충분할 것입니다.

Rust에서 사용할 수 있는 컬렉션은 아래와 같이 네 가지 주요 범주로 그룹화할 수 있습니다.

Rust의 큐 데이터 구조는 요소를 저장하는 데 사용됩니다. Rust의 대기열은 선입 선출을 의미하는 FIO 방식으로 작동합니다.

이것은 Rust 컬렉션 라이브러리에 포함된 표준 대기열입니다. 선형 데이터 구조입니다.

대기열을 조작하는 데 사용할 수 있는 여러 작업을 제공합니다. 여러 요소를 포함할 수 있습니다. 전체 구현은 Rust의 벡터 데이터 구조를 기반으로 합니다.

통사론:

let mut variable_name : Queue<queue_size> = queue![];

스택은 추가 및 제거할 수 있는 항목 모음이지만 다음 순서로만 가능합니다. 후입선출(LIFO). 예를 들어, 과밀 열차에 탑승한 경우 다른 승객도 하차할 수 있도록 가장 먼저 하차해야 합니다.

객체를 추가하는 것은 일반적으로 푸시라고 하며 상품을 제거하는 것은 일반적으로 팝이라고 합니다. 이러한 기능은 Vec(벡터) 데이터 구조를 사용하여 Rust에서 구현되기 때문입니다.

새 스택을 생성하려면 다음 구문을 사용할 수 있습니다.

let s = Stack { stack: Vec::new() };

Rust’는 표준 라이브러리에 요소를 추가하기 위해 대기 시간이 보장된 라이브러리를 제공하지 않습니다. Rust 컬렉션에 추가 요소를 추가할 때 메모리가 할당될 수 있습니다.

최악의 시나리오에서는 메모리 할당에 무한한 시간이 걸릴 수 있습니다.

각각의 경우에 두 가지 후보가 있습니다.

Vec과 LinkedList에는 약간의 차이가 있습니다. 후자는 더 단순합니다. push back에 대한 각 호출에 대해 메모리가 할당됩니다.

한편으로 이것은 푸시백 비용이 컬렉션에 이미 있는 개체 수와 무관하기 때문에 유리합니다. 반면에 메모리 할당에는 시간이 오래 걸릴 수 있습니다.

전자는 다음과 같은 이유로 조금 더 복잡합니다.

캐시 친화적인 특성으로 인해 처리량이 더 높습니다.
추가 용량이 있어 초과 용량이 있는 한 푸시백이 할당되지 않습니다. 초과 용량이 사전에 예약되지 않은 경우에도 상각된 O(1) 푸시 백을 유지합니다.

스택에는 Vec을 사용하고 대기열에는 VecDeque를 사용하는 것이 좋습니다.