队列

队列简介

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

在队列的形成过程中，可以利用线性链表的原理，来生成一个队列。基于链表的队列，要动态创建和删除节点，效率较低，但是可以动态增长。队列采用的 FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部，而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。所谓的动态创建，动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成，遍历也方便。

队列实现

下面看一下我们使用 Vec 来实现的简单 Queue：

主要实现的new( ), push( ), pop( )三个方法

  1. #[derive(Debug)]
  2. struct Queue<T> {
  3.     qdata: Vec<T>,
  4. }
  6. impl <T> Queue<T> {
  7.     fn new() -> Self {
  8.         Queue{qdata: Vec::new()}
  9.     }
  11.     fn push(&mut self, item:T) {
  12.         self.qdata.push(item);
  13.     }
  15.     fn pop(&mut self) -> T{
  16.         self.qdata.remove(0)
  17.     }
  18. }
  20. fn main() {
  21.     let mut q = Queue::new();
  22.     q.push(1);
  23.     q.push(2);
  24.     println!("{:?}", q);
  25.     q.pop();
  26.     println!("{:?}", q);
  27.     q.pop();
  28. }

练习

看起来比我们在上一节实现的Stack简单多了。不过这个Queue实现是有Bug的。

练习：在这个代码的上找到 Bug，并修改。

提示：pop( )方法有 Bug，请参考 Stack 小节的实现，利用 Option 来处理。