基于双向链表实现: 栈 队列

        内部类DoublelinkedList 可以构建双向链表, 提供4中操作: 头插 ,头取 ,尾插 ,尾取 .所以可以称为"双端双向链表"(自己起的 便于理解),这两端分别由head 和 tail 分别引用. 通常链表无论是单向还是双向链表都只有一个 head, 但为了实现基于"双端双向链表"的 "栈" 和 "队列",这四种操作头插 和 头取 就是 "栈" ,头插 尾取就是"队列".

         栈和队列都是逻辑上的结构,在数据结构中是ADT,实现的方式可以基于数组或链表或其它.      

public class StackOrQueuebaseonlink {

    private static class MyStack{
        private final DoublelinkedList linkedList = new DoublelinkedList<>();
        public void push(T t){
            linkedList.addToHead(t);
        }
        public T pop(){
            return linkedList.popFromHead();
        }
    }

    private static class MyQueue{
        private final DoublelinkedList linkedList = new DoublelinkedList<>();
        public void push(T t){
            linkedList.addToHead(t);
        }
        public T pop(){
            return linkedList.popFromTail();
        }
    }

    
    private static class DoublelinkedList {
        public Node head;
        public Node tail;

        
        public T popFromHead(){
            if(this.head == null){
                return null;
            }
            Node curr = head;
            if(head == tail){
                head = null;
                tail = null;
            }else{
                head = head.next;
                head.prev = null;
                curr.next = null;
            }
            return curr.val;
        }
        
        public T popFromTail(){
            if(this.tail == null){
                return null;
            }
            Node curr = tail;
            if(tail == head){
                tail = null;
                head = null;
            }else{
                tail = tail.prev;
                tail.next = null;
                curr.prev = null;
            }
            return curr.val;
        }

        public void addToHead(T val) {
            Node curr = new Node<>(val);
            if (head == null) {
                head = curr;
                tail = curr;
            } else {
                //头插curr
                curr.next = head;
                head.prev = curr;
                //重置head
                head = curr;
            }
        }

        public void addToTail(T val){
            Node curr = new Node<>(val);
            if(tail == null){
                head = curr;
                tail = curr;
            }else{
                //尾插
                tail.next = curr;
                curr.prev = tail;
                tail = curr;
            }
        }
    }

    private static class Node {
        public T val;
        public Node prev;
        public Node next;

        public Node(T val) {
            this.val = val;
        }
    }
}

  左神算法学习