链表实现栈（LIFO）、队列（FIFO）

今天来用链表实现栈

栈可以用链表实现，压栈操作即在链表头赋值，弹栈只需要将链表头元素指向下一个即可

public class LinkedListStack<T> {
    private int N;
    private Node first;
    private class Node{
        T t;
        Node next;
    }
    public LinkedListStack(){
        first = new Node();
    }
    //压栈 添加一个first 将值赋给first
    public void push(T t){
        Node oldFirst = first;
        first = new Node();
        first.next = oldFirst;
        first.t = t;
        N++;
    }

    public T pop(){
        T t = first.t;
        first = first.next;
        N --;
        return t;
    }

    public boolean isEmpty(){
        return N ==0;
    }
    
    //返回顶元素
    public T peek(){
        return first.t;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(first.t);
        for(Node node = first.next; node!=null; node = node.next){
            res.append("->").append(node.t);
        }
        return res.toString();
    }
}

由此可见，链表也可以实现队列操作，只需要每次返回链表尾部即可

public class LinkedListQueue<T> {
    private int N;
    private Node first; //指向最早添加的
    private Node last; //指向尾部
    private class Node{
        T t;
        Node next;
    }
    public LinkedListQueue(){
        first = new Node();
        last = new Node();
    }

    public boolean isEmpty(){
        return N == 0;
    }

    public int size(){
        return N;
    }

    public void enqueue(T t){
        //进队，则向链表尾部添加元素
        Node oldLast = last;
        last = new Node();
        last.t = t;
        last.next = null;
        //判断是否是空队列
        if(isEmpty()){
            first = last;
        }else {
            oldLast.next = last;
        }
        N ++;
    }
    public T dequeue(){
        //从表头删除元素 ，类似出栈
        T t = first.t;
        first = first.next;
        if(isEmpty()){
            last = null;
        }
        N --;
        return t;
    }

队列的实现也就是增加一个last指向尾部，每一次进队都要对尾部进行操作

转载于:https://www.jianshu.com/p/d9ee39540f9a