java数据结构之双端队列

//其实数据结构我们首先要去理解其原理，然后通过实践来验证自己的想法，是一个很不错的选择
//如果你们看到了我前期链表的设计
//再来理解双端队列其实也是很简单的，
/*
 *主要是要注意到，在Node初始化时

就对Node的prev或next进行了指定
 *这也是理解双端队列的关键
 */

public class DQueue<E> {

    public DQueue() {
        firstNode = null ;
        lastNode = null ;
        size = 0 ;
    }
    private class Node{
        public E e ;
        public Node prev ;
        public Node next ;
        public Node(E e , Node prev ,Node next) {
            this.e = e ;
            this.prev = prev ;
            this.next = next ;
        }
    }
    
    private int size ;
    private Node firstNode ;
    private Node lastNode ;
    
    public void addToFront(E e) {
        Node newNode =new Node(e , null , firstNode) ;
        if(firstNode == null) {
            firstNode = newNode ;
            lastNode = newNode ;
        } else {
            firstNode.prev = newNode ;
            firstNode = newNode ;
        }
        size ++ ;
    }
    
    public void addToBack(E e) {
        Node newNode = new Node(e , lastNode , null) ;
        if(lastNode == null) {
            lastNode = newNode ;
            firstNode = newNode ;
        } else {
            lastNode.next = newNode  ;
            lastNode = newNode ;
        }
        size ++ ;
    }
    
    //从前端删除元素
    public E removeFront() {
        if(isEmpty()) {
            throw new IllegalArgumentException("空异常") ;
        }
        Node retNode = firstNode ;
        if(size == 1) {
            firstNode = lastNode = null ;
            size -- ;
        } else {
            firstNode = firstNode.next ;
            size -- ;
        }
        return retNode.e ;
    }

    //从后端删除元素
    public E removeLast() {
        if(isEmpty()) {
            throw new IllegalArgumentException("空异常") ;
        }
        Node retNode = lastNode ;
        if(size == 1) {
            firstNode = lastNode = null ;
            size -- ;
        } else {
            lastNode = lastNode.prev ;
            size -- ;
        }
        return retNode.e ;
    }    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public int getSize() {
        return size ;
    }
    
    public void clear() {
        firstNode = lastNode = null ; 
        size = 0 ;
    }
    
    public E getFront() {
        return firstNode.e ;
    }
    
    public E getLast() {
        return lastNode.e ;
    }
    
    public static void main(String[] args) {
        DQueue<Integer> dqueue = new DQueue<>() ;
        dqueue.addToFront(1);//1
        dqueue.addToFront(2);//21
        dqueue.addToFront(3);//321
        dqueue.addToFront(4);//4321
        dqueue.addToFront(5);//54321
        dqueue.addToBack(6);//543216
        dqueue.addToBack(7);//5432167
        
        System.out.println("获取第一个元素：");
        System.out.println(dqueue.getFront());
        System.out.println("获取最后一个元素");
        System.out.println(dqueue.getLast());
        System.out.println("输出数组大小");
        System.out.println(dqueue.getSize());
        int n = dqueue.getSize() ;
        for(int i =0 ; i < n ; i ++) {
            System.out.println("删除第1个元素:" + dqueue.removeFront());
        }
        System.out.println("分割线=============================分割线");
        dqueue.addToFront(1);
        dqueue.addToFront(2);
        dqueue.addToFront(3);
        dqueue.addToFront(4);
        dqueue.addToFront(5);
        dqueue.addToBack(6);
        dqueue.addToBack(7);
        /**
         * 删除第一个元素的结果为：5432167
         * 删除最后一个元素的结果为：7612345
         */
        for(int i =0 ; i < n ; i ++) {
            System.out.println("删除最后1个元素" + dqueue.removeLast());
        }

    }
}