[数据结构与算法]实现队列（链表实现）和循环队列（数组实现）

队列的概念：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾（Tail/Rear）

出队列：进行删除操作的一端称为队头 （Head/Front）

?实现队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据效率会比较低。

?

?

1.使用链表实现队列

package queue;

public class MyQueue {

    //使用链表实现队列
    static class Node{
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
        }
    }
    //头结点和尾结点
    private Node head;
    private Node tail;
    //以尾部入队列，头部出队列实现
    //入队列,标准库用offer
    public void offer(int val){
        Node node=new Node(val);
        if(this.head==null){
            this.head=node;
            this.tail=node;
        }
        this.tail.next=node;
        tail=tail.next;
    }
    //出队列，表中库用poll
    public int poll(){
        if(this.head==null){
            throw new RuntimeException();
        }
        int ret=this.head.data;
        this.head=this.head.next;
        if(this.head==null){
            this.tail=null;
        }
        return ret;
    }
    //查看队首元素,标准库用peek
    public int peek(){
        return this.head.data;
    }
}

2.使用数组实现循环队列

package queue;

//数组实现循环队列
class Array {
    private int[] array = new int[3];
    private int head = 0;
    private int tail = 0;
    private int size = 0;

    //入队列
    public void offer(int val) {
        if (size == array.length) {
            return;
        }
        array[tail] = val;
        tail++;
        //当tail超过数组最后一个的时候，就让tail等于0
        if (tail >= array.length) {
            tail = 0;
        }
        size++;
    }

    //出队列
    public Integer poll() {
        int ret = array[head];
        head++;
        //当head超过数组最后一个元素的时候，就让head等于0
        if (head >= array.length) {
            head = 0;
        }
        size--;
        return ret;
    }

    //查看对手元素
    public Integer peek() {
        if(size==0){
            return null;
        }
        return array[head];
    }
}

public class MyQueueArray {
    public static void main(String[] args) {
        Array array=new Array();
        array.offer(1);
        array.offer(2);
        array.offer(3);
        array.offer(4);
        System.out.println(array.poll());
        System.out.println(array.peek());
        System.out.println(array.poll());
        System.out.println(array.poll());
        System.out.println(array.poll());
        System.out.println(array.poll());





    }
}