循环队列(Circular Queue)

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

Properties

  • de_queue O(1)
  • en_queue O(1)
  1. use std::{
  2.     alloc::{self, Layout},
  3.     ptr,
  4. };
  6. pub struct CircularQueue<T> {
  7.     write_index: usize,
  8.     read_index: usize,
  9.     cap: usize,
  10.     len: usize,
  11.     data: Box<[T]>,
  12. }
  14. impl<T> CircularQueue<T> {
  15.     pub fn new(cap: usize) -> Self {
  16.         let data = unsafe {
  17.             let data_ptr = alloc::alloc(Layout::array::<T>(cap).unwrap()) as *mut T;
  18.             Box::from_raw(ptr::slice_from_raw_parts_mut(data_ptr, cap))
  19.         };
  20.         Self {
  21.             write_index: 0,
  22.             read_index: 0,
  23.             cap,
  24.             len: 0,
  25.             data,
  26.         }
  27.     }
  29.     /**
  30.      * add value to CircularQueue
  31.      * return true if success, false if queue is full
  32.      */
  33.     pub fn en_queue(&mut self, value: T) -> bool {
  34.         if self.is_full() {
  35.             false
  36.         } else {
  37.             self.data[self.write_index] = value;
  38.             self.write_index = (self.write_index + 1) % self.cap;
  39.             self.len += 1;
  40.             true
  41.         }
  42.     }
  44.     /**
  45.      * remove value from CircularQueue
  46.      * return true if success, false if queue is full
  47.      */
  48.     pub fn de_queue(&mut self) -> bool {
  49.         if self.is_empty() {
  50.             false
  51.         } else {
  52.             self.read_index = (self.read_index + 1) % self.cap;
  53.             self.len -= 1;
  54.             true
  55.         }
  56.     }
  58.     /**
  59.      * get front value
  60.      */
  61.     pub fn front(&self) -> Option<&T> {
  62.         if self.is_empty() {
  63.             None
  64.         } else {
  65.             Some(&self.data[self.read_index])
  66.         }
  67.     }
  69.     /**
  70.      * get tail value
  71.      */
  72.     pub fn rear(&self) -> Option<&T> {
  73.         if self.is_empty() {
  74.             None
  75.         } else if self.write_index == 0 {
  76.             Some(&self.data[self.cap - 1])
  77.         } else {
  78.             Some(&self.data[self.write_index - 1])
  79.         }
  80.     }
  82.     pub fn is_empty(&self) -> bool {
  83.         self.len == 0
  84.     }
  86.     pub fn is_full(&self) -> bool {
  87.         self.cap == self.len
  88.     }
  89. }
  91. #[cfg(test)]
  92. mod tests {
  93.     use std::result;
  95.     use super::*;
  97.     #[test]
  98.     fn test_en_queue() {
  99.         let mut circular_queue = CircularQueue::new(100);
  100.         for i in 0..100 {
  101.             let result = circular_queue.en_queue(i);
  102.             assert!(result);
  103.         }
  104.         let result = circular_queue.en_queue(100);
  105.         assert!(!result);
  106.     }
  108.     #[test]
  109.     fn test_de_queue() {
  110.         let mut circular_queue = CircularQueue::new(100);
  111.         for i in 0..200 {
  112.             circular_queue.en_queue(i);
  113.         }
  115.         for _ in 0..100 {
  116.             let result = circular_queue.de_queue();
  117.             assert!(result);
  118.         }
  120.         let result = circular_queue.de_queue();
  121.         assert!(!result);
  122.     }
  124.     #[test]
  125.     fn test_circular_queue_order() {
  126.         let mut circular_queue = CircularQueue::new(3);
  128.         for i in 1..4 {
  129.             circular_queue.en_queue(i);
  130.         }
  132.         circular_queue.en_queue(4);
  134.         let result = circular_queue.rear();
  135.         assert_eq!(result, Some(&3));
  137.         assert!(circular_queue.is_full());
  139.         circular_queue.de_queue();
  141.         circular_queue.en_queue(4);
  142.         let result = circular_queue.front();
  143.         assert_eq!(result, Some(&2));
  145.         let result = circular_queue.rear();
  146.         assert_eq!(result, Some(&4))
  147.     }
  148. }