Stack

Stack 是一种非常重要的数据类型，在运算表达式的实现、DFS算法、进制转换中都会用到 Stack

简介

Klaus Samelson 和 Friedrich L. Bauer 在1955年提出了 栈 的概念，并在1957年申请了专利，Klaus Samelson 在1988年3月去世时，Friedrich L. Bauer 因发明了栈原理而获得IEEE计算机先锋奖。其实早在1946年 Alan M. Turing 就提出过这种数据堆叠的方式，图灵使用 “bury” 和 “unbury” 表示子程序的调用与返回

原理

栈是一种抽象的数据类型，它是一种后进先出（LIFO）的数据组织方式，核心操作包括 push 、pop。具体表现如下

push

新增元素

pop

删除元素

实现

栈的底层数据结构可以基于数组或链表实现，因此栈是一种 线性^{元素之间有着固定的顺序关系} 数据结构。这里我们使用 Rust 中的 Vec^{底层是动态数组} 实现 Stack。由于底层使用数组实现，所以 push 和 pop 的操作时间复杂度都是 O(1)，效率高于链表实现

#[derive(Debug)]
struct Stack<T> {
    top: usize,
    data: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Self {
        Stack {
            top: 0,
            data: Vec::new(),
        }
    }
    fn push(&mut self, val: T) {
        self.data.push(val);
        self.top += 1;
    }
    fn pop(&mut self) -> Option<T> {
        if self.top == 0 {
            return None;
        }
        self.top -= 1;
        self.data.pop()
    }
    fn peek(&self) -> Option<&T> {
        if self.top == 0 {
            return None;
        }
        self.data.get(self.top - 1) // 只查看，不删除
    }
    fn is_empty(&mut self) -> bool {
        self.top == 0
    }
    fn size(&self) -> usize {
        self.top
    }
}

应用

Stack 的应用非常广泛，包括但不限于

• 数制转换：将十进制数转换为二进制、八进制或十六进制
• 括号匹配：检查括号是否匹配
• 函数调用：保存和恢复函数状态
• 运算表达式：前缀、中、后缀表达式求值
• 编辑器的Undo/Redo操作
• 。。。

参考

Stack

You got a dream… You gotta protect it. - Chris Gardner

The Pursuit of Happyness