前言
Rust 标准库里面是有 Vec这种可以在堆上分配内存的连续可增长的数组类型。可以用它很方便的实现队列和栈，但是他只能增长不能收缩。所以接下来使用链表实现队列
结点的结构
#[derive(Debug)]
struct Node<T> {
data: T,
next: Option<Box<Node<T>>>,
}
impl<T> Node<T> {
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<T> {
data: Option<Box<Node<T>>>,
length: usize,
}
impl<T:Copy> Queue<T> {
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<T> {
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<T> {
data: Option<Box<Node<T>>>,
length: usize,
}
impl<T: Copy> Stack<T> {
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<T> {
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
}
}
