大家好,又见面了,我是你们的朋友全栈君。
一、队列简单介绍
队列是一种常用的数据结构之一,与之前的栈类似,不过队列是“先进先出”。队列有队头(front)和队尾(rear),数据从队尾进入队列,从队头出队列,队头(front)指向队列的第一个数据,队尾(rear)指向队列中的最后一个数据。
二、队列实现
队列有很多种,这里只是介绍最基本的实现,采用链式存储,也就是链式队列,与之前的链表存储形式一样,通过结点对象描述一个数据,结点对象包含具体数据和下一个结点的引用。
1、创建节点类
结点类就跟创建链表的结点类一样。
public class Node<T> {
// 存储的数据
private T data;
// 下一个节点的引用
private Node<T> next;
public Node(T data) {
this.data = data;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
}
2、创建队列类LinkQueue
在LinkQueue类中成员变量及方法如下:
成员变量:front、rear、size
对应的行为方法有:入队、出队、获取队列元素个数、判断队列是否为空。
public class LinkQueue<T> {
// 队头
private Node<T> front;
// 队尾
private Node<T> rear;
// 元素个数
private int size;
/** * 创建队列 */
public LinkQueue() {
rear = front = null;
}
/** * 入队列 * * @param data */
public void enQueue(T data) {
Node<T> node = new Node<T>(data);
if (isEmputy()) {
front = rear = node;
} else {
rear.setNext(node);
rear = node;
}
size++;
}
/** * 出队列 * * @return 返回数据 */
public T deQueue() {
if (isEmputy()) {
throw new RuntimeException("队列为空");
}
Node<T> delete = front;
front = delete.getNext();
delete.setNext(null);; // help GC
size--;
if (size == 0) {
// 删除掉最后一个元素时,front值已经为null,但rear还是指向该节点,需要将rear置为null
// 最后一个结点front和rear两个引用都没指向它,帮助GC处理该节点对象
rear = front;
}
return (T) delete.getData();
}
/** * 判断队列是否为空 * @return */
public boolean isEmputy() {
return (front == null && rear == null) ? true : false;
}
/** * 获取队列的元素个数 * @return */
public int size() {
return this.size;
}
}
当创建队列时队列中没有数据,front和rear的值都为null。当插入第一个数据时,将front和rear都指向第一个结点对象
后续在插入数据时就利用rear进行数据的插入。
3、测试
测试代码及结果如下:
public static void main(String[] args) {
LinkQueue<Integer> queue = new LinkQueue<Integer>();
queue.enQueue(1);
queue.enQueue(2);
queue.enQueue(3);
queue.enQueue(4);
System.out.println("size:" + queue.size());
System.out.println("出队列:" + queue.deQueue());
System.out.println("出队列:" + queue.deQueue());
System.out.println("出队列:" + queue.deQueue());
System.out.println("出队列:" + queue.deQueue());
System.out.println("删完重新添加==============");
queue.enQueue(11);
queue.enQueue(22);
queue.enQueue(33);
queue.enQueue(44);
System.out.println("size:" + queue.size());
System.out.println("出队列:" + queue.deQueue());
System.out.println("出队列:" + queue.deQueue());
System.out.println("出队列:" + queue.deQueue());
System.out.println("出队列:" + queue.deQueue());
}
size:4
出队列:1
出队列:2
出队列:3
出队列:4
删完重新添加==============
size:4
出队列:11
出队列:22
出队列:33
出队列:44
好了,java队列的简单实现就介绍到这里。
生活不只是敲代码,如果你或你身边的人喜欢摄影或者生活的点点滴滴,可以关注下面的公众号~
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/159026.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...