一、概念
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(FirstIn First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头(Head/Front)
二、 队列的使用
在Java中,Queue是个接口,底层是通过链表实现的。
(一)常用方法
1.入队
public class TestDemo1 {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
System.out.println(queue);
}
}
2.出队
public class TestDemo1 {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
System.out.println(queue);
queue.poll();
queue.poll();
System.out.println(queue);
}
}
结果剩下 [3,4]
3、获取队头元素
public class TestDemo1 {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
int s = queue.peek();//获取队头元素但是不删除
System.out.println(s);
}
}
运行结果为 1
4、判断队列是否为空
public class TestDemo1 {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
boolean b1 = queue.isEmpty();
System.out.println(b1);
}
}
结果为:false
5、获取队列中有效元素的个数
public class TestDemo1 {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
System.out.println(queue.size());
}
}
结果为:4
四、队列的模拟实现
public class MyQueue {
static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode tail;
public int usedSize;
public void offer(int val) {
ListNode node = new ListNode(val);
if (head == null) {
head = node;
tail = node;
} else {
tail.next = node;
tail = tail.next;
}
usedSize++;
}
public int poll() {
if (empty()) {
return -1;
}
int ret = head.val;
head = head.next;
if (head == null) {
tail = null;
}
usedSize--;
return ret;
}
public int peek() {
if (empty()) {
return -1;
}
return head.val;
}
public boolean empty() {
return usedSize==0;
}
public int getUsedSize() {
return usedSize;
}
}
标签:queue,head,val,offer,队列,Queue,int,数据结构,public
From: https://blog.csdn.net/weixin_72703349/article/details/142305523