struct Node<T> {
    elem: T,
    next: Link<T>,
}

struct List<T> {
    head: Link<T>
}


type Link<T> = Option<Box<Node<T>>>;

impl<T> List<T> {
    pub fn new() -> List<T> {
        return List { head: None };
    }
    pub fn push(&mut self, elem: T) {
        let old_head = self.head.take();
        let new_node = Node { elem: elem, next: old_head };
        self.head = Some(Box::new(new_node));
    }
    pub fn pop(&mut self, elem: T) -> Option<T> {
        let old_head = self.head.take();
        self.head = old_head.map(|n| { n.next });
        return old_head.map(|x| { x.elem });
    }
}