队列queue

先进先出的线性结构

方法

void enqueue(E)：入队
E dequeue()：出队
E getFront()：查看队列首元素
int getSize()：获取队列的大小
boolean isEmpty()：是否为空

数组队列

构造方法

/**
 * 自定义数组队列的实现
 * 基于动态数组实现
 * @author langao_q
 * @create 2020-05-20 15:35
 */
public class ArrayQueue<E> implements Queue<E>{

    private Array<E> array;

    /**
     * 自定义长度的
     * @param capacity
     */
    public ArrayQueue(int capacity){
        array = new Array<>(capacity);
    }

    /**
     * 使用默认长度的
     */
    public ArrayQueue(){
        array = new Array<>();
    }

获取方法

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public String toString() {
        return  "top<<< " + array + " <<<tail";
    }

void enqueue(E)：入队

    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

E dequeue()：出队

    @Override
    public E dequeue() {
        return array.removeFirst();
    }

E getFront()：查看队列首元素

    @Override
    public E getFront() {
        return array.getFirst();
    }

测试

循环队列

构造方法

/**
 * 自定义循环队列的实现
 * 基于动态数组实现
 * @author langao_q
 * @create 2020-05-20 16:03
 */
public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    /**
     * front队首指针
     * tail队尾指针
     */
    private int front, tail;

    private int size;

    /**
     * 有参数构造：指定长度的队列
     * @param capacity
     */
    public LoopQueue(int capacity){
        data = (E[]) new Object[capacity+1];
        front = 0;
        tail = 0;
        size = 0;
    }

    /**
     * 无参数构造
     */
    public LoopQueue(){
        this(10);
    }

获取方法

    @Override
    public int getSize() {
        return size;
    }

    /**
     * 获取队列的容量
     * 循环队列会有意的浪费调一个节点 所以要减一
     * @return
     */
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * 当队首和队尾指针相同时 队列就为空了
     * @return
     */
    @Override
    public boolean isEmpty() {
        return front == tail;
    }

void enqueue(E)：入队

    @Override
    public void enqueue(E e) {
        //当队尾+1 % 容量 == 队首时说明队列已经满了
        if((tail + 1)%data.length == front){
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;
    }

E dequeue()：出队

    @Override
    public E dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("dequeue 出队失败 === 队列为空！");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size --;
        if(size == getCapacity()/4 && getCapacity()/2 != 0){
            resize(getCapacity() / 2);
        }
        return ret;
    }

E getFront()：查看队列首元素

    @Override
    public E getFront() {
        if(isEmpty()){
            throw new IllegalArgumentException("dequeue 出队失败 === 队列为空！");
        }
        return data[front];
    }

扩容方法

    /**
     * 扩容方法 队列满了之后才扩容 每次扩容capacity * 2
     * 注意：队列数组中我们有意识的浪费了一个节点
     * 队尾的指针可能指向index为2的位置，所以迁移元素的时候要注意，同时还要考虑数组越界的问题
     * resize以后队首指向index为0的位置，队尾指向size位置
     * @param newCapacity
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i)%data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

测试

数组队列&循环队列比较

数组队列：dequeue出队时时间复杂度为0(n)，需要遍历整个数组（删除后需要遍历移动整个数组）
循环队列：dequeue出队时时间复杂度为0(1)，直接取出当前数据即可

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2020/05/20 17:26