有什么好的书写网站,做视频点播网站的要求,个人网店系统,精品资源共享课网站建设目录 引出抽象数据类型#xff08;abstract data type,ADT#xff09;表ListArrayList,Vector, LinkedListArrayList手动实现与分析Vector的分析#xff08;线程安全#xff09;LinkedList 的手动实现与分析 栈stack—后进先出java中stack源码分析栈的应用#xff1a;检查… 目录 引出抽象数据类型abstract data type,ADT表ListArrayList,Vector, LinkedListArrayList手动实现与分析Vector的分析线程安全LinkedList 的手动实现与分析 栈stack—后进先出java中stack源码分析栈的应用检查程序括号是否闭合栈的应用后缀表达式 队列queue—先进先出Java中的queue队列的应用RabbitMq队列 总结 引出 1.抽象数据类型Abstract data type的概念 2.表listjava中的ArrayList和linkedlist以及vector的分析 3.栈stack的分析以及应用 4.队列queue的理解以及rabbitmq的应用
抽象数据类型abstract data type,ADT 抽象数据类型(abstract data type,ADT)是带有一组操作的一些对象的集合。抽象数据类型是数学的抽象在ADT的定义中没有地方提到关于这组操作是如何实现的任何解释。
诸如表、集合、图以及与它们各自的操作一起形成的这些对象都可以被看做是抽象数据类型这就像整数、实数、布尔数都是数据类型一样。整数、实数和布尔数各自都有与之相关的操作而抽象数据类型也是如此。
对于集合ADT,可以有像添加(add)、删除(remove)以及包含(contain)这样一些操作。当然也可以只要两种操作并(union)和查找(ind),这两种操作又在这个集合上定义了一种不同的ADT。 表List
ArrayList,Vector, LinkedList ArrayList 底层数据结构是数组使用动态数组实现。查询元素的性能较好时间复杂度为O(1)。插入和删除元素的性能较差需要移动其他元素时间复杂度为O(n)。不是线程安全的适用于单线程环境。可以通过指定初始容量来提高性能。 Vector 底层数据结构也是数组与ArrayList类似但是Vector是线程安全的。查询、插入和删除元素的性能与ArrayList相似。由于线程安全的特性Vector的性能通常比ArrayList略差。可以通过指定初始容量和增长因子来提高性能。 LinkedList 底层数据结构是双向链表。查询元素的性能较差需要遍历链表时间复杂度为O(n)。插入和删除元素的性能较好只需要修改相邻节点的指针时间复杂度为O(1)。不是线程安全的适用于单线程环境。适用于频繁插入和删除元素的场景。
综上所述如果需要频繁进行查询操作可以选择ArrayList或Vector如果需要频繁进行插入和删除操作可以选择LinkedList。如果需要线程安全可以选择Vector。另外ArrayList是最常用的一种集合类因为它在大多数场景下具有较好的性能和灵活性。
ArrayList手动实现与分析
Java进阶3——手动实现ArrayList 源码的初步理解分析 数组插入数据和删除数据的问题 Vector的分析线程安全 synchronize锁线程安全 LinkedList 的手动实现与分析
Java进阶7——手动实现LinkedList 内部node类的实现 增删改查的实现 toString方法 源码的初步理解 栈stack—后进先出 栈(stack)是限制插入和删除只能在一个位置上进行的表该位置是表的末端叫作栈的顶(top)。栈有时又叫作LIFO(后进先出)表。
对栈的基本操作有push(进栈)和pop(出栈)前者相当于插人后者则是删除最后插入的元素。最后插入的元素可以通过使用top例程在执行pop之前进行考查。对空栈进行的pop或top一般被认为是栈ADT中的一个错误。另一方面当运行push时空间用尽是一个实现限制但不是ADT错误。 java中stack源码分析 peek方法和pop方法
peek()方法用于查看栈顶元素但不会将其从栈中移除。它返回栈顶元素的值并不改变栈的状态。如果栈为空则会抛出EmptyStackException异常。pop()方法用于移除并返回栈顶元素。它将栈顶元素从栈中弹出并返回其值。如果栈为空则会抛出EmptyStackException异常。
这两个方法在栈的操作中非常常用。通过peek()方法我们可以查看栈顶元素的值而不改变栈的状态。通过pop()方法我们可以移除并获取栈顶元素的值同时改变栈的状态。 栈的应用检查程序括号是否闭合
在这种情况下一个有用的工具就是检验是否每件事情都能成对的程序。于是每一个右花括号、右方括号及右圆括号必然对应其相应的左括号。序列 [ ( ) ] 是合法的但 [ ( ] ) 是错误
这个简单的算法用到一个栈叙述如下
做一个空栈。读入字符直到文件结尾。如果字符是一个开放符号则将其推入栈中。如果字符是一个封闭符号则当栈空时报错。否则将栈元素弹出。如果弹出的符号不是对应的开放符号则报错。在文件结尾如果栈非空则报错。
import java.util.Stack;public class ParenthesesChecker {public static boolean checkParentheses(String code) {StackCharacter stack new Stack();for (int i 0; i code.length(); i) {char c code.charAt(i);if (c ( || c [ || c {) {stack.push(c);} else if (c ) || c ] || c }) {if (stack.isEmpty()) {return false;}char top stack.pop();if ((c ) top ! () || (c ] top ! [) || (c } top ! {)) {return false;}}}return stack.isEmpty();}public static void main(String[] args) {String code1 ((a b) * (c - d));String code2 ((a b) * (c - d);String code3 ((a b) * (c - d))};String code4 ((a b) * (c - d))];String code5 ((a b) * (c - d))};System.out.println(Code 1 is valid: checkParentheses(code1));System.out.println(Code 2 is valid: checkParentheses(code2));System.out.println(Code 3 is valid: checkParentheses(code3));System.out.println(Code 4 is valid: checkParentheses(code4));System.out.println(Code 5 is valid: checkParentheses(code5));}
}栈的应用后缀表达式
后缀表达式也称为逆波兰表达式是一种不使用括号来表示运算符优先级的数学表达式表示方法。在后缀表达式中运算符位于操作数之后。
例如将中缀表达式3 4 * 2 - 5转换为后缀表达式得到3 4 2 * 5 -。
后缀表达式的计算可以通过使用栈来实现。遍历后缀表达式当遇到操作数时将其入栈当遇到运算符时从栈中弹出两个操作数进行运算并将结果入栈。最后栈中剩下的元素即为计算结果。 队列queue—先进先出
像栈一样队列(queue)也是表。然而使用队列时插入在一端进行而删除则在另一端进行。Queue队列是一种常用的数据结构用于存储和操作元素。它遵循先进先出FIFO的原则即最先进入队列的元素最先被取出。 队列的基本操作是enqueue(入队)它是在表的末端叫作队尾(rear))插入一个元素和dequeue(出队)它是删除并返回在表的开头(叫作队头(front))的元素。
Java中的queue
Java提供了多种实现Queue接口的类常用的有以下几种
LinkedListLinkedList类实现了Queue接口可以用作队列的实现。它既可以作为队列使用也可以作为双端队列使用。ArrayDequeArrayDeque类也实现了Queue接口它是一个基于数组的双端队列。它可以在队列的两端进行插入和删除操作因此可以作为队列或栈使用。PriorityQueuePriorityQueue类实现了Queue接口它是一个优先级队列。元素按照优先级进行排序每次取出的元素都是优先级最高的。
这些类都实现了Queue接口因此具有类似的方法如offer()用于添加元素到队列尾部poll()用于取出队列头部的元素并删除它peek()用于查看队列头部的元素但不删除它isEmpty()用于判断队列是否为空size()用于获取队列的大小等。
import java.util.LinkedList;
import java.util.Queue;public class QueueExample {public static void main(String[] args) {QueueString queue new LinkedList();// 添加元素到队列尾部queue.offer(A);queue.offer(B);queue.offer(C);// 取出队列头部的元素并删除它String first queue.poll();System.out.println(取出的元素 first);// 查看队列头部的元素但不删除它String peek queue.peek();System.out.println(队列头部的元素 peek);// 判断队列是否为空boolean isEmpty queue.isEmpty();System.out.println(队列是否为空 isEmpty);// 获取队列的大小int size queue.size();System.out.println(队列的大小 size);}
}
队列的应用
当作业送交给一台行式打印机的时候它们就以到达的顺序被排列起来。因此被送往行式打印机的作业基本上被放到一个队列中。
事实上每一个实际生活中的排队都应该是一个队列。例如在一些售票口排列的队伍都是队列因为服务的顺序是先到先买票。
另一个例子是关于计算机网络的。有多种PC机的网络设置其中磁盘是放在一台叫作文件服务器(file server)的机器上的。使用其他计算机的用户是按照先到先使用的原则访问文件的因此其数据结构是一个队列。
进一步的例子如下
当所有的接线员忙不开的时候对大公司的呼叫一般都被放到一个队列中。在大型的大学里如果所有的终端都被占用由于资源有限学生们必须在一个等待表上签字登记。在终端上停留时间最长的学生将首先被强制离开而等待时间最长的学生则将是下一个被允许使用终端的用户。
RabbitMq队列 RabbitMQ基础1——生产者消费者模型 RabbitMQ简介 Docker版本的安装配置 RabbitMQ的helloworld 分模块构建 解决大量注册案例 https://www.rabbitmq.com/ RabbitMQ基础2——发布订阅/fanout模式 topic模式 rabbitmq回调确认 延迟队列死信设计 总结
1.抽象数据类型Abstract data type的概念 2.表listjava中的ArrayList和linkedlist以及vector的分析 3.栈stack的分析以及应用 4.队列queue的理解以及rabbitmq的应用
