实现简单结构的队列
队列与栈的差异在于栈遵循“先进后出”原则,即只有单向出口,而队列更像生活中的排队结账,队首完成结账后离开队列,同时队尾又可以不断加入需要结账的人。二者都可以通过链表和数组来实现。
1. 链表实现队列
将链表的尾节点看作队尾,可以不断加入新的节点,将链表的头节点看作队首,出队的时候,删除头节点,并将头节点的下一节点作为新的头节点。
代码实现:
use std::rc::Rc;
use std::cell::RefCell;
/*链表结构体*/
#[derive(Debug,Clone)]
#[warn(dead_code)]
pub struct ListNode{
value:i32,
next:Option<Rc<RefCell<ListNode>>>
}
impl ListNode{
pub fn new(num:i32)->Self{
Self{
value:num,
next:None
}
}
}
#[derive(Debug)]
pub struct Queue{
peek:Option<Rc<RefCell<ListNode>>>,//头节点
end:Option<Rc<RefCell<ListNode>>>,//尾节点
q_size:usize //队列长度
}
impl Queue{
//初始化队列
pub fn new()-> Self{
Self{
peek:None,
end:None,
q_size:0
}
}
//获取头节点
pub fn peek(&self)->Option<&Rc<RefCell<ListNode>>>{
self.peek.as_ref()
}
//获取队列长度
pub fn size(&self)->usize{
self.q_size
}
//判断队列是否为空
pub fn is_empty(&self)->bool{
self.size() == 0
}
//入队
pub fn push(&mut self,num:i32){
//根据传入的入队元素,初始化该入列节点为Option<Rc<RefCell<LisstNode>>>
let new_end = Some(Rc::new(RefCell::new(ListNode::new(num))));
//匹配当前队列的尾节点
match self.end.take() {
// 如果队列不为空,就把老节点的指针指向传入的节点
Some(old_end)=>{
old_end.borrow_mut().next = new_end.clone();
self.end = new_end;
}
// 如果队列为空,则令头、尾节点都指向该节点
None=>{
self.peek = new_end.clone();
self.end = new_end
}
}
//队列长度加一
self.q_size += 1
}
//出队
pub fn pop(&mut self){
//从当前队列头节点开始遍历
self.peek.take().map(|cur_peek|{
//获取头节点的下一个节点
match cur_peek.borrow_mut().next.take() {
//如果不为空,就让头节点的下一个节点作为新的节点
Some(new_preek)=>{
self.peek = Some(new_preek)
}
None=>{
self.end.take();
}
}
//队列长度减一
self.q_size -= 1;
Rc::try_unwrap(cur_peek).ok().unwrap().into_inner().value;
});
}
}
2. 数组实现队列
数组实现队列,本质上就是“屏蔽”一些数组的特性,如数组可以从任意位置删除、插入元素,换句话说我们不实现数组的所有特性来实现队列。在Rust中数组存在size和capacity两个概念,始终满足size <= capacity,定义一个front = 0,代表数组的第一个元素下标,同时也代表队列的“队首”,那么要向队尾插入的的下标应为 (front + size) % capacity;这里通过取余计算,当front到数组尾端时,使其重新回到数组头部。
代码实现:
/*数组实现队列*/
//数组队列结构体
pub struct ArrayQueue{
nums:Vec<i32>, //存储队列元素的数组
front:i32, //队首指针
q_size:i32, //队列长度
q_capacity:i32 //队列容量
}
impl ArrayQueue{
pub fn new(capacity:i32)-> ArrayQueue{
ArrayQueue{
nums:vec![0;capacity as usize],
front:0,
q_size:0,
q_capacity:capacity,
}
}
//获取队列的容量
pub fn capacity(&self) -> i32{
self.q_capacity
}
//获取队列的长度
pub fn size(&self) -> i32{
self.q_size
}
//判断队列长度是否为0
pub fn is_empty(&self) -> bool{
self.size() == 0
}
//获取队首元素
pub fn peek(&self) -> i32{
if self.is_empty(){
println!("队列为空")
}
self.nums[self.front as usize]
}
//入队
pub fn push(&mut self,num:i32) {
if self.capacity() == self.q_size {
println!("队列已满");
return;
}
// 计算队尾指针,指向队尾索引 + 1
// 通过取余操作实现 rear 越过数组尾部后回到头部
let end = (self.front + self.q_size) % self.q_capacity;
self.nums[end as usize] = num;
self.q_size += 1
}
//出队
pub fn pop(&mut self) -> i32{
let peek = self.peek();
//队首指针向后移动1
self.front = (self.front + 1) % self.q_capacity;
self.q_size -= 1;
peek
}
}
本文由 yuin 创作,
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名。