Deque--双向队列，支持同时在两端添加或删除元素--基于双向链表实现

支持以下API
isEmpty() 判断队列是否为空
size() 节点数量
pushLeft() 左端插入节点
pushRight() 右端插入节点
popLeft() 左端删除节点
popRight() 右端删除节点

代码

import java.util.Iterator;

/**
 * @author 鯉伴MAY
 * @param <Item>
 */
public class Deque <Item> implements Iterable<Item>{
    public Deque() {}

    private class DequeNode {
        Item item;
        DequeNode pre;
        DequeNode next;
    }
    private DequeNode first;
    private DequeNode last;
    private int N;
    public boolean isEmpty(){
        return first == null;
    }
    public  int size() {
        return N;
    }

    //创建新的节点
    private DequeNode newNode(Item item) {
        DequeNode temp = new DequeNode();
        temp.item = item;
        return  temp;
    }

    //从左端插入节点
    public void pushLeft(Item item) {
        DequeNode xNode = newNode(item);
        if(isEmpty()) {
            first = xNode;
            last = xNode;
        }else {
            xNode.next = first;
            first.pre = xNode;
            first = xNode;
        }
        N++;
    }

    //从右端插入节点
    public void pushRight(Item item) {
        DequeNode xNode = newNode(item);
        if(isEmpty()) {
            first = xNode;
            last = xNode;
        }else {
            last.next = xNode;
            xNode.pre = last;
            last = xNode;
        }
        N++;
    }

    //从左端弹出节点
    public Item popLeft() {
        if(isEmpty()){
            System.out.println("栈已空");
            return null;
        }
        DequeNode temp = first;
        if(size() == 1) {
            first = null;
            last = null;
        }else {
            first = first.next;
            first.pre = null;
            temp.next = null;
        }
        N--;
        return temp.item;
    }

    //从右端弹出节点
    public Item popRight() {
        if(isEmpty()) {
            System.out.println("队列已空");
            return null;
        }
        DequeNode temp = last;
        if(size() == 1) {
            first = null;
            last = null;
        }else {
            last = last.pre;
            last.next = null;
            temp.pre = null;
        }
        N--;
        return  temp.item;
    }


    public void printStack() {
        DequeNode temp = first;
        while(temp != null) {
            System.out.println(temp.item);
            temp = temp.next;
        }
    }

    @Override
    public Iterator<Item> iterator() {
        return new LIterator();
    }
    private class LIterator implements  Iterator<Item>{
        private DequeNode current = first;
        @Override
        public boolean hasNext() {
            return current != null;
        }
        @Override
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}