Rust基础(11)-基本数据结构

队列 栈等数据结构的实现

1. 队列

#[derive(Debug)]
struct Queue<T> {
    qdata: Vec<T>,
    capacity: usize,
}

impl<T> Queue<T> {
    fn new(size: usize) -> Self {
        Queue {
            qdata: Vec::with_capacity(size),
            capacity: size,
        }
    }
    fn enqueue(&mut self, item: T) -> Result<(), String> {
        if self.qdata.len() == self.capacity {
            return Err("No space in queue!".to_string());
        }
        self.qdata.push(item);
        Ok(())
    }
    fn dequeue(&mut self) -> Option<T> {
        let size = self.qdata.len();
        if size > 0 {
            let v = self.qdata.remove(0);
            Some(v)
        } else {
            None
        }
    }

    fn size(&self) -> usize {
        self.qdata.len()
    }
}

fn main() {
    let mut q = Queue::new(2);
    q.enqueue(1);
    q.enqueue(2);

    if let Err(error) = q.enqueue(3) {
        println!("enqueue error: {}", error)
    }

    println!("size:{}", q.size());
    println!("q: {:#?}", q);

    for _ in 0..3 {
        if let Some(data) = q.dequeue() {
            println!("data: {}", data);
        } else {
            println!("queue empty!");
        }
    }
}

2. 栈（vector实现）

#[derive(Debug)]
struct Stack<T> {
    data: Vec<T>,
    top: usize,
    capacity: usize,
}

impl<T> Stack<T> {
    fn new(size: usize) -> Self {
        Stack {
            data: Vec::new(),
            top: 0,
            capacity: size,
        }
    }

    fn push(&mut self, item: T) -> Result<(), String> {
        if self.top >= self.capacity {
            return Err(String::from("There is no space in stack!"));
        }
        self.data.push(item);
        self.top += 1;
        Ok(())
    }
    fn pop(&mut self) -> Option<T> {
        if self.top == 0 {
            return None;
        }
        self.top -= 1;
        self.data.pop()
    }
    fn top(&self) -> usize {
        self.top
    }
}

fn main() {
    let mut s = Stack::new(3);
    let _ = s.push(1);
    let _ = s.push(2);
    let _ = s.push(3);

    if let Err(error) = s.push(4) {
        println!("push 4 error:{}", error);
    }

    println!("++++++++++++++++");
    println!("top: {}",s.top());
    println!("s: {:#?}", s);
    for _ in 0..4 {
        let a = s.pop();
        match a {
            Some(item) => println!("pop item:{}", item),
            None => println!("stack empty!"),
        }
    }
}

3. 栈（链表实现）

#[derive(Debug)]
struct StackNode<T> {
    data: T,
    next: Option<Box<StackNode<T>>>, //使用Option，可以用它的None;智能指针指向下一个节点
}

#[derive(Debug)]
struct Stack<T> {
    top: Option<Box<StackNode<T>>>,
}

impl<T> Stack<T> {
    fn new() -> Stack<T> {
        Stack { top: None }
    }

    fn push(&mut self, data: T) {
        let mut node = StackNode { data, next: None };
        let next = self.top.take();
        node.next = next;
        self.top = Some(Box::new(node));
    }

    fn pop(&mut self) -> Option<T> {
        let node = self.top.take();
        match node {
            None => None,
            Some(mut x) => {
                self.top = x.next.take();
                Some(x.data)
            }
        }
    }
}


fn main() {
    let mut s = Stack::new();
    s.push(1);
    s.push(2);
    s.push(3);
    println!("after push, s:{:#?}", s);

    for _ in 0..4{
        if let Some(data)=s.pop(){
            println!("data:{}",data)
        }else{
            println!("empty");
        }
    }
}

总结

本文编辑完毕