الخوارزميات وهياكل البيانات بلغة Rust: دليل عملي

مقدمة: لماذا Rust مثالية للخوارزميات وهياكل البيانات

تجمع Rust بين أداء C/C++ وأمان الذاكرة، مما يجعلها خيارًا ممتازًا لتنفيذ الخوارزميات وهياكل البيانات. بفضل نظام الملكية (ownership) والاقتراض (borrowing)، يمكنك إنشاء هياكل فعالة وآمنة دون وجود جامع للقمامة. في هذه المقالة، سنقوم بتحليل التنفيذ العملي لهياكل البيانات والخوارزميات الرئيسية بلغة Rust - من المكدس إلى الشجرة الثنائية واجتياز الرسم البياني.

سنستخدم فقط المكتبة القياسية لـ Rust، حتى تتمكن من تطبيق الكود فورًا في مشاريعك. جميع الأمثلة يتم تجميعها وتعمل مع إصدار Rust 2021.

1. المكدس وقائمة الانتظار: الهياكل الكلاسيكية في Rust

المكدس (Stack)

يعمل المكدس وفقًا لمبدأ LIFO (Last In, First Out). في Rust، أسهل طريقة لتنفيذ المكدس هي باستخدام Vec:

struct Stack<T> {\n    elements: Vec<T>,\n}\n\nimpl<T> Stack<T> {\n    fn new() -> Self {\n        Stack { elements: Vec::new() }\n    }\n\n    fn push(&mut self, value: T) {\n        self.elements.push(value);\n    }\n\n    fn pop(&mut self) -> Option<T> {\n        self.elements.pop()\n    }\n\n    fn peek(&self) -> Option<&T> {\n        self.elements.last()\n    }\n\n    fn is_empty(&self) -> bool {\n        self.elements.is_empty()\n    }\n}\n\nfn main() {\n    let mut stack = Stack::new();\n    stack.push(10);\n    stack.push(20);\n    stack.push(30);\n    \n    println!("العنصر العلوي: {:?}", stack.peek()); // Some(30)\n    println!("نقوم بالإخراج: {:?}", stack.pop()); // Some(30)\n    println!("هل المكدس فارغ؟ {}", stack.is_empty()); // false\n}

الميزة: Vec يوفر بالفعل تعقيدًا زمنيًا متوسطًا O(1) لعمليات push/pop، وتضمن Rust تحرير الذاكرة عند الخروج من النطاق.

قائمة الانتظار (Queue)

تعمل قائمة الانتظار وفقًا لمبدأ FIFO (First In, First Out). للتنفيذ الفعال، نستخدم VecDeque من المكتبة القياسية:

use std::collections::VecDeque;\n\nstruct Queue<T> {\n    elements: VecDeque<T>,\n}\n\nimpl<T> Queue<T> {\n    fn new() -> Self {\n        Queue { elements: VecDeque::new() }\n    }\n\n    fn enqueue(&mut self, value: T) {\n        self.elements.push_back(value);\n    }\n\n    fn dequeue(&mut self) -> Option<T> {\n        self.elements.pop_front()\n    }\n\n    fn front(&self) -> Option<&T> {\n        self.elements.front()\n    }\n\n    fn len(&self) -> usize {\n        self.elements.len()\n    }\n}\n\nfn main() {\n    let mut queue = Queue::new();\n    queue.enqueue("الأول");\n    queue.enqueue("الثاني");\n    queue.enqueue("الثالث");\n\n    println!("الأول في قائمة الانتظار: {:?}", queue.front()); // Some("الأول")\n    println!("نقوم بالخدمة: {:?}", queue.dequeue()); // Some("الأول")\n    println!("طول قائمة الانتظار: {}", queue.len()); // 2\n}

هام: يستخدم VecDeque مخزنًا دائريًا، مما يعطي تعقيدًا زمنيًا O(1) للإدراج والحذف من كلا الطرفين. هذا أسرع بكثير من استخدام Vec لقائمة الانتظار.

2. شجرة البحث الثنائية (BST) في Rust

شجرة البحث الثنائية هي واحدة من هياكل البيانات الأساسية. سنقوم بتنفيذها باستخدام Box للأنواع العودية:

use std::cmp::Ordering;\n\n#[derive(Debug)]\nstruct Node<T: Ord> {\n    value: T,\n    left: Option<Box<Node<T>>>,\n    right: Option<Box<Node<T>>>,\n}\n\n#[derive(Debug)]\nstruct BinarySearchTree<T: Ord> {\n    root: Option<Box<Node<T>>>,\n}\n\nimpl<T: Ord> BinarySearchTree<T> {\n    fn new() -> Self {\n        BinarySearchTree { root: None }\n    }\n\n    fn insert(&mut self, value: T) {\n        let mut current = &mut se