数据结构-栈实验

发表于 更新于 从0开始的rust之旅

基本结构

一个栈结构体要有：栈底指针``栈顶指针``可用最大容量三个字段……指针是什么东西啊？rust崩溃

换个角度想，栈就是只能在一端进行增删操作的线性表，course.rs里给出了单向链表的实现，但为何非要链表？也许可以用Box模拟：

struct Stack {
    base : Box<[i32]>,
    top : usize,
    size : usize,
}

Box<[i32]>分配一个堆上的定长i32切片，但是定长并不能满足需求，大致有两种思路，一是利用vec完成不定长的部分再转换回定长切片，二是利用unsafe代码手动分配内存

使用vec!来简化实现：

impl Stack {
    fn new(size : usize) ->Self {
        let base  = vec![0; size].into_boxed_slice();
        Stack{
            base,
            top : 0,
            size,
        }
    }

    fn realloc(&mut self) -> Result<()> {
        let new_size = self.size * 2;
        let mut base = vec![0; new_size].into_boxed_slice();
        for i in 0..self.size {
            base[i] = self.base[i];
        }
        self.base = base;
        self.size = new_size;
        Ok(())
    }

    fn push(&mut self, value : i32) -> Result<()> {
        // full
        if self.top >= self.size {
            self.realloc()?;
        }
        // push
        self.base[self.top] = value;
        println!("top: {}", self.top);
        self.top += 1;
        Ok(())
    }

    fn pop(&mut self) -> Result<i32> {
        // empty
        if self.top == 0{
            return Err(anyhow!("Stack underflow"));
        }
        self.top -= 1;
        Ok(self.base[self.top])
    }
}

测试如下：

#[cfg(test)]
mod tests {
    use super::Stack;
    use anyhow::Result;
    // new 后栈应为空，pop 应返回错误
    #[test]
    fn test_new_initial_state() {
        let mut s = Stack::new(2);
        assert!(s.pop().is_err(), "new stack should be empty");
    }

    // push 多个元素后，pop 应按 LIFO 返回
    #[test]
    fn test_push_and_pop_lifo() -> Result<()>{
        let mut s = Stack::new(3);
        s.push(10)?;
        s.push(20)?;
        s.push(30)?;

        assert_eq!(s.pop()?, 30);
        assert_eq!(s.pop()?, 20);
        assert_eq!(s.pop()?, 10);
        assert!(s.pop().is_err(), "stack should be empty after popping all elements");
        Ok(())
    }

    // push 的数量超过初始容量，验证能正常工作（隐式测试扩容）
    #[test]
    fn test_push_resizes_and_handles_more_than_initial_capacity() {
        let mut s = Stack::new(2);
        for i in 1..=10 {
            s.push(i);
        }
        for i in (1..=10).rev() {
            assert_eq!(s.pop().unwrap(), i);
        }
        assert!(s.pop().is_err(), "stack should be empty after popping all elements");
    }

    // 单次 push 后 pop 返回相同值
    #[test]
    fn test_push_single_then_pop() {
        let mut s = Stack::new(1);
        s.push(42);
        assert_eq!(s.pop().unwrap(), 42);
        assert!(s.pop().is_err(), "stack should be empty after popping the single element");
    }
}

接下来就可以正式开始实验了：

（一） 数制转换问题

问题描述

将十进制数N和其它d进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除d取余法。例如：（1348）10 = （2504）8

10进制转换8进制过程

N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2

从表中可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈的后进先出（LIFO）的特性。所以可以用顺序栈来模拟这个过程。

基本要求

对于键盘输入的任意一个非负的十进制整数，打印输出与其等值的八进制数。由于上述的计算过程是从低位到高位顺序产生的八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此可以先将计算过程中得到的八进制数的各位进栈，待相对应的八进制数的各位均产生以后，再使其按顺序出栈，并打印输出。即得到了与输入的十进制数相对应的八进制数。

测试数据

依据软件工程的测试技术自己确定，注意测试边界数据。

实现

在实现了基本操作后，顺理成章：

fn trans(dec : i32) -> Result<()> {
    let mut s = Stack::new(5);
    let mut value = dec;

    if value == 0 {
        s.push(0)?;
    }

    while value > 0 {
        let m = value % 8;
        s.push(m)?;
        value = value / 8;
    }
    while !(s.top == 0 ){
        print!("{}", s.pop()?);
    }
    println!("");
    Ok(())
}

测试：

#[test]
    fn test_trans() -> Result<()> {
        assert!(trans(1348).is_ok());
        Ok(())
    }

看到结果：

running 1 test
2504
test stack::tests::test_trans ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

完成

括号匹配的检验

问题描述

假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（（）[ ]）或[（[ ] [ ]）]等为正确格式，[（]）或（（（]均为不正确的格式。检验括号是否匹配的方法可用"期待的紧迫程度"这个概念来描述。

例如：考虑下列的括号序列：

[  (  [  ]  [  ]  )  ]

当计算机接收了第1个括号以后，它期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号"[“只能暂时靠边，而迫切等待与第2个括号相匹配的第7个括号”）“的出现，类似的，因只等来了第3个括号”["，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接收了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了，……，依次类推。可见这个处理过程正好和栈的特点相吻合。

基本要求

读入圆括号和方括号的任意序列，输出"匹配"或"此串括号匹配不合法"。

测试数据

  • 输入 ([ ]())，结果"匹配"
  • 输入 [( ))，结果"此串括号匹配不合法"

实现提示

设置一个栈，每读入一个括号：

  • 若是左括号，则作为一个新的更急迫的期待压入栈中
  • 若是右括号，并且与当前栈顶的左括号相匹配，则将当前栈顶的左括号退出
  • 继续读下一个括号
  • 如果读入的右括号与当前栈顶的左括号不匹配，则属于不合法的情况

在初始和结束时，栈应该是空的。

实现

增加了一个辅助函数

fn is_empty(&self) -> bool {
        self.top == 0
    }
fn _match(seq : &str) -> Result<()> {
    let mut s = Stack::new(5);
    for c in seq.chars() {
        match c {
            '(' | '[' => s.push(c as i32)?,
            ')' => {
                if s.is_empty() || s.pop()? != '(' as i32 {
                    return Err(anyhow!("括号不匹配"));
                }
            },
            ']' => {
                if s.is_empty() || s.pop()? != '[' as i32 {
                    return Err(anyhow!("括号不匹配"));
                }
            },
            _ => {
                return Err(anyhow!("出现非预期字符"))
            } // 忽略其他字符
        }
    }
    if s.is_empty(){
        return Ok(());
    }else {
        return Err(anyhow!("mismatch"));
    }
}

测试：

#[test]
fn test_match(){
    assert!(_match("()").is_ok());
    assert!(_match("[]").is_ok());
    assert!(_match("([])").is_ok());
    assert!(_match("[()]").is_ok());
    assert!(_match("([][])").is_ok());
    assert!(_match("(([]))").is_ok());

    // 不匹配的情况
    assert!(_match("(").is_err());
    assert!(_match(")").is_err());
    assert!(_match("([)]").is_err());
    assert!(_match("][").is_err());
    assert!(_match("())").is_err());
    assert!(_match("[[]").is_err());
}

停车场管理

逃了逃了

# rust# 栈