双链表实现双端队列

双链表实现双端队列

双端队列是一个从两端都可以进行进队出队的队列。

代码：

/**
 * 使用双链表实现双端队列
 * 双端队列也就是在队列的两端都可以进行出队列以及入队列
 */
public class DoubleLinkedListImplementsDeQueue {
    //1.首先定义一个双端队列的节点信息类
    public static class Node<V> {
        public V value;
        public Node<V> last;
        public Node<V> next;
        public Node(V v) {
            value = v;
            last = null;
            next = 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;
        }
        //1.判断双端队列是否为空
        public boolean isEmpty() {
            return size == 0;
        }
        //2.双端队列的大小
        public int size() {
            return size;
        }
        //3.双端队列从头开始入队列
        public void pushHead(V value) {
            //1.首先定义一个节点信息用以保存入队列的节点信息
            Node<V> cur = new Node<>(value);
            //2.如果队列为空那么头和尾都指向刚进入队列的节点
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                //双端队列不为空
                cur.next = head;
                head.last = cur;
                head = cur;
            }
            size++;
        }
        //4.双端队列尾部进入队列
        public void pushTail(V value) {
            Node<V> cur = new Node<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                tail.next = cur;
                cur.last = tail;
                tail = cur;
            }
            size++;
        }
        //5.头部出队列
        public V pollHead() {
            //1.定义一个变量用以存储出队列节点的值
            V ans = null;
            if (head == null) {
                return ans;
            }
            size--;
            ans = head.value;
            //如果队列中只有一个节点那么出队列后需要将头尾都置为空
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                //队列不止一个节点
                head = head.next;
                head.last = null;
            }
            return ans;
        }
        //6.从尾部出节点
        public V pollTail() {
            V ans = null;
            if (head == null) {
                return ans;
            }
            size--;
            ans = tail.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.last;
                tail.next = null;
            }
            return ans;
        }
        //7.获取头节点信息的值
        public V peekHead() {
            V ans = null;
            if (head != null) {
                ans = head.value;
            }
            return ans;
        }
        //8.获取尾部节点信息的值
        public V peekTail() {
            V ans = null;
            if (tail != null) {
                ans = tail.value;
            }
            return ans;
        }
    }
}