数据结构 | 队列、以及队列的两种实现方式

### 实现简单结构的队列

队列与栈的差异在于栈遵循“先进后出”原则,即只有单向出口,而队列更像生活中的排队结账,队首完成结账后离开队列，同时队尾又可以不断加入需要结账的人。二者都可以通过链表和数组来实现。

<center>队列示意图(来自《Hello算法》图5-4)</center>

![队列示意图](https://www.hello-algo.com/chapter_stack_and_queue/queue.assets/queue_operations.png)

### 1. 链表实现队列

将链表的尾节点看作队尾，可以不断加入新的节点,将链表的头节点看作队首，出队的时候，删除头节点，并将头节点的下一节点作为新的头节点。

<center>基于链表实现队列的入队出队操作(来自《Hello算法》)</center>

![](https://www.hello-algo.com/chapter_stack_and_queue/queue.assets/linkedlist_queue_step1.png)

代码实现：

<div class="code-toolbar"><pre class="language-rust line-numbers"><code class="language-rust">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;
        });
    }
}</code></pre></div>

### 2. 数组实现队列

数组实现队列，本质上就是“屏蔽”一些数组的特性，如数组可以从任意位置删除、插入元素，换句话说我们不实现数组的所有特性来实现队列。在Rust中数组存在size和capacity两个概念，始终满足size <= capacity，定义一个front = 0，代表数组的第一个元素下标，同时也代表队列的“队首”，那么要向队尾插入的的下标应为 （front + size） % capacity；这里通过取余计算，当front到数组尾端时，使其重新回到数组头部。

<center>基于数组实现队列的入队出队操作(来自《Hello算法》)</center>

![](https://xxzxka-1316694700.cos.ap-nanjing.myqcloud.com//typecho/array_queue_step1.png)

代码实现：

<div class="code-toolbar"><pre class="language-rust line-numbers"><code class="language-rust">/*数组实现队列*/
//数组队列结构体
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
    }
}</code></pre></div>

本文由 yuin 创作，
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名。