实现简单队列

使用数组实现

对于有静态队列, 使用数组来实现比较符合直觉.

#![allow(unused)]
fn main() {
use std::cmp::Ordering;
use std::fmt;
use std::hash::{Hash, Hasher};

pub struct ArrayQueue<T> {
    len: usize,
    buf: Box<[Option<T>]>,
}

impl<T> ArrayQueue<T> {
    #[must_use]
    pub fn new(capacity: usize) -> Self {
        let values: Vec<Option<T>> = (0..capacity).map(|_| None).collect();

        Self {
            len: 0,
            buf: values.into_boxed_slice(),
        }
    }

    /// # Errors
    ///
    /// 当栈已满时再将元素入队, 就会返回错误, 以及原有的元素 `value`.
    pub fn push(&mut self, value: T) -> Result<(), T> {
        if self.len == self.buf.len() {
            return Err(value);
        }

        self.buf[self.len] = Some(value);
        self.len += 1;

        Ok(())
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len > 0 {
            let front = self.buf[0].take();
            for i in 1..self.len {
                self.buf.swap(i - 1, i);
            }
            self.len -= 1;
            front
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub const fn len(&self) -> usize {
        self.len
    }

    #[must_use]
    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    #[must_use]
    #[inline]
    pub const fn capacity(&self) -> usize {
        self.buf.len()
    }

    #[must_use]
    #[inline]
    pub const fn front(&self) -> Option<&T> {
        if self.len > 0 {
            self.buf[0].as_ref()
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub fn front_mut(&mut self) -> Option<&mut T> {
        if self.len > 0 {
            self.buf[0].as_mut()
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub const fn back(&self) -> Option<&T> {
        if self.len > 0 {
            self.buf[self.len - 1].as_ref()
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub fn back_mut(&mut self) -> Option<&mut T> {
        if self.len > 0 {
            self.buf[self.len - 1].as_mut()
        } else {
            None
        }
    }
}

impl<T: PartialEq> PartialEq for ArrayQueue<T> {
    fn eq(&self, other: &Self) -> bool {
        self.len == other.len && PartialEq::eq(&self.buf, &other.buf)
    }
}

impl<T: Eq> Eq for ArrayQueue<T> {}

impl<T: PartialOrd> PartialOrd for ArrayQueue<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        PartialOrd::partial_cmp(&self.buf, &other.buf)
    }
}

impl<T: Ord> Ord for ArrayQueue<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        Ord::cmp(&self.buf, &other.buf)
    }
}

impl<T: Hash> Hash for ArrayQueue<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&self.buf, state);
    }
}

impl<T> FromIterator<T> for ArrayQueue<T> {
    fn from_iter<U: IntoIterator<Item=T>>(iter: U) -> Self {
        let vec: Vec<Option<T>> = iter.into_iter().map(|item| Some(item)).collect();
        Self {
            len: vec.len(),
            buf: vec.into_boxed_slice(),
        }
    }
}

impl<T: fmt::Debug> fmt::Debug for ArrayQueue<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&self.buf, f)
    }
}

使用数组实现 - 消除 Option<T> 类型

上面中的队列, 使用了 [Option<T>] 来表示数组中的元素类型, 这有些占用空间, 我们可以将这个问题消除, 通过手动操作内存的方式. 当然这会引入 unsafe 的函数:

#![allow(unused)]
fn main() {
use std::{fmt, ptr};
use std::alloc::{alloc, Layout};
use std::cmp::Ordering;
use std::hash::{Hash, Hasher};
use std::mem::ManuallyDrop;
use std::ptr::NonNull;

pub struct ArrayQueue2<T> {
    len: usize,
    buf: Box<[T]>,
}

struct RawVec<T> {
    ptr: NonNull<T>,
    cap: usize,
}

#[derive(Debug, Clone, Copy, Eq, PartialEq)]
enum AllocError {
    CapacityOverflow,
    AllocateError,
}

impl<T> ArrayQueue2<T> {
    /// # Panics
    ///
    /// Raise panic if failed to allocate memory.
    #[must_use]
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0);
        let raw_vec = RawVec::<T>::try_allocate(capacity).expect("Failed to allocate buffer");
        let buf: Box<[T]> = unsafe { raw_vec.into_box() };
        Self {
            len: 0,
            buf,
        }
    }

    /// # Errors
    ///
    /// 当栈已满时再将元素入队, 就会返回错误, 以及原有的元素 `value`.
    pub fn push(&mut self, value: T) -> Result<(), T> {
        if self.len == self.buf.len() {
            return Err(value);
        }

        self.buf[self.len] = value;
        self.len += 1;

        Ok(())
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len > 0 {
            // Take the first value, without calling drop method.
            let front = unsafe {
                Some(ptr::read(self.buf.as_ptr()))
            };
            // Move memory.
            unsafe {
                ptr::copy(self.buf.as_ptr().wrapping_add(1), self.buf.as_mut_ptr(), self.len - 1);
            }
            self.len -= 1;
            front
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub const fn len(&self) -> usize {
        self.len
    }

    #[must_use]
    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    #[must_use]
    #[inline]
    pub const fn capacity(&self) -> usize {
        self.buf.len()
    }

    #[must_use]
    #[inline]
    pub const fn front(&self) -> Option<&T> {
        if self.len > 0 {
            Some(&self.buf[0])
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub fn front_mut(&mut self) -> Option<&mut T> {
        if self.len > 0 {
            Some(&mut self.buf[0])
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub const fn back(&self) -> Option<&T> {
        if self.len > 0 {
            Some(&self.buf[self.len - 1])
        } else {
            None
        }
    }

    #[must_use]
    #[inline]
    pub fn back_mut(&mut self) -> Option<&mut T> {
        if self.len > 0 {
            Some(&mut self.buf[self.len - 1])
        } else {
            None
        }
    }
}

impl<T: PartialEq> PartialEq for ArrayQueue2<T> {
    fn eq(&self, other: &Self) -> bool {
        self.len == other.len && PartialEq::eq(&self.buf, &other.buf)
    }
}

impl<T: Eq> Eq for ArrayQueue2<T> {}

impl<T: PartialOrd> PartialOrd for ArrayQueue2<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        PartialOrd::partial_cmp(&self.buf, &other.buf)
    }
}

impl<T: Ord> Ord for ArrayQueue2<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        Ord::cmp(&self.buf, &other.buf)
    }
}

impl<T: Hash> Hash for ArrayQueue2<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&self.buf, state);
    }
}

impl<T> FromIterator<T> for ArrayQueue2<T> {
    fn from_iter<U: IntoIterator<Item=T>>(iter: U) -> Self {
        let vec: Vec<T> = iter.into_iter().collect();
        Self {
            len: vec.len(),
            buf: vec.into_boxed_slice(),
        }
    }
}

impl<T: fmt::Debug> fmt::Debug for ArrayQueue2<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&self.buf, f)
    }
}

impl<T> RawVec<T> {
    fn try_allocate(
        capacity: usize,
    ) -> Result<Self, AllocError> {
        debug_assert!(capacity > 0);
        let Ok(layout) = Layout::array::<T>(capacity) else {
            return Err(AllocError::CapacityOverflow);
        };

        let ptr = unsafe { alloc(layout) };
        if ptr.is_null() {
            return Err(AllocError::AllocateError);
        }
        let ptr = unsafe {
            NonNull::new_unchecked(ptr.cast::<T>())
        };

        Ok(Self { ptr, cap: capacity })
    }

    unsafe fn into_box(self) -> Box<[T]> {
        let me = ManuallyDrop::new(self);
        unsafe {
            let slice = ptr::slice_from_raw_parts_mut(me.ptr.as_ptr(), me.cap);
}

使用链表实现

可以使用链表来实现动态数组, 不限制队列中的元素个数.

对标准库中的双链表, 就可以很容易支持队列的接口.

#![allow(unused)]
fn main() {
use std::cmp::Ordering;
use std::collections::LinkedList;
use std::fmt;
use std::hash::{Hash, Hasher};

#[allow(clippy::linkedlist)]
pub struct ListQueue<T> (LinkedList<T>);

impl<T> Default for ListQueue<T> {
    #[inline]
    fn default() -> Self {
        Self::new()
    }
}

impl<T> ListQueue<T> {
    #[must_use]
    #[inline]
    pub const fn new() -> Self {
        Self(LinkedList::new())
    }

    #[inline]
    pub fn push(&mut self, value: T) {
        self.0.push_back(value);
    }

    #[must_use]
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        self.0.pop_front()
    }

    #[must_use]
    #[inline]
    pub fn len(&self) -> usize {
        self.0.len()
    }

    #[must_use]
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }

    #[must_use]
    #[inline]
    pub fn front(&self) -> Option<&T> {
        self.0.front()
    }

    #[must_use]
    #[inline]
    pub fn front_mut(&mut self) -> Option<&mut T> {
        self.0.front_mut()
    }

    #[must_use]
    #[inline]
    pub fn back(&self) -> Option<&T> {
        self.0.back()
    }

    #[must_use]
    #[inline]
    pub fn back_mut(&mut self) -> Option<&mut T> {
        self.0.back_mut()
    }
}

impl<T: PartialEq> PartialEq for ListQueue<T> {
    fn eq(&self, other: &Self) -> bool {
        PartialEq::eq(&self.0, &other.0)
    }
}

impl<T: Eq> Eq for ListQueue<T> {}

impl<T: PartialOrd> PartialOrd for ListQueue<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        PartialOrd::partial_cmp(&self.0, &other.0)
    }
}

impl<T: Ord> Ord for ListQueue<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        Ord::cmp(&self.0, &other.0)
    }
}

impl<T: Hash> Hash for ListQueue<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&self.0, state);
    }
}

impl<T> FromIterator<T> for ListQueue<T> {
    fn from_iter<U: IntoIterator<Item=T>>(iter: U) -> Self {
        let list = iter.into_iter().collect();
        Self(list)
    }
}

impl<T: fmt::Debug> fmt::Debug for ListQueue<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&self.0, f)
    }
}
}