java实现队列的链式存储
程序员文章站
2022-06-05 14:47:14
...
队列:操作受限制的线性表,只能在一端删除元素,另一端添加元素。
特点:先进先出
代码实现如下:
package 数据结构;
public class ListQueue {
private Node rear = new Node(); // 尾指针
private Node front = new Node(); // 头指针
class Node{
String value;
Node next;
}
/**
* 进队:在队尾插入
* @param value
* @return
*/
public boolean enQueue(String value) {
Node n = new Node();
n.value = value;
if(rear.next == null) { // 队列为空
rear.next = n; // 更新队尾和队首指针
front.next = n;
return true;
}
// 队列有元素
rear.next.next = n; // 插入到末尾
rear.next = n; // 更新队尾指针
return true;
}
/**
* 出队:从队首删除元素
* @return
*/
public String deQueue() {
if(rear.next == null) { // 队列为空
return null;
}
String value = null;
if(rear.next == front.next) {
value = front.next.value; // 队列中有一个元素
rear.next = null;
front.next = null;
return value;
}
// 获取队首元素的值
value = front.next.value; // 队列中有两个或两个以上的元素
// 更新队首指针
front.next = front.next.next;
return value;
}
/**
* 判断队列是否为空
* @return
*/
public boolean isEmpty() {
return rear.next == null;
}
public static void main(String[] args) {
ListQueue queue = new ListQueue();
System.out.println(queue.isEmpty()); // 判读队列是否为空
System.out.println(queue.enQueue("孙悟空")); // 将元素在队尾进队
System.out.println(queue.enQueue("唐僧"));
System.out.println(queue.enQueue("猪八戒"));
System.out.println(queue.isEmpty()); // 判读队列是否为空
System.out.println(queue.deQueue()); // 将元素在队首出队
System.out.println(queue.deQueue()); // 将元素在队首出队
System.out.println(queue.deQueue()); // 将元素在队首出队
System.out.println(queue.isEmpty()); // 判读队列是否为空
}
}
运行结果如下
true
true
true
true
false
孙悟空
唐僧
猪八戒
true