数据结构-Queue队列

news/发布时间2024/5/15 16:16:13

一,队列的简单认识

队列也是一种线性数据结构,与栈不同的是,它只能从一端添加元素,从另一端取出元素.定义了一端,另一端也就确定了.

(当然还有一个特殊的双向队列LinkedList除外,它既可以从队首添加元素,也可以移除元素,队尾也是一样的,既可以添加元素,也可以移除元素)

二,队列的实现

Queue<E>

1,void enqueue(E) //添加元素

2,E dequeue() //移除元素

3,E getFront() //获取第一个元素,但不移除

4,int getSize() //获取索引

5,boolean isEmpty() //判断队列是否为空

三,队列代码实现,

了解队列的基本功能,对队列的功能进行代码实现,底层逻辑为数组,同样栈也可以实现队列的功能,队列也可以实现栈的功能.

(注意:利用泛型可以对任意类型的数据进行操作)

1,用抽象类来封装相关功能

public interface Queue<T> {// 入队的方法void enqueue(T ele);// 出队的方法T dequeue();// 查看队首元素T getFront();// 队列中元素的数量int getSize();// 判断队列是否为空boolean isEmpty();
}

2,用数组来实现队列功能

import java.util.Optional;
import java.util.Random;// 封装属于自己的数组,使用泛型
public class CycleArray<T> {private T[] data; // 底层数据结构private int size;// 用来保存实际存放元素的个数private int capacity; // 表示容积// 声明索引private int front, tail;public CycleArray() {this(5);}public CycleArray(int capacity) {this.capacity = capacity;this.data = (T[]) new Object[this.capacity + 1];this.size = 0;this.front = this.tail = 0;}// 获取容积的方法public T getFront() {if (this.isEmpty()) {return null;}return this.data[this.front];}// 判断数组是否为空public boolean isEmpty() {return this.front == this.tail;}// 获取数组实际存放元素的个数public int getSize() {return this.size;}/*** 在尾部添加** @param val 插入的值*/public void addTail(T val) {// 在增加之前，判断数组是否已满，如果已满，要进行扩容if ((this.tail + 1) % this.data.length == this.front % this.data.length) {// 扩容操作resize(this.capacity * 2);}this.data[this.tail] = val;// 更新tailthis.tail = (this.tail + 1) % this.data.length;System.out.println("入队：this.front=" + this.front + ",this.tail=" + this.tail);this.size += 1;}// 改变容积的方法private void resize(int newCapacity) {System.out.println("--------resize--------");// 2、 创建一个新数组T[] newArr = (T[]) new Object[newCapacity + 1];// 3、将原来数组的内容转移到新数组for (int i = 1; i <= this.size; i++) {newArr[i - 1] = this.data[this.front];this.front = (this.front + 1) % this.data.length;}this.front = 0;this.tail = this.size;System.out.println("扩容完成：this.front=" + this.front + ",this.tail=" + this.tail);// 4、将newArr赋值给 this.datathis.data = newArr;// 5、将newCapacity 赋值给this.capacitythis.capacity = newCapacity;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();int curIndex = this.front;while (curIndex != this.tail) {sb.append(this.data[curIndex]);curIndex = (curIndex + 1) % this.data.length;}String result = sb.toString();return result.substring(0, result.length() - 1);}// 删除队首元素public Optional<T> removeFromHead() {// 判断是否为空if (this.front == this.tail) {Optional.empty();}Optional<T> result = Optional.of(this.data[this.front]);// 更新frontthis.front = (this.front + 1) % this.data.length;this.size--;System.out.println("出队：this.front=" + this.front + ",this.tail=" + this.tail);if (this.size <= this.capacity / 4 && this.capacity / 2 > 1) {resize(this.capacity / 2);}return result;}
}

3,对功能进行封装

public class CycleQueue<T> implements Queue<T> {private CycleArray<T> data;public CycleQueue() {this.data = new CycleArray<>();}@Overridepublic void enqueue(T ele) {this.data.addTail(ele);}@Overridepublic T dequeue() {return this.data.removeFromHead().orElse(null);}@Overridepublic T getFront() {return this.data.getFront();}@Overridepublic int getSize() {return this.data.getSize();}@Overridepublic boolean isEmpty() {return this.data.isEmpty();}
}