JAVA队列

1. 队列(Queue)

2.1 概念

2.2 队列的使用

编辑

后入后出

和栈类似队列同样有 size（）和 empty（）方法

2.3 队列模拟实现

3. 出队列

1. 队列(Queue)

1.1 概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO

入队列：进行插入操作的一端称为队尾（Tail/Rear）

出队列：进行删除操作的一端称为队头（Head/Front）

1.2 队列的使用

在Java中，Queue是个接口，底层是通过链表实现的。

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

1.入队列

java">public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.offer(1);
q.offer(2);
q.offer(3);
q.offer(4);
q.offer(5); // 从队尾入队列
System.out.println(q.size());
System.out.println(q.peek()); // 获取队头元素
q.poll();
System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回
if(q.isEmpty()){
System.out.println("队列空");
}else{
System.out.println(q.size());
}
}

从中我们看到了先入的进入 队头 ，后入的进入 队尾

2.出队列

java">class Test2 {public static void main(String[] args) {Queue<Integer> q= new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);System.out.println("=========入队列=========");System.out.println(q.poll());System.out.println(q.poll());System.out.println(q.poll());System.out.println(q.poll());}
}

后入后出

java">
public class TestStudentSpeak {public static void main(String[] args) {Queue<Integer> q= new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);System.out.println("=========出队列=========");System.out.println(q.poll());System.out.println(q.poll());System.out.println("=========获取对头元素========");System.out.println(q.peek());System.out.println(q.peek());}}

3.查找队头元素

java">public class TestStudentSpeak {public static void main(String[] args) {Queue<Integer> q= new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);System.out.println("=========出队列=========");System.out.println(q.poll());System.out.println(q.poll());System.out.println("=========获取对头元素========");System.out.println(q.peek());System.out.println(q.peek());  System.out.println("======获取队列大小=======");System.out.println(q.size());System.out.println("=======判断队列是否为空=======");if (q.isEmpty()) {System.out.println("队列为空！");} else {System.out.println("队列不为空！");}}}

和栈类似队列同样有 size（）和 empty（）方法

1.3 队列模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有
两种：顺序结构和链式结构。

那队列的实现使用顺序结构还是链式结构好？

java">public class MyQueue implements IQueue {List<Integer> queue;public MyQueue() {queue= new LinkedList<>();}
}

用链表删除头节点的时间复杂度是 O(1)

顺序表删除头数据的，由于要扭动数据，所以时间复杂度达到了 O(N)

java">queue= new LinkedList<>();

所以建议选择链表

1.入队列

java">public boolean offer(int val) {queue.add(val);return true;
}

采用了双向链表的尾插功能

2. 出队列

java"> @Overridepublic int remove() {return queue.remove(0);}

采用双向链表的头删功能

java">@Overridepublic int peek() {return queue.get(0);}

3.查找

这里利用到链表的获取第一个元素的功能

java">@Override
public int size() {return queue.size();
}public boolean isEmpty() {return queue.isEmpty();
}

4.判空和判断大小

利用链表的 size() 和 isEmpty（） 两个方法爱实现我们的队列

java">public class Queue {
// 双向链表节点
public static class ListNode{
ListNode next;
ListNode prev;
int value;
ListNode(int value){
this.value = value;
}
}
ListNode first; // 队头
ListNode last; // 队尾
int size = 0;
// 入队列---向双向链表位置插入新节点
public void offer(int e){
ListNode newNode = new ListNode(e);
if(first == null){
first = newNode;
// last = newNode;
}else{
last.next = newNode;
newNode.prev = last;
// last = newNode;
}
last = newNode;
int value = 0;
if(first == null){
return null;
}else if(first == last){
last = null;
first = null;
}else{
value = first.value;
first = first.next;
first.prev.next = null;
first.prev = null;
}
--size;
return value;
}
// 获取队头元素---获取链表中第一个节点的值域
public int peek(){
if(first == null){
return null;
}
return first.value;
}
public int size() {
return size;
}
public boolean isEmpty(){
return first == null;
}
}