数据结构玩转数据结构 3-5 数组队列

标签：11 return 队列 int QueueFirst 玩转数据结构 public size

0　　　　课程地址

https://coding.imooc.com/lesson/207.html#mid=13422

1　　　　重点关注

1.1　　　　队列的特性

FIFO,先进先出，水管

1.2　　　　队列的实现

参考3Coding　　

1.3　　　　队列的弊端：

dequeue方法复杂度为O(n)，数据量特别大的时候，计算机运行效率下降。

解决方案在下一节

2　　　　课程内容

3　　　　Coding

3.1　　　　队列示例

实现类

package com.company;

public class QueueFirst<E> implements Queue<E> {

    ArrayFan<E> arrayFan;

    /**
     *  无参构造
     * @author weidoudou
     * @date 2022/10/23 11:14
     * @return null
     **/
    public QueueFirst(){
        arrayFan = new ArrayFan<>();
    }

    /**
     * 有参构造
     * @author weidoudou
     * @date 2022/10/23 11:14
     * @param capacity 请添加参数描述
     * @return null
     **/
    public QueueFirst(int capacity){
        arrayFan = new ArrayFan<>(capacity);
    }

    /**
     * 这个方法感觉很鸡肋，因为动态数组能自增自减，是动态的，没有用到，课程有 ，先记下
     * @author weidoudou
     * @date 2022/10/23 11:33
     * @return int
     **/
    public int getCapacity(){
        return arrayFan.getCapacity();
    }

    /**
     * 队尾插入元素
     * @author weidoudou
     * @date 2022/10/23 11:10
     * @param e 请添加参数描述
     * @return void
     **/
    @Override
    public void enQueue(E e) {
        arrayFan.addLast(e);
    }

    /**
     * 队首删除元素
     * @author weidoudou
     * @date 2022/10/23 11:11
     * @return E
     **/
    @Override
    public E deQueue() {
        return arrayFan.removFirst();
    }

    /**
     * 队首展示元素
     * @author weidoudou
     * @date 2022/10/23 11:11
     * @return E
     **/
    @Override
    public E getFront() {
        return arrayFan.getFirst();
    }

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

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


    @Override
    public String toString() {
        StringBuffer stringBuffer = new StringBuffer();
        stringBuffer.append("QueueFirst:");

        stringBuffer.append("front"); //队列顶在此
        stringBuffer.append("[");
        for(int i=0;i<arrayFan.getSize();i++){
            stringBuffer.append(arrayFan.get(i));
            if(i!=arrayFan.getSize()-1){
                stringBuffer.append(",");
            }
        }
        stringBuffer.append("]");
        return stringBuffer.toString();
    }

}

接口

package com.company;

/**
 * 队列接口
 * @author weidoudou
 * @date 2022/10/23 11:10
 * @return null
 **/
public interface Queue<E> {

    /**
     * 队尾插入元素
     * @author weidoudou
     * @date 2022/10/23 11:10
     * @param e 请添加参数描述
     * @return void
     **/
    void enQueue(E e);

    /**
     * 队首删除元素
     * @author weidoudou
     * @date 2022/10/23 11:11
     * @return E
     **/
    E deQueue();

    /**
     * 队首展示元素
     * @author weidoudou
     * @date 2022/10/23 11:11
     * @return E
     **/
    E getFront();

    /**
     * 获取size
     * @author weidoudou
     * @date 2022/10/23 11:12
     * @return int
     **/
    int getSize();

    /**
     * 是否为空
     * @author weidoudou
     * @date 2022/10/23 11:12
     * @return boolean
     **/
    boolean isEmpty();

}

引用类

package com.company;

import java.util.Arrays;

public class ArrayFan<E> {
    private int size;
    //int类型的数组
    private E[] data;


    //1.1　　创建构造函数，传入容量，则新生成一个数组
    public ArrayFan(int capacity){
        data = (E[]) new Object[capacity];
        size = 0;
    }

    //1.2　　创建无参构造函数
    public ArrayFan(){
        this(10);
    }

    //1.3　　添加传入静态数组的构造函数
    public ArrayFan(E[] param){
        this.data = param;
        long outParm = Arrays.stream(param).filter(e->{
            return e!=null;
        }).count();
        this.size = (int)outParm;
    }

    //2.1　　添加getSize,获取数组元素个数
    public int getSize(){
        return size;
    }

    //2.2　　添加getCapacity,获取数组容量
    public int getCapacity(){
        return data.length;
    }

    //2.3　　添加数组是否为空方法
    public boolean isEmpty(){
        return size==0;
    }

    //3.1　　在数组末尾添加元素
    public void addLast(E e){
        addElement(size,e);
    }

    //3.2　　在数组起始添加元素
    public void addFirst(E e){
        addElement(0,e);
    }

    //3.3　　数组根据索引添加元素
    public void addElement(int index,E e){
        //1     校验异常
        //1.1   如果数组已经满了，则禁止插入
        if(size== data.length){

            //todo 并不会，需要把值一条一条的赋进来
            resize(2*size);
            //throw new IllegalArgumentException("数组已满，禁止插入");
        }

        //1.2   如果传入的索引在已有数组的索引之外，则校验异常
        if(index<0||index>size){
            throw new IllegalArgumentException("索引应在已有数组的索引之间");
        }

        //2     实现根据索引添加元素的逻辑
        //2.1   data同步
        for(int j = size-1;j>=index;j--){
            data[j+1] = data[j];
        }
        data[index] = e;

        //2.2   size同步
        size++;
    }

    //6.1     数组动态伸缩 这里用size更好，想想为什么
    private void resize(int capacity){
        E[] newData = (E[]) new Object[capacity];
        for(int i = 0;i < size;i++){
            newData[i] = data[i];
        }
        data = newData;
    }

    //4.1     数组 toString 范例
    @Override
    public String toString() {
        StringBuffer stringBuffer = new StringBuffer();
        stringBuffer.append(String.format("Array:size = %d,capacity = %d\n",size,data.length));

        stringBuffer.append("[");
        for(int i=0;i<size;i++){
            stringBuffer.append(data[i]);
            if(i!=size-1){
                stringBuffer.append(",");
            }
        }
        stringBuffer.append("]");
        return stringBuffer.toString();
    }

    //7.1  get第一个元素
    public E getFirst(){
        return get(0);
    }

    //7.2   get最后一个元素
    public E getLast(){
        return get(size-1);
    }


    //4.2     get获取元素
    public E get(int index){
        if(index<0||index>data.length){
            throw new IllegalArgumentException("111");
        }
        return data[index];
    }

    //4.3       set获取元素
    public void set(int index,E e){
        if(index<0||index>data.length){
            throw new IllegalArgumentException("111");
        }
        data[index] = e;
    }

    //5.1     数组包含
    public boolean contails(E e){
        for(int i = 0;i<size;i++){
            if(e.equals(data[i])){
                return true;
            }
        }
        return false;
    }

    //5.2     数组搜索
    public int search(E e){
        for(int i = 0;i<size;i++){
            if(e.equals(data[i])){
                return i;
            }
        }
        return -1;
    }

    //5.3     数组删除，通常情况下做删除，会在出参把删除的值带出来
    public E remove(int index){
        if(index<0||index>=size){
            throw new IllegalArgumentException("111");
        }

        E outParm = data[index];
        for(int i=index;i<size-1;i++){
            data[i] = data[i+1];
        }
        //这块不塞值也没有任何影响，因为size已经--了，不会访问到size之外的元素
        data[size-1]= null;
        size--;

        if(size == data.length/2){
            resize(data.length/2);
        }

        return outParm;
    }

    //5.4       删除首个元素
    public E removFirst(){
        return remove(0);
    }

    //5.5       删除最后的元素
    public E removLast(){
        return remove(size-1);
    }

    //5.6       删除指定的元素
    public void removElement(E e){
        int index = -1;
        //判断删除的元素是否存在
        for(int i=0;i<size;i++){
            if(e.equals(data[i])){
                index = i;
                break;
            }
        }
        if(index>=0){
            remove(index);
        }else{
            throw new IllegalArgumentException("删除的元素未找到");
        }
    }


}

测试类

package com.company;

public class Main {

    public static void main(String[] args) {
        Queue<Integer> queue = new QueueFirst<Integer>();
        for(int i = 0;i<10 ;i++){
            queue.enQueue(i);
            System.out.println(queue);

            if(i%3==0){
                queue.deQueue();
                System.out.println(queue);
            }

        }
    }
}

测试结果

QueueFirst:front[0]
QueueFirst:front[]
QueueFirst:front[1]
QueueFirst:front[1,2]
QueueFirst:front[1,2,3]
QueueFirst:front[2,3]
QueueFirst:front[2,3,4]
QueueFirst:front[2,3,4,5]
QueueFirst:front[2,3,4,5,6]
QueueFirst:front[3,4,5,6]
QueueFirst:front[3,4,5,6,7]
QueueFirst:front[3,4,5,6,7,8]
QueueFirst:front[3,4,5,6,7,8,9]
QueueFirst:front[4,5,6,7,8,9]

Process finished with exit code 0

标签：11,return,队列,int,QueueFirst,玩转,数据结构,public,size
From： https://www.cnblogs.com/1446358788-qq/p/16818240.html

数据结构玩转数据结构 3-5 数组队列

0　　　　课程地址

1　　　　重点关注

1.1　　　　队列的特性

1.2　　　　队列的实现

1.3　　　　队列的弊端：

2　　　　课程内容

3　　　　Coding

3.1　　　　队列示例

相关文章

赞助商

阅读排行

数据结构 玩转数据结构 3-5 数组队列

0 课程地址

1 重点关注

1.1 队列的特性

1.2 队列的实现

1.3 队列的弊端：

2 课程内容

3 Coding

3.1 队列示例

相关文章

赞助商

阅读排行

数据结构玩转数据结构 3-5 数组队列

0　　　　课程地址

1　　　　重点关注

1.1　　　　队列的特性

1.2　　　　队列的实现

1.3　　　　队列的弊端：

2　　　　课程内容

3　　　　Coding

3.1　　　　队列示例