数据结构 | (四) Queue

在 Java 中， Queue 是个接口，底层是通过链表实现 的

public class Queue {
    // 双向链表节点
    public static class ListNode{
        ListNode next;
        ListNode prev;
        int value;
        ListNode(int value){
            this.value = value;
        }
    }
    ListNode first; // 队头
    ListNode last; // 队尾
    int size = 0;
    // 入队列---向双向链表位置插入新节点
    public void offer(int e){
        ListNode newNode = new ListNode(e);
        if(first == null){
            first = newNode;
            // last = newNode;
        }else{
            last.next = newNode;
            newNode.prev = last;
            // last = newNode;
        }
        last = newNode;
        size++;
    }
    // 出队列---将双向链表第一个节点删除掉
    public int poll(){
    // 1. 队列为空
    // 2. 队列中只有一个元素----链表中只有一个节点---直接删除
    // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
        int value = 0;
        if(first == null){
            return null;
        }else if(first == last){
            last = null;
            first = null;
        }else{
            value = first.value;
            first = first.next;
            first.prev.next = null;
            first.prev = null;
        }
        --size;
        return value;
    }
    // 获取队头元素---获取链表中第一个节点的值域
    public int peek(){
        if(first == null){
            return null;
        }
        return first.value;
    }
    public int size() {
        return size;
    }
    public boolean isEmpty(){
        return first == null;
    }
}