「java使用链表实现队列」编写实现队列的例程,使用链表
本篇文章给大家谈谈java使用链表实现队列，以及编写实现队列的例程,使用链表对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
队列的 2 种实现方式
队列，是一个线性表，和数组，栈，链表类似。队列和栈类似，戏称“边吃边拉”。即 FIFO。
队列和栈还有一个不同，栈只需维护一个栈顶指针，而队列需要维护 2 个指针，队首和队尾。
队列可以使用数组实现，例如 Java 类库的 LinkedBlockingQueue，也可以使用数组实现，例如 Java 的 ArrayBlockingQueue。这里我们讨论数组的实现。
通常使用数组实现，会使用循环数组，也称 ringBuffer，好处是不用 copy 数组进行迁移，另外，传统实现，如果数组满了，就不能再继续插入了，即使前面还有空间，因此就需要刚刚说的 copy 进行迁移。下面是最简单的一个 Java 循环数组实现。
这个是一个标准的实现，但是存在一个问题：如果队列长度是 8，那么就只能存储 7 个元素。原因下面分析。
这个图，表示队列为空，因为 put 指针和 get 指针，指向了同一个槽位。get 指针不能够再继续移动。
那如果表示满了呢？
这个图，get 指针在 5 槽位，put 指针 4 槽位，put 指针不能再继续移动，否则会覆盖 5 槽位的值。
由此我们得到公式：
isEmpty = put == get;
ifFull = (put + 1) % n == get;
所以，put 一定比 get 少在一个槽位。
当 put 在 7 这个槽位，get 在 0 这个槽位，他还能继续放入元素在 7 这个位置吗？答案是不能，因为我们通过 put + 1 % n == get 这个公式计算，如果 在 7 个槽位加入了元素，那么 put 指针就会变成 0，问题来了，put 是 0 ，get 也是0。
而 isEmpty 的公式是 put == get。这个时候，就会发生判断错误：原本是满的，却判断是空的。
所以，这个实现导致必须有一个空位。当然，我们也可以把槽位加1，也就是把数组长度加 1，避免实际长度不符合预期，也可以避免这个问题。
通过上面的分析，我们知道了，如果不加上1，将导致 isEmpty 判断错误。原因是如果 put 和 get 指针重合，我们无法区分到底是 满了 还是 空了。因为我们判断是满还是空，利用的是指针。
如果不使用指针呢？使用一个计算器，例如，添加一个元素，计算器 + 1， 删除一个元素，计算器 - 1. 是否可以呢？答案是可以的.
下面是具体实现：
我们判断 ifEmpty ，使用 size == 0 判断；判断 isFull，使用 size == n 判断，这样就解决了这个问题。
队列可以使用链表和数组实现，通常使用使用数组实现，效率高，不用搬移。使用循环数组，需要考虑的是 ifFull 判断和 isEmpty 判断。
这里我建议使用 size 这种方式，而不是 + 1 这种方式，为什么呢？使用 size 这种方式，我们可以利用 运算来快速计算下标——只要用户指定的队列长度是 2 的幂次方。
如果使用 + 1 的方式，即使用户指定的队列长度是 2 的幂次方，也无法使用 运算快速获取下标。
当然，我们也可以根据用户指定的队列长度是否为2 的幂次方，来觉得到底是使用 size 方式，还是使用 + 1 方式。
JAVA里链队怎么移动指针
循环条件或者判断语句。
为了和队列的定义保持一致，所以要指明尾指针，链式队列只是队列的一种实现方式，还要把握住队列的本质，至于尾指针指向是尾结点还是尾结点的下一个结点，这个只是实现的一点区别，没有强制的要求。要根据自己的具体实现选择，不同的应用这两种会有些微小的区别，比如循环条件，判空等。
判断依据是根据栈和堆解决，栈是后进先出，用链表的话在头部操作即可，没必要再加个尾指针，队列是先进先出，头尾都要有指针记忆位置，但是循环链表的话，尾节点的下一个便是头结点，所以只要有个尾指针即可，头指针省略不用。
java中的队列用什么实现
其内部是用链表实现的。
class ABT//一个链表类
{
class NodeT//内部类，表示链表中的一个节点
{
NodeT prev;//前一节点
NodeT next; //后一节点
T abc; //当前节点的元素
}
}
大体如上，具体的功能自行添加。
Java使用LinkedList来模拟一个队列(先进先出的特性)
import java.util.LinkedList;
public class Demo01 {
private LinkedListObject linkedList;
public Demo01() {
linkedList = new LinkedListObject();
}
public void put(Object object) {
linkedList.add(object);
}
public Object get() {
Object object = null;
if (linkedList.size() != 0) {
object = linkedList.get(0);
linkedList.remove(0);
}
return object;
}
public boolean isEmpty() {
if (linkedList.size() != 0) {
return true;
} else {
return false;
}
}
public static void main(String[] args) {
Demo01 demo01 = new Demo01();
demo01.put("1");
demo01.put("2");
System.out.println(demo01.get());
System.out.println(demo01.get());
System.out.println(demo01.isEmpty());
}
}
结果：
1
2
false
关于java使用链表实现队列和编写实现队列的例程,使用链表的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
发布于：2022-12-04，除非注明，否则均为原创文章，转载请注明出处。