队列

队列：

只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
允许插入的一端为队尾，允许删除的一端为对头。
先进先出的线性表。

——————————————顺序存储队列——————————————

队满判断条件：rear == size
队空判断条件：rear == front

   
    private static final Object[] EMPTY_ELEMENT_DATA = {};

    private Object[] elementData;

    private int rear;

    private int front;

    /**
     * 队列大小
     */
    private int size;

    public OrderQueue() {
        elementData = EMPTY_ELEMENT_DATA;
        rear = 0;
        front = 0;
    }

    public OrderQueue(int size) {
        this.size = size;
        rear = 0;
        front = 0;
        elementData = new Object[size];
    }

    /**
     * 入队
     *
     * @param o
     */
    public void enqueue(Object o) {
        //队尾指针比最大数据元素下一指针，则队列满
        if (rear == size) {
            throw new RuntimeException("队列已满");
        }

        elementData[rear++] = o;
    }

    /**
     * 出队
     * @return
     */
    public Object dequeue() {
        //队空判断条件
        if (rear == front) {
            throw new RuntimeException("队列为空");
        }

        return elementData[front ++ ];
    }

——————————————链式存储队列——————————————

    private static class LinkedQueueNode{
        private LinkedQueueNode next;

        private Object item;

        public LinkedQueueNode(LinkedQueueNode next, Object item) {
            this.next = next;
            this.item = item;
        }
    }


    //对头
    private LinkedQueueNode front;

    //队尾
    private LinkedQueueNode rear;

    /**
     * 队列长度
     */
    private int size;


    public void enqueue(Object o){
        //对头元素为空，则队头队尾都指向新元素
        LinkedQueueNode linkedQueueNode = new LinkedQueueNode(null,o);
        if(front == null){
            front = linkedQueueNode;
            rear = linkedQueueNode;
        }else {
            rear.next = linkedQueueNode;
            rear = linkedQueueNode;
        }

        size ++;
    }


    public Object dequeue(){
        if(front == null){
            throw new RuntimeException("队空");
        }


        LinkedQueueNode linkedQueueNode = front;
        front = front.next;
        size --;

        return linkedQueueNode.item;
    }



    public static void main(String[] args) {
        LinkedQueue linkedQueue = new LinkedQueue();
        linkedQueue.enqueue("1");
        linkedQueue.enqueue("s");
        linkedQueue.enqueue("c");
        linkedQueue.enqueue("a");

        System.out.println(linkedQueue.size);

        System.out.println(linkedQueue.dequeue());

        System.out.println(linkedQueue.size);

    }

———————————————-循环队列———————————————-

队空判断条件：rear == front
队满判断条件：(rear + 1) % size == front

    private Object[] elementData;

    /**
     * 队尾下标
     */
    private int rear;

    /**
     * 队头下标
     */
    private int front;

    /**
     * 队列大小
     */
    private int size;

    public LoopQueue(int size) {
        this.size = size;
        rear = 0;
        front = 0;
        elementData = new Object[size];
    }

    public void enqueue(Object o) {
        if ((rear + 1) % size == front) {
            throw new RuntimeException("队列满了");
        }

        elementData[rear] = o;

        /**
         * 队尾标识向下移动一
         */
        rear = (rear + 1) % size;







    }

    public Object dequeue() {
        if (rear == front) {
            throw new RuntimeException("队空");
        }

        Object o = elementData[front];
        front = (front + 1) % size;
        return o;

    }