栈
栈（Stack）可以理为一种具有双向数据方向（进栈和出栈），但只有单向出口（栈顶）的“容器式”的数据结构。
1. 认识栈
在生活中有许多类似栈数据结构的例子，比如一筒羽毛球，取球只能从顶部一个一个拿出来，对应出栈：从栈顶取出元素的操作；当把球放进筒时，每个放进的球只能在顶部，对应入栈：不断将新元素放入栈顶。
实际上，在很多编程语言中并没有预先设定的栈数据结构，可以使用该语言的数组或者链表，忽略其一些属性和方法来达到栈的状态。下面是一些栈的常用操作:
rust
let mut stack = Vec::new();
/*入栈*/
stack.push(0);
stack.push(1);
stack.push(2);
stack.push(3);
/*出栈*/
stack.pop().unwrap();
/*获取栈顶元素*/
let stack_top = stack.last().unwrap();
/*获取栈长度*/
let len = stack.len();
/*判断栈是否为空*/
let is_empty = stack.is_empty();2. 栈的实现
栈只能在栈顶添加和删除元素，而数组或者链表可以在任何位置添加和删除数据。因此想要通过二者实现栈，本质上就是对二者一些”属性“和”方法“的限制，使实现的栈对外仅保持栈的特性。为了更深刻地理解栈是如何通过这两种数据结构实现的，下面来着手实现简单的栈结构。
2.1. 基于链表实现栈
通过链表实现栈要考虑使用链表的头节点还是尾节点作为栈顶，分别对应头插法和尾插法。尾插法添加新元素的时候需要遍历链表至尾节点来实现，这里使用头插法来不断替换链表的头节点实现栈。一下以头插法实现栈的基本代码如下：
rust
//链表结构体
use std::rc::Rc;
use std::cell::RefCell;
/* 链表节点类 */
#[derive(Debug)]
struct ListNode {
val: i32, // 节点值
next: Option<Rc<RefCell<ListNode>>>, // 指向下一节点的指针
}
srtuct StackList{
stack_peek: Option<Rc<RefCell<ListNode<T>>>>,
stack_size:usize
}
impl StackList<T>{
//初始化栈
pub fn new() -> Self{
Self{
stack_peek:None,
stack_size:usize
}
}
//获取栈长度
pub fn size(&self) -> usize{
self.stack_size
}
//判断栈是否空
pub fn is_empty(&self) -> bool{
self.size() == 0
}
//获取栈顶元素
pub fn peek(&self) -> Option<Rc<RefCell<ListNode<T>>>>{
self.stack_peek.as_ref();
}
//入栈
pub fn push(&self,num:T){
let node = ListNode::new(num);
node.borrow_mut.next() = self.peek.take();
self.stack_peek = Some(node);
self.stack_size += 1;
}
//出栈
pub fn pop(&self) -> Option<T>{
/*
*当栈顶元素没有下一个元素时，栈顶被清空；如果有下一个元素，则更新栈顶为下一个元素,循环到栈尾实现出栈
*/
self.stack_peek.take().map(|old_head| {
match old_head.borrow_mut().next.take() {
Some(new_head) => {
self.stack_peek = Some(new_head);
}
None => {
self.stack_peek = None;
}
}
self.stk_size -= 1;
Rc::try_unwrap(old_head).ok().unwrap().into_inner().val
}
}