Có hàng đợi và bộ sưu tập ngăn xếp không?

Question

Nếu chúng ta cần các bộ sưu tập FIFO hoặc LIFO (về cơ bản là push, pop và front/back) chúng ta nên sử dụng gì trong Rust? Một cái gì đó như std::queue hoặc std::stack từ C++.

Answer 1

Trước hết, Rust không cung cấp (trong thư viện Chuẩn) bất kỳ thư viện nào có độ trễ đảm bảo cho các yếu tố thêm: Bộ sưu tập có thể phân bổ bộ nhớ khi thêm yếu tố mới và phân bổ bộ nhớ có thể mất nhiều thời gian trong trường hợp xấu nhất.

đó đang được nói, có hai ứng cử viên cho từng trường hợp:

• một chồng có thể được thực hiện hoặc trên đầu trang của Vec hoặc LinkedList (cả tính năng pop_back và push_back)
• một hàng đợi có thể được thực hiện một trong hai trên đầu trang của VecDeque hoặc LinkedList (cả tính năng pop_front và push_back)

các diff erence giữa Vec* và LinkedList là sau này là đơn giản: cho mỗi cuộc gọi đến push_back phân bổ bộ nhớ được thực hiện. Một mặt, điều này là tuyệt vời bởi vì nó có nghĩa là chi phí của push_back độc lập với số lượng các phần tử đã có trong bộ sưu tập, mặt khác ... tốt, việc cấp phát bộ nhớ có thể mất nhiều thời gian.

Điều thứ nhất là phức tạp hơn một chút:

• nó có thông tốt hơn, nhờ được nhiều hơn bộ nhớ cache thân thiện
• nó có khả năng bổ sung, đảm bảo không phân bổ push_back chừng nào có công suất dư thừa
• nó vẫn duy trì khấu hao O (1) push_back ngay cả khi không đặt công suất dư thừa trước thời hạn

Nói chung, tôi khuyên bạn nên sử dụng Vec cho một ngăn xếp và VecDeque cho một hàng đợi.

Answer 2

Cả VecDeque và LinkedList có push/pop _ front/back.