数据结构 | 队列、以及队列的两种实现方式 Nov 11 2024 笔记 0 comment ### 实现简单结构的队列 队列与栈的差异在于栈遵循“先进后出”原则,即只有单向出口,而队列更像生活中的排队结账,队首完成结账后离开队列,同时队尾又可以不断加入需要结账的人。二者都可以通过链表和数组来实现。 队列示意图(来自《Hello算法》图5-4)  ### 1. 链表实现队列 将链表的尾节点看作队尾,可以不断加入新的节点,将链表的头节点看作队首,出队的时候,删除头节点,并将头节点的下一节点作为新的头节点。 基于链表实现队列的入队出队操作(来自《Hello算法》)  代码实现: 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到数组尾端时,使其重新回到数组头部。 基于数组实现队列的入队出队操作(来自《Hello算法》)  代码实现: /*数组实现队列*/ //数组队列结构体 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 创作,本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名。