七、Java数据结构-队列(Queue)

什么是队列

队列是一种基于先进先出(FIFO)的数据结构，是一种只能在一端进行插入,在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先读被读出来；

代码实现（通过双向链表来实现）

public class MyQueue<T> implements Iterable<T>{

    //记录头结点
    private Node head;
    // 记录最后一个结点
    private Node last;
    //记录链表的长度
    private int N;

    public MyQueue(){
        this.head = new Node(null,null);
        this.last = null;
        this.N = 0;
    }




    /**
     *  定义节点类
     */
    public   class Node{
        T item ;   //存储数据
        Node next;  //下一个节点
        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }



    public void clear(){
        this.head = null;
        this.N = 0;
    }
    public boolean isEmpty(){
        return this.N == 0;
    }
    public int size(){
        return this.N;
    }

    public T get(){
        if(isEmpty()){
            System.out.println("没有数据了");
            return null;
        }
        Node n = this.head.next;
        this.head.next = n.next;
        N --;
        if(isEmpty()){
            this.head.next=null;
            this.last = null;
        }
        return n.item;
    }


    public void push(T t){
        if(this.head.next == null){
            last = new Node(t, null);
            head.next = last;
        }else {
            Node oldlast = last;
            last = new Node(t,null);
            oldlast.next = last;
        }
        N ++;
    }
    @Override
    public Iterator<T> iterator() {
        return new MyIterator();
    }
    private  class MyIterator implements Iterator<T>{
        Node n = head;
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public T next() {
            n = n.next;
            return n.item;
        }
    }
}