数据结构Java版（3）——队列Queue
一、概念
队列也是一种线性数据结构，最主要的特点是入队列顺序和出队列顺序是相同的，操作时在队尾入队，在队首出队。在Java中给我们提供了一个泛型队列——Queue，其中最常用的方法有：
- void offer()：入队
- E poll()：出队
- E peek()：查看队首元素
- int size()：返回队中元素
- boolean isEmpty()：检查队列是否为空
二、队列的实现
因为队列也是一种线性结构，所以这里可以利用之前我们写的数组，这里可以用接口的方式来实现我们自己的顺序队列，下面进行代码演示。
队列的接口
public interface Queue_i<Elem> {
public abstract boolean offer(Elem e);
public abstract Elem poll();
public abstract Elem peek();
public abstract int getLength();
public abstract boolean isEmpty();
public abstract Elem peekLast();
}通过接口的方式，对queue中的方法进行重写，实现功能
public class ArrQueue<E> implements Queue_i<E>{
private MyArray<E> queue;
private int length;
public ArrQueue() {
this.queue = new MyArray<>(16);
length = 0;
}
@Override
public boolean offer(E e) {
try{
this.queue.add(e);
}catch (Exception exception){
return false;
}
length++;
return true;
}
@Override
public E poll() {
if (isEmpty()) return null;
E e;
try{
e = this.queue.removeByIndex(0);
}catch (Exception exception){
return null;
}
this.length--;
return e;
}
@Override
public E peek() {
if (isEmpty()) return null;
E e;
try{
e = this.queue.getValueByIndex(0);
}catch (Exception exception){
return null;
}
return e;
}
@Override
public int getLength() {
return this.length;
}
@Override
public boolean isEmpty() {
return getLength()==0;
}
@Override
public E peekLast() {
if (isEmpty()) return null;
E e;
try{
e = this.queue.getValueByIndex(this.length-1);
}catch (Exception exception){
return null;
}
return e;
}
}对自己的顺序队列进行代码测试
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class testMyQueue {
public static void test(Queue_i<Integer> queue, List<Integer> list){
Random random = new Random();
for(int i = 0;i < 10;i++){
queue.offer(random.nextInt(1000));
System.out.println(queue.peekLast()+"——现在还有"+queue.getLength()+"个元素");
}
Integer temp;
while ((temp = queue.poll())!=null){
list.add(temp);
}
System.out.println();
}
public static void main(String[] args) {
List<Integer> list = new ArrayList();
Queue_i<Integer> queue = new ArrQueue<>();
test(queue,list);
for (Integer i:list) {
System.out.println(i);
}
}
}输出结果：
通过观察可知，队列具有先进先出的特点。
三、循环队列（这里逻辑上是错的——2024-1-19）
不要看
因为顺序队列每次出队时都要把所有元素向前移动一位，时间复杂度高，但如果用双指针，则会导致假溢出现象出现，为了解决这个问题，我们提出了循环队列这个概念。
通过接口的方式，对queue中的方法进行重写，实现功能
public class LoopQueue<T> implements Queue_i<T>{
private MyArray<T> queue;
private int front;
private int rear;
public LoopQueue() {
this.queue = new MyArray<>(17);
this.front = 0;
this.rear = 0;
}
@Override
public boolean offer(T t) {
try{
queue.add(rear, t);
}catch (Exception e){
return false;
}
rear = (rear + 1)%queue.getSize();
return true;
}
@Override
public T poll() {
if(isEmpty()) return null;
T t;
try{
t = queue.removeByIndex(front);
}catch (Exception e){
return null;
}
front = (front+1)%queue.getSize();
return t;
}
@Override
public T peek() {
if(isEmpty()) return null;
T t;
try{
t = queue.getValueByIndex(front);
}catch (Exception e){
return null;
}
return t;
}
@Override
public int getLength() {
return (rear + queue.getSize() - front)%queue.getSize();
}
@Override
public boolean isEmpty() {
return rear==front;
}
@Override
public T peekLast() {
if(isEmpty()) return null;
T t;
try{
t = queue.getValueByIndex((rear - 1 + queue.getSize())%queue.getSize());
}catch (Exception e){
return null;
}
return t;
}
}这里需要注意的时，因为循环队列两个指针能循环使用的原因，我们判断队列是否为空和为满时会出现冲突，即两个条件都是rear==front，为了解决这个问题，我们牺牲了一个空间，以区别为空和为满，则为空条件不变，为满条件变为（rear+1）%总容量==front，这个就导致我们在数组扩容时出现问题，这里有两个解决方案，一是将数组中的方法进行重写，二是将数组的长度初始值设为一，以填补浪费掉的空间。这里还有一个注意点是要重新数组中的删除方法，仅删除不调动位置。
对循环队列的测试
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class testMyQueue {
public static void test(Queue_i<Integer> queue, List<Integer> list){
Random random = new Random();
for(int i = 0;i < 10;i++){
queue.offer(random.nextInt(1000));
System.out.println(queue.peekLast()+"——现在还有"+queue.getLength()+"个元素");
}
Integer temp;
while ((temp = queue.poll())!=null){
list.add(temp);
}
System.out.println();
}
public static void test(Queue_i<Integer> queue){
List<Integer> list = new ArrayList();
Random random = new Random();
for(int i = 0;i < 20;i++){
queue.offer(random.nextInt(1000));
System.out.println(queue.peekLast()+"——现在还有"+queue.getLength()+"个元素");
}
Integer temp;
while ((temp = queue.poll())!=null){
list.add(temp);
}
for (Integer i:list) {
System.out.println(i);
}
}
public static void main(String[] args) {
List<Integer> list = new ArrayList();
Queue_i<Integer> queue = new ArrQueue<>();
Queue_i<Integer> queue2 = new LoopQueue<>();
test(queue2);
// test(queue,list);
// for (Integer i:list) {
// System.out.println(i);
// }
}
}输出结果：
四、队列可以解决的问题
1.进行异步操作，在多线程编程时减少线程阻塞现象
这里具体操作可以去看之前一篇浏览器事件循环的文字，其中对浏览器的异步操作进行了详细讲解，其中就用到了队列的知识：
原文地址：https://blog.csdn.net/2301_77523019/article/details/135693491
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！