Rust의 대기열 및 스택 모음
이 글은 Rust에서 큐와 스택 모음의 존재에 관한 것입니다.
러스트 컬렉션
Rust의 표준 컬렉션 라이브러리에는 범용 프로그래밍에서 가장 자주 사용되는 데이터 구조의 효율적인 구현이 포함되어 있습니다. 결과적으로 두 라이브러리는 표준 구현을 사용하는 경우 많은 데이터 변환 없이 통신할 수 있어야 합니다.
시작하려면 Vec
을 사용해야 합니다. 이 두 컬렉션은 일반 데이터에 대한 대부분의 스토리지 및 처리 시나리오를 다룹니다.
그들은 그들이 하는 일에 뛰어납니다. 표준 라이브러리의 다른 모든 컬렉션에는 최적의 선택인 특정 사용 사례가 있지만 이러한 사용 사례는 틈새 시장에 불과합니다.
Vec
과 HashMap
이 기술적으로 좋지 않더라도 시작점으로 충분할 것입니다.
Rust에서 사용할 수 있는 컬렉션은 아래와 같이 네 가지 주요 범주로 그룹화할 수 있습니다.
- 시퀀스:
Vec
,VecDeque
,LinkedList
- 지도:
HashMap
,BTreeMap
- 세트:
HashSet
,BTreeSet
- 기타:
BinaryHeap
녹 대기열
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
위에 스택을 구현할 수 있습니다.팝 프론트
및푸시 백
을 모두 지원하므로VecDeque
또는LinkedList
위에 큐를 구현할 수 있습니다.
Vec
과 LinkedList
에는 약간의 차이가 있습니다. 후자는 더 단순합니다. push back
에 대한 각 호출에 대해 메모리가 할당됩니다.
한편으로 이것은 푸시백
비용이 컬렉션에 이미 있는 개체 수와 무관하기 때문에 유리합니다. 반면에 메모리 할당에는 시간이 오래 걸릴 수 있습니다.
전자는 다음과 같은 이유로 조금 더 복잡합니다.
- 캐시 친화적인 특성으로 인해 처리량이 더 높습니다.
- 추가 용량이 있어 초과 용량이 있는 한
푸시백
이 할당되지 않습니다. 초과 용량이 사전에 예약되지 않은 경우에도 상각된O(1)
푸시 백
을 유지합니다.
스택에는 Vec
을 사용하고 대기열에는 VecDeque
를 사용하는 것이 좋습니다.