【椰神Java小课堂】用双链表实现双端队列

前言

之前只能但单调的完成一端插入，一端删除，可是我希望功能更加全面，我两端均可以插入删除，该如何做呢？这需要使用一个数据结构——双向链表

双向链表
每个结点均有前驱后继

算法分析

**1.准备好头结点

1.头插（尾插类似）

2.头删（尾删类似）

代码展示

1.头插

public void pushHead(V value){//头插
            Node<V> cur=new Node<>(value);
            if(head==null){
                head=cur;
                tail=cur;
            }else{
                cur.next=head;
                head.pre=cur;
                head=cur;
            }
            size++;
        }

2.尾插

public void pushTail(V value){//尾插
            Node<V> cur=new Node<>(value);
            if(tail==null){
                head=cur;
                tail=cur;
            }else{
                tail.next=cur;
                cur.pre=tail;
                tail=cur;
            }
            size++;
        }

3.头删

public V popHead(){//头删
            V ans=null;
            if(head==null){//边界
                return ans;
            }
            size--;
            ans=head.value;
            if(head==tail){//说明只有一个元素，弹出该元素，那就为空了，头尾均设置为null
                head=null;
                tail=null;
            }else{
                head=head.next;//头往后跳
                head.pre=null;//当前结点为头结点，无前驱，故其pre设置为null
            }
            return ans;
        }

4.尾删

public V popTail(){
            V ans=null;
            if(tail==null){
                return ans;
            }
            size--;
            ans=tail.value;
            if(head==tail){
                head=null;
                tail=null;
            }else{
                tail=tail.pre;
                tail.next=null;
            }
            return ans;
        }

5.完整代码

package List;

public class 用单链表实现队列和栈 {
    public static class Node<V>{
        public V value;
        public Node<V> pre;
        public Node<V> next;
        public Node(V v){
            value=v;
            next=null;
            pre=null;
        }
    }

    public static class MyDeque<V>{
        private Node<V> head;
        private Node<V> tail;
        private  int size;
        public MyDeque(){
            head=null;
            tail=null;
            size=0;
        }
        public boolean isEmpty(){
            return size==0;
        }
        public int size(){
            return size;
        }
        public void pushHead(V value){//头插
            Node<V> cur=new Node<>(value);
            if(head==null){
                head=cur;
                tail=cur;
            }else{
                cur.next=head;
                head.pre=cur;
                head=cur;
            }
            size++;
        }
        public void pushTail(V value){//尾插
            Node<V> cur=new Node<>(value);
            if(tail==null){
                head=cur;
                tail=cur;
            }else{
                tail.next=cur;
                cur.pre=tail;
                tail=cur;
            }
            size++;
        }
        public V popHead(){//头删
            V ans=null;
            if(head==null){//边界
                return ans;
            }
            size--;
            ans=head.value;
            if(head==tail){//说明只有一个元素，弹出该元素，那就为空了，头尾均设置为null
                head=null;
                tail=null;
            }else{
                head=head.next;//头往后跳
                head.pre=null;//当前结点为头结点，无前驱，故其pre设置为null
            }
            return ans;
        }
        public V popTail(){
            V ans=null;
            if(tail==null){
                return ans;
            }
            size--;
            ans=tail.value;
            if(head==tail){
                head=null;
                tail=null;
            }else{
                tail=tail.pre;
                tail.next=null;
            }
            return ans;
        }
    }
    public static void main(String[] args) {
        MyDeque<Integer> myDeque=new MyDeque<Integer>();
        myDeque.pushHead(1);//1
        myDeque.pushHead(2);//2 1
        myDeque.pushTail(3);//2 1 3
        myDeque.pushTail(4);//2 1 3 4
        int ans1=myDeque.popHead();//1 3 4
        int ans2=myDeque.popTail();//1 3
        System.out.println(ans1+" "+ans2);//2 4
    }
}

双端链表，你学fei了吗？