一、队列简单介绍
队列是一种常用的数据结构之一，与之前的栈类似，不过队列是“先进先出”。队列有队头（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;
}
}
原文链接：https://www.qiquanji.com/post/8394.html
本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。
微信扫码关注
更新实时通知