栈的实现

使用数组实现

使用数组实现的栈结构, 它能保存的元素个数是固定的, 需要在初始化栈时指定栈的容量.

这里, 我们使用 Box<[Option<T>]> 用于指示数组中是否存储了元素, 如果它为 None 则表示在位置没有元素.

另外一种实现方式是 Box<[T]>, 并且要求类型 T 实现 Clone trait.

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

/// 使用数组实现静态栈结构
pub struct ArrayStack<T> {
    top: usize,
    buf: Box<[Option<T>]>,
}

impl<T> ArrayStack<T> {
    /// 初始化栈, 指定栈的容量
    #[must_use]
    pub fn new(capacity: usize) -> Self {
        debug_assert!(capacity > 0);
        
        let values: Vec<Option<T>> = (0..capacity).map(|_| None).collect();

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

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

    /// 将栈顶元素出栈
    ///
    /// 当栈已经空时, 返回 `None`
    pub fn pop(&mut self) -> Option<T> {
        if self.top > 0 {
            self.top -= 1;
            self.buf[self.top].take()
        } else {
            None
        }
    }

    /// 返回栈顶元素
    #[must_use]
    pub const fn top(&self) -> Option<&T> {
        if self.top > 0 {
            self.buf[self.top - 1].as_ref()
        } else {
            None
        }
    }

    /// 检查栈是否空
    #[must_use]
    pub const fn is_empty(&self) -> bool {
        self.top == 0
    }

    /// 返回当前栈中的元素个数
    #[must_use]
    pub const fn len(&self) -> usize {
        self.top
    }

    /// 返回栈的容量
    #[must_use]
    pub const fn capacity(&self) -> usize {
        self.buf.len()
    }
}

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

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

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

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

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

impl<T> FromIterator<T> for ArrayStack<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 {
            top: vec.len(),
            buf: vec.into_boxed_slice(),
        }
    }
}

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

使用数组实现 - 消除 Option

上面的实现过程中, 使用了 Option<T> 来向数组中存储元素, 这会额外占用一些内存, 操作效率有影响. 我们可以手动操作内存, 来消除 Option<T>:

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

/// 使用数组实现静态栈结构
pub struct ArrayStack2<T> {
    top: usize,
    buf: Box<[T]>,
}

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

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

impl<T> ArrayStack2<T> {
    /// # Panics
    ///
    /// Raise panic if failed to allocate memory.
    #[must_use]
    pub fn new(capacity: usize) -> Self {
        debug_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 {
            top: 0,
            buf,
        }
    }

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

    pub fn pop(&mut self) -> Option<T> {
        if self.top > 0 {
            self.top -= 1;
            unsafe {
                Some(ptr::read(self.buf.as_ptr().wrapping_add(self.top)))
            }
        } else {
            None
        }
    }

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

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

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

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

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

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

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

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

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

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

impl<T: fmt::Debug> fmt::Debug for ArrayStack2<T> {
    fn fmt(&self, f: &mut 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);
            Box::from_raw(slice)
        }
    }
}
}

使用动态数组 Vec 实现动态栈

使用 Vec<T> 实现的栈可以进行动态扩容, 但每次扩容时可能要进行内存的批量拷贝.

这个比较简单, 因为 Vec<T> 本身就实现了基本的栈操作接口, 我们只需要再包装一下就行:

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

pub struct VecStack<T: Sized>(Vec<T>);

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

impl<T> VecStack<T> {
    /// 初始化栈, 默认的容量为 0
    #[must_use]
    #[inline]
    pub const fn new() -> Self {
        Self(Vec::new())
    }

    /// 初始化栈, 指定栈的容量, 但可以自动扩容.
    #[must_use]
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        Self(Vec::with_capacity(capacity))
    }

    /// 将元素入栈
    #[inline]
    pub fn push(&mut self, value: T) {
        self.0.push(value);
    }

    /// 将栈顶元素出栈
    ///
    /// 当栈已经空时, 返回 `None`
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        self.0.pop()
    }

    /// 返回栈顶元素
    #[must_use]
    #[inline]
    pub fn top(&self) -> Option<&T> {
        self.0.last()
    }

    /// 检查栈是否空
    #[must_use]
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }

    /// 返回当前栈中的元素个数
    #[must_use]
    #[inline]
    pub fn len(&self) -> usize {
        self.0.len()
    }

    /// 返回栈的容量
    #[must_use]
    #[inline]
    pub fn capacity(&self) -> usize {
        self.0.capacity()
    }
}


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

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

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

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

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

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

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

使用链表实现动态栈

使用链表实现动态栈, 也是一个可行的方式, 为了简化代码, 我们使用了标准库中的双链表. 但是在这里使用单链表就足够了.

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

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

impl<T> ListStack<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);
    }

    /// 将栈顶元素出栈
    ///
    /// 当栈已经空时, 返回 `None`
    #[must_use]
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        self.0.pop_back()
    }

    /// 返回栈顶元素
    #[must_use]
    #[inline]
    pub fn top(&self) -> Option<&T> {
        self.0.back()
    }

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

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

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

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

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

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

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

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

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

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