链表实现队列的底层实现

image.png

接口定义

public interface Queue <E> {
    void enQueue(E e);
    E deQueue();
    int getSize();
    E getFront();
    boolean isEmpty();
}

public class LinkedListQueue<E> implements Queue<E> {

    private class Node<E>{
        E e;
        Node next;
        public Node (E e, Node next){
            this.e=e;
            this.next=next;
        }
        public Node(E e){
            this(e,null);
        }
        public Node(){
            this(null,null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }
    private Node head,tail;
    private int size;

    public LinkedListQueue(){
        this.head=null;
        this.tail=null;
        size=0;
    }
    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }
    @Override
    public void enQueue(E e) {
        if(tail==null) {
            tail = new Node(e);
            head=tail;
        }
        else{
            tail.next=new Node(e);
            tail=tail.next;
        }
        size++;
    }

    @Override
    public E deQueue() {
        if(isEmpty()){
            throw new IllegalArgumentException("DeQueue fail, Queue is Empty!");
        }
        Node retNode=head;
        head=head.next;
        retNode.next=null;
        if(head.next==null){
            tail=null;
        }
        size--;
        return (E) retNode.e;
    }


    @Override
    public E getFront() {
        if(isEmpty())
            throw new IllegalArgumentException("*Queue is empty.");
        return (E) head.e;
    }

    @Override
    public String toString() {
        StringBuilder res=new StringBuilder();
        res.append("Queue front ");
        Node cur=head;
        while (cur!= null) {
            res.append(cur+"->");
            cur=cur.next;
        }
        res. append ( "NULL tail' ");
        return res. toString ();
    }
    public static void main(String[] args){
        LinkedListQueue<Integer> queue=new LinkedListQueue<>();
        System.out.println(queue.isEmpty());
        queue.enQueue(1);
        queue.enQueue(2);
        queue.enQueue(3);
        queue.enQueue(4);
        queue.enQueue(5);
        System.out.println(queue);
        queue.deQueue();
        queue.deQueue();
        System.out.println(queue);
        System.out.println(queue.getSize());

    }
}

实验结果