1 概述 队列是一种先进先出的数据结构,本文将基于链表实现一种简单的队列,主要功能包括入队,出队。
2 代码实现
package com.niuniu.studyalgorithm;
import java.util.Iterator;
import java.util.Spliterator;
import java.util.function.Consumer;
/**
* @author 002991
* 基于链表的自定义队列
*/
public class ChainQueue- implements Iterable
- {
/**
* 指向最早添加的节点的链接
*/
private Node first;
/**
* 指向最近添加的节点的链接
*/
private Node last;
/**
* 节点的数量
*/
private int size;
/**
* 判断队列是否为空
* @return
*/
public boolean isEmpty(){
return first == null;
}/**
* 获取队列的长度
* @return
*/
public int size(){
return size;
}/**
* 向队列中添加元素
* @param item
*/
public void enqueue(Item item){
Node oldLast = last;
last = new Node();
last.item = item;
last.next = null;
if(isEmpty()){
first = last;
}else{
oldLast.next = last;
}
size++;
}/**
* 从队列中获取元素
* @return
*/
public Item dequeue(){
Item item = first.item;
first = first.next;
if(isEmpty()){
last = null;
}
size--;
return item;
}/**
* 自定义节点
*/
private class Node{
Item item;
Node next;
}//下面是省略Iterator的实现@Override
public Iterator
- iterator() {
return new ListIterator();
}@Override
public void forEach(Consumer super Item> action) {}@Override
public Spliterator
- spliterator() {
return null;
}private class ListIterator implements Iterator
- {
private Node current = first;
@Override
public boolean hasNext() {
return current != null;
}@Override
public Item next() {
Item item = current.item;
current = current.next;
return item;
}@Override
public void remove() {}@Override
public void forEachRemaining(Consumer super Item> action) {}
}
}
3 总结 【算法|Java算法系列3--基于链表自定义队列】此种队列有以下好处:
(1)所需空间总是和集合大小成正比
(2)操作所需时间总是和集合大小无关
推荐阅读
- Java|Java基础——数组
- 人工智能|干货!人体姿态估计与运动预测
- java简介|Java是什么(Java能用来干什么?)
- Java|规范的打印日志
- Linux|109 个实用 shell 脚本
- 程序员|【高级Java架构师系统学习】毕业一年萌新的Java大厂面经,最新整理
- 分析COMP122 The Caesar Cipher
- Spring注解驱动第十讲--@Autowired使用
- SqlServer|sql server的UPDLOCK、HOLDLOCK试验
- jvm|【JVM】JVM08(java内存模型解析[JMM])