Rust队列和栈

2023-09-21 07:12| 来源: 网络整理| 查看: 265

前言

Rust 标准库里面是有 Vec这种可以在堆上分配内存的连续可增长的数组类型。可以用它很方便的实现队列和栈，但是他只能增长不能收缩。所以接下来使用链表实现队列

结点的结构 #[derive(Debug)] struct Node { data: T, next: Option, } impl Node { fn new(data: T) -> Self { Node { data, next: None } } fn get_last_node(&mut self) -> &mut Self { if let Some(ref mut node) = self.next { return node.get_last_node(); } self } } 队列实现

采用尾插法插入结点，最后在弹出头结点。这样就实现先进先出（FIFO）

#[derive(Debug)] struct Queue { data: Option, length: usize, } impl Queue { fn new() -> Self { Queue { data: None, length: 0, } } fn push(&mut self, data: T) { // push end if let Some(ref mut head) = self.data { let mut last_node = head.get_last_node(); last_node.next = Some(Box::new(Node::new(data))); } else { self.data = Some(Box::new(Node::new(data))); } self.length += 1 } fn pop(&mut self) -> Option { if let Some(ref mut head) = self.data { self.length -= 1; let data = head.data; self.data = head.next.take(); return Some(data); } None } fn length(&self) -> usize { self.length } } 栈实现

采用头插法插入结点，最后在弹出头结点。这样就实现先进后出（FIFO）

#[derive(Debug)] struct Stack { data: Option, length: usize, } impl Stack { fn new() -> Self { Stack { data: None, length: 0, } } fn push(&mut self, data: T) { let mut new_node = Node::new(data); // push head if self.data.is_some() { let head = self.data.take(); new_node.next = head; self.data = Some(Box::new(new_node)); } else { self.data = Some(Box::new(new_node)); } self.length += 1 } fn pop(&mut self) -> Option { if let Some(ref mut head) = self.data { self.length -= 1; let data = head.data; self.data = head.next.take(); return Some(data); } None } fn length(&self) -> usize { self.length } }

队列代码地址

栈代码地址

【本文地址】

Rust队列和栈

Rust队列和栈

今日新闻

推荐新闻