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

الخوارزميات وهياكل البيانات في Rust: لماذا هذا مهم

Rust هي لغة برمجة أنظمة حديثة تجمع بين أداء C++ وأمان الذاكرة الذي توفره نظام الملكية (ownership). تعلم الخوارزميات وهياكل البيانات في Rust لا يسمح فقط بإتقان المفاهيم الكلاسيكية في Computer Science، بل يساعد أيضًا على فهم أعمق للميزات الفريدة للغة: الاقتراض (borrowing)، وأوقات الحياة (lifetimes)، والتكاليف الصفرية للتجريدات (zero-cost abstractions).

في هذه المقالة، سنشرح ثلاثة هياكل بيانات أساسية (المكدس، والطابور، وشجرة البحث الثنائية) وخوارزمية كلاسيكية واحدة (الفرز السريع)، مطبقة في Rust. كل مثال مصحوب بكود وشروحات ستساعدك على الانتقال من النظرية إلى التطبيق العملي.

1. المكدس في Rust: تطبيق باستخدام Vec

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

ومع ذلك، لإظهار أمان Rust، سننشئ غلافًا مع معالجة صريحة للأخطاء:

pub struct Stack<T> {    elements: Vec<T>,}

impl<T> Stack<T> {    pub fn new() -> Self {        Stack { elements: Vec::new() }    }

    pub fn push(&mut self, item: T) {        self.elements.push(item);    }

    pub fn pop(&mut self) -> Option<T> {        self.elements.pop()    }

    pub fn peek(&self) -> Option<&T> {        self.elements.last()    }

    pub fn is_empty(&self) -> bool {        self.elements.is_empty()    }}

fn main() {    let mut stack = Stack::new();    stack.push(10);    stack.push(20);    stack.push(30);

    println!("العنصر العلوي: {:?}", stack.peek()); // Some(30)    println!("نستخرج: {:?}", stack.pop());         // Some(30)    println!("نستخرج: {:?}", stack.pop());         // Some(20)    println!("هل المكدس فارغ؟ {}", stack.is_empty());      // false}

الميزة الرئيسية لـ Rust هنا هي نظام الأنواع. إذا حاولت استخراج عنصر من مكدس فارغ، فسيجبرك المترجم على معالجة Option، مما يستبعد أخطاء إلغاء الإشارة إلى المؤشر الفارغ (null pointer dereferencing) الشائعة في C/C++.

2. الطابور: تطبيق يدوي باستخدام المخزن المؤقت الدائري

الطابور (FIFO) أكثر تعقيدًا من المكدس، لأنه يتطلب إزالة فعالة من البداية. لا توفر Rust طابورًا ثنائي الاتجاه جاهزًا بأداء مضمون، لذلك سنقوم بتنفيذ مخزن مؤقت دائري (circular buffer) بحجم ثابت.

هذا مثال ممتاز لعرض كود unsafe والمؤشرات الخام، لكننا سنبقى في المنطقة الآمنة باستخدام Vec والمؤشرات (indices):

pub struct Queue<T> {    buffer: Vec<Option<T>>,    head: usize,    tail: usize,    capacity: usize,}

impl<T> Queue<T> {    pub fn new(capacity: usize) -> Self {        let mut buffer = Vec::with_capacity(capacity);        buffer.resize_with(capacity, || None);        Queue {            buffer,            head: 0,            tail: 0,            capacity,        }    }

    pub fn enqueue(&mut self, item: T) -> Result<(), &str> {        if (self.tail + 1) % self.capacity == self.head {            return Err("الطابور ممتلئ");        }        self.buffer[self.tail] = Some(item);        self.tail = (self.tail + 1) % self.capacity;        Ok(())    }

    pub fn dequeue(&mut self) -> Option<T> {        if self.head == self.tail {            return None;        }        let item = self.buffer[self.head].take();        self.head = (self.head + 1) % self.capacity;        item    }

    pub fn is_empty(&self) -> bool {        self.head == self.tail    }}

fn main()