数据结构---队列(Queue)

一、基本概念

队列是一种线性数据结构

二、特点

1. 队列是"先进先出(FIFO---First In First Out)"(买饭排队:先排队的先买饭,买完饭就退出队列,准备买饭从队尾进入队列排队)

2. 规定只能从一端(队尾)添加元素,从另一端(队首)取出元素

三、基本操作

1. 定义一个接口,里面实现队列的相关操作

   public interface Queue_1<T> {
       //  入队
       void offer(T ele);
   
       //  出队
       T pool();
   
       //  查看队首元素
       T peek();
   
       //  队列中元素的个数
       int getSize();
   
       //  队列是否为空
       boolean isEmpty();
   }

2. 以数组作为队列的底层数据结构

   public class ArrQueue<T> implements Queue_1<T> {}
   

3. 创建全局变量

   //  队列的容器
   private MyArray<T> data;

4. 重载构造方法

   public ArrQueue() {
       this.data = new MyArray<>(50);
   }

5. 入队操作

   @Override
   public void offer(T ele) {
       this.data.add(ele);//  将元素添加到队尾
   }

6. 出队操作

   @Override
   public T pool() {
       if (isEmpty()) {
           return null;
       }
       return this.data.removeByIndex(0);//  将第一个元素返回
   }

7. 获取队首的元素

   @Override
   public T peek() {
       if (isEmpty()) {
           return null;
       }
       return this.data.getValueByIndex(0);//  获取队首的元素
   }

8. 获取队列中实际存放元素的个数

   @Override
   public int getSize() {
       return this.data.getSize();//  获取队列中实际存放元素的个数
   }

9. 判断队列是否为空

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

四、循环队列

1.创建一个以数组为底层的循环队列类

public class LoopArr<T> {}

2.定义全局变量

private T[] data;//  创建一个泛型数组 保存数据data
private int size;//  创建一个变量 数组中实际存放元素的个数size
private int front;//  指向队首
private int tail;//  指向队尾
private int capacity;//  创建一个变量 容积capacity

?3.构造函数

public LoopArr(int capacity) {
    //  判断容量,传入容量小于0
    if (capacity < 0) {
        //  将队列容量初始化为11
        this.capacity = 11;
    } else {
        //  将队列容量增加1个,可使队列判断队满及队空更加方便
        this.capacity = capacity + 1;
    }
    this.size = 0;//  初始化队列中实际存放元素个数
    this.front = this.tail = 0;//  初始化队列,将队头与队尾都置为0
    this.data = (T[]) (new Object[this.capacity + 1]);//  为泛型数组赋值
}

?4.向数组中添加元素

public void add(T item) {
    //判断数组是否满
    if ((this.tail + 1) % capacity == this.front) {
        // 扩容   resize  容积扩一倍
        resize((this.capacity - 1) * 2 + 1);
    }
    //  向指定位置添加元素
    this.data[this.tail] = item;
    this.tail = (this.tail + 1) % this.capacity;
    //更新this.size
    this.size++;
}

5.扩容

private void resize(int newCapacity) {
    System.out.println("resize:" + newCapacity);//  打印数组的新容量
    //  改变容量与容积
    this.data = Arrays.copyOf(data, newCapacity);
    this.capacity = newCapacity;
    //  将this.front置为零,this.tail=this.size
    this.front = 0;
    this.tail = this.size;
}

?6.移除队首元素

public T remove() {
    if (isEmpty()) {
        return null;
    }
    T delValue = this.data[this.front];//  获取要删除索引的值
    //  删除完之后,this.front向后移动
    this.front = (this.front + 1) % capacity;
    //  更新数组索引
    this.size--;
    //  判断是否缩容
    if (this.size < this.capacity / 4 && this.capacity / 2 > 0) {
        resize((this.capacity - 1) / 2 + 1);
    }
    return delValue;//  返回删除的值
}

7.创建循环队列

public class LoopQueue<T> implements Queue_1<T> {
    private LoopArr<T> data;//  容器

    public LoopQueue() {
        this.data = new LoopArr<>(100);
    }

    //  向循环队列中从队尾添加元素
    @Override
    public void offer(T ele) {
        this.data.add(ele);
    }

    //  将队头元素从循环队列中移出
    @Override
    public T pool() {
        return this.data.remove();
    }

    //  获取队头元素
    @Override
    public T peek() {
        return this.data.getFirstVal();
    }

    //  获得循环队列的长度
    @Override
    public int getSize() {
        return this.data.getSize();
    }

    //  判断循环队列是否为空
    @Override
    public boolean isEmpty() {
        return this.data.isEmpty();
    }
}

五、双端队列

1.创建双端队列类

public class Dique {}

2.创建队列

//  普通队列
Queue<Integer> queue = new LinkedList<>();

//  双端队列  linkedList
LinkedList<Integer> help = new LinkedList<>();

3.添加操作

public void offer(int ele) {
    this.queue.add(ele);
    //  判断双端队列中(从尾部开始比ele小的元素都要出队)
    while (!this.help.isEmpty() && this.help.peekFirst() < ele) {
        this.help.pollLast();//  LinkedList中特有的方法,将最后一个元素检索并删除
    }
    this.help.offerLast(ele);//  将元素从尾部添加
}

4.删除操作

public Integer remove() {
    //  队列为空,返回null
    if (this.queue.isEmpty()) {
        return null;
    }
    //  队头与双端队列队头相同,双端环队列队头删除
    if (this.queue.peek() == this.help.peekFirst()) {
        this.help.pollFirst();
    }
    //  并将普通队列队头删除
    return this.queue.poll();
}