队列与栈二

队列是一种常见的数据结构，在生活中有很多应用场景，例如排队系统，常见的各种MQ基本上都算队列，队列的一个原则就是先进先出，保证了公平性。

队列的数组实现

队列的数组实现方式如下，数组实现的有点在于每次出队都要进行大量元素的腾挪操作，非常耗时。并且当进行入队操作时，初始分配的队列长度不够的时候，需要申请一块更大的空间来腾挪旧的元素，再插入新元素。

package com.lei.payment.java.base.algorithm.list.queue;

import com.lei.payment.java.base.algorithm.exception.AlgorithmException;
import com.lei.payment.java.base.algorithm.exception.ErrorCode4Algorithm;
import com.lei.payment.java.base.algorithm.list.AbstractList;

public class ArrayQueue<T> extends AbstractList<T> {
    private Object[] queue;

    private int DEFAULT_QUEUE_SIZE = 32;

    private int size = 0;

    /**
     * 有参构造函数
     * @param size
     */
    public ArrayQueue(int size) {
        if (size < 1) {
            throw new AlgorithmException(ErrorCode4Algorithm.INDEX_OUT_OF_RANGE);
        }
        this.queue = new Object[size];
        this.size = 0;
    }

    /**
     * 无参构造函数
     */
    public ArrayQueue() {
        new ArrayQueue<T>(DEFAULT_QUEUE_SIZE);
    }

    @Override
    public T pop() {
        if (this.isEmpty()) {
            throw new AlgorithmException(ErrorCode4Algorithm.INDEX_OUT_OF_RANGE);
        }
        T t = (T) this.queue[0];
        for (int i = 1; i < this.size; i++) {
            this.queue[i - 1] = this.queue[i];
        }
        this.size--;
        return t;
    }

    @Override
    public void push(T t) {
        if (this.size == this.queue.length) {
            resize(this.queue, this.size + this.DEFAULT_QUEUE_SIZE);
        }
        this.queue[this.size++] = t;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public T fist() {
        if (this.isEmpty()) {
            throw new AlgorithmException(ErrorCode4Algorithm.INDEX_OUT_OF_RANGE);
        }
        return (T) this.queue[0];
    }

    @Override
    public T last() {
        if (isEmpty()) {
            throw new AlgorithmException(ErrorCode4Algorithm.INDEX_OUT_OF_RANGE);
        }
        return (T) this.queue[this.size - 1];
    }

    @Override
    public boolean isEmpty() {
        return this.size <= 0;
    }

    /**
     * resize array
     *
     * @param oldQueue old queue
     * @param newSize  new size
     */
    private void resize(Object[] oldQueue, int newSize) {
        Object[] newQueue = new Object[newSize];
        for (int i = 0; i < this.size; i++) {
            newQueue[i] = oldQueue[i];
        }
        this.queue = newQueue;
    }
}

队列的链式实现

队列的链式实现如下，链式队列适合进行频繁的插入删除操作。

package com.lei.payment.java.base.algorithm.list.queue;

import com.lei.payment.java.base.algorithm.exception.AlgorithmException;
import com.lei.payment.java.base.algorithm.exception.ErrorCode4Algorithm;
import com.lei.payment.java.base.algorithm.list.AbstractList;
import com.lei.payment.java.base.algorithm.node.ListNode;

public class LinkedQueue<T> extends AbstractList<T> {
    /**
     * 队头
     */
    ListNode<T> head;

    /**
     * 队尾
     */
    ListNode<T> end;

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

    /**
     * 构造函数
     */
    public LinkedQueue() {
        this.init();
    }

    @Override
    public T pop() {
        if (this.isEmpty()) {
            throw new AlgorithmException(ErrorCode4Algorithm.INDEX_OUT_OF_RANGE);
        }
        T t = this.head.getVal();
        this.head = this.head.getNext();
        this.size--;
        return t;
    }

    @Override
    public void push(T t) {
        this.end.setVal(t);
        ListNode<T> newEnd = new ListNode<T>();
        this.end.setNext(newEnd);
        this.end = this.end.getNext();
        this.size++;
    }

    @Override
    public int size() {
        return this.size;
    }

    /**
     * init queue
     */
    private void init() {
        this.head = new ListNode();
        this.head.setNext(null);
        this.head.setVal(null);
        this.end = this.head;
        this.size = 0;
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0 || this.head == this.end;
    }

    @Override
    public T fist() {
        if (this.isEmpty()) {
            throw new AlgorithmException(ErrorCode4Algorithm.INDEX_OUT_OF_RANGE);
        }
        return this.head.getVal();
    }

    @Override
    public T last() {
        if (this.isEmpty()) {
            throw new AlgorithmException(ErrorCode4Algorithm.INDEX_OUT_OF_RANGE);
        }
        return this.end.getVal();
    }
}