1.链队列的特点:
链队列其实就是单链表,只不过它是先进先出的单链表,为了实现方便,程序中设置了队头(front),队尾(rear)两个指针。
2. Java使用链表实现队列:
//结点类,包含结点的数据和指向下一个节点的引用
public class Node<E> {
private E data; // 数据域
private Node<E> next; // 指针域保存着下一节点的引用
public Node() {
}
public Node(E data) {
this.data = data;
}
public Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
public Node<E> getNext() {
return next;
}
public void setNext(Node<E> next) {
this.next = next;
}
}
// Java实现链队列
public class LinkedQueue<T> {
private Node<T> front; // 记住队头结点
private Node<T> rear; // 记住队尾结点
private int size; // 记住链表长度
public LinkedQueue() {
front = rear = null;
size = 0;
}
// 将元素追加到队列尾部
public boolean enqueue(T data) {
Node<T> newNode = new Node<T>(data);
if (isEmpty()) { // 判断队列是否为空
front = rear = newNode;
} else {
rear.setNext(newNode); // 将新进来的结点设置为尾结点
rear = newNode;
}
size++;
System.out.println(data + "入队..");
return true;
}
// 队列头部的第一个元素出队
public T dequeue() {
T data = null;
if (isEmpty()) {
System.out.println("队列为空,无法出队..");
} else {
if (front.getNext() == null) { // 队列中只有一个结点
rear = null;
}
data = front.getData();
front = front.getNext(); // 将原队头的下一个结点设置为队头
System.out.println(data + "出队..");
size--;
}
return data;
}
// 获取链队列的长度
public int size() {
return size;
}
// 判断链队列是否为空
public boolean isEmpty() {
return size == 0;
}
// 清空链队列
public void clear() {
front = rear = null;
size = 0;
}
// 打印队列中的元素
public void display() {
if (!isEmpty()) {
Node<T> nextNode = front;
for (int i = 0; i < size(); i++) {
System.out.print(" " + nextNode.getData());
nextNode = nextNode.getNext();
}
}
}
// 测试方法
public static void main(String[] args) {
LinkedQueue<String> queue = new LinkedQueue<String>();
queue.enqueue("张三");
queue.dequeue();
queue.dequeue();
queue.enqueue("李四");
queue.enqueue("王五");
queue.enqueue("赵六");
queue.dequeue();
queue.enqueue("田七");
queue.dequeue();
queue.enqueue("周八");
System.out.println("队列中元素个数为: " + queue.size());
System.out.print("打印队列中的元素: ");
queue.display();
}
}
3. 链队列和循环队列比较:
1.) 时间上:循环队列事先申请好空间,使用期间不释放。链队列每次申请和释放结点存在一些时间开销,如果入队出队操作频繁,链队列性能稍差。
2.) 空间上:循环队列必须有一个固定长度,所以就有了存储元素个数和空间浪费的问题。链队列不存在这个问题,所以在空间上更为灵活。
4. 什么时候使用链队列:
1.) 在可以确定队列长度最大值的情况下,建议用循环队列。
2.) 如果无法预估队列的长度,则用链队列 。
分享到:
相关推荐
大话数据结构 .pptx
接着,书中会深入讲解存储层次结构,从CPU缓存到主内存,再到外部存储设备,阐述如何通过缓存策略优化数据访问速度。此外,还会涉及虚拟内存管理,解释如何在物理内存不足时,利用硬盘空间作为虚拟内存,确保系统的...
《大话数据分析:Tableau数据可视化实战》的数据集是一份重要的资源,对于想要学习和提升Tableau数据可视化技能的人来说极具价值。Tableau是一款强大的商业智能工具,它允许用户通过直观的拖放界面来探索和可视化...
大话存储2:存储系统架构与底层原理极限剖析》内容简介:网络存储是一个涉及计算机硬件以及网络协议/技术、操作系统以及专业软件等各方面综合知识的领域。目前国内阐述网络存储的书籍少之又少,大部分是国外作品,对...
大话存储:存储系统底层架构原理极限剖析(终极版)第4部分 大话存储:存储系统底层架构原理极限剖析(终极版)第4部分
大话数据结构
大数据也可以定义为来自各种来源的大量非结构化或结构化数据。从学术角度而言,大数据的出现促成广泛主题的新颖研究。这也导致各种大数据统计方法的发展。大数据并没有统计学的抽样方法;它只是观察和追踪发生的事情...
大话存储:存储系统底层架构原理极限剖析(终极版)第3部分 大话存储:存储系统底层架构原理极限剖析(终极版)第3部分大话存储:存储系统底层架构原理极限剖析(终极版)第3部分
3. 存储系统的基础技术:讨论了计算机IO基本概念、硬盘物理结构、盘片数据结构和工作原理等基础知识。 4. RAID技术:书中有对七种常见RAID技术原理的详细分析,并对性能细节进行了对比。 5. 磁盘阵列技术:涉及...
个人自用
Android之大话设计模式——:抽象工厂模式借鉴.pdf
基于《大话数据结构》进行数据结构的学习
大话存储:存储系统底层架构原理极限剖析(终极版)_张冬2015.01_P989
数据结构是组织和存储数据的方式,以便于高效地访问和修改。C和C++提供了多种内置数据结构,如数组、链表、栈、队列、哈希表、树等。每种数据结构都有其特定的用途和操作效率: 1. **数组**:一组相同类型的元素...
《大话存储终极版》是IT领域内一本深受读者喜爱的存储技术图书,作者冬瓜哥(张冬)以其通俗易懂的语言,深入浅出地介绍了存储领域的诸多知识。这本书对于初学者来说是一份非常宝贵的资源,可以帮助他们快速入门并...
在计算机系统中,文件系统、块存储和文件存储是存储数据的三种主要方式。它们之间存在一些区别,主要体现在性能、可扩展性和灵活性等方面。首先,让我们了解一下文件系统的概念。文件系统是一种用于管理计算机文件...
数据结构是计算机科学中的一个重要概念,它主要研究如何组织和存储数据,以便可以高效地访问和修改这些数据。数据结构的选择对于算法的效率有着直接的影响。本次内容将围绕“栈”、“队列”、“树”以及“二叉树”等...
大话Oracle RAC:集群、高可用性、备份与恢复(带目录清晰中文完整版)