Java学数据结构（1）——抽象数据类型ADT & 表List、栈Stack和队列Qeue

短命女 2023-10-15 09:58 119阅读 0赞

#### 目录 ####

*  引出
 *  抽象数据类型（abstract data type,ADT）
 *  表List
 *   *  ArrayList,Vector, LinkedList
     *  ArrayList手动实现与分析
     *  Vector的分析（线程安全）
     *  LinkedList 的手动实现与分析
 *  栈stack—后进先出
 *   *  java中stack源码分析
     *  栈的应用：检查程序括号是否闭合
     *  栈的应用：后缀表达式
 *  队列queue—先进先出
 *   *  Java中的queue
     *  队列的应用
     *  RabbitMq队列
 *  总结

## 引出 ##

--------------------

1.抽象数据类型Abstract data type的概念；  
2.表list，java中的ArrayList和linkedlist以及vector的分析；  
3.栈stack的分析以及应用；  
4.队列queue的理解，以及rabbitmq的应用；

## 抽象数据类型（abstract data type,ADT） ##

![在这里插入图片描述][37b9b460dcc3436d86f5551a5de174ff.png]

抽象数据类型(abstract data type,ADT)是带有一组操作的一些对象的集合。抽象数据类型是数学的抽象；在ADT的定义中没有地方提到关于这组操作是如何实现的任何解释。

诸如表、集合、图以及与它们各自的操作一起形成的这些对象都可以被看做是抽象数据类型，这就像整数、实数、布尔数都是数据类型一样。整数、实数和布尔数各自都有与之相关的操作，而抽象数据类型也是如此。

对于集合ADT,可以有像添加(add)、删除(remove)以及包含(contain)这样一些操作。当然，也可以只要两种操作并(union)和查找(ind),这两种操作又在这个集合上定义了一种不同的ADT。

![在这里插入图片描述][4dbc79f7d0644171a356ae7f7bf221f6.png]

## 表List ##

### ArrayList,Vector, LinkedList ###

1.  ArrayList：
    
     *  底层数据结构是数组，使用动态数组实现。
     *  查询元素的性能较好，时间复杂度为O(1)。
     *  插入和删除元素的性能较差，需要移动其他元素，时间复杂度为O(n)。
     *  不是线程安全的，适用于单线程环境。
     *  可以通过指定初始容量来提高性能。
2.  Vector：
    
     *  底层数据结构也是数组，与ArrayList类似，但是Vector是线程安全的。
     *  查询、插入和删除元素的性能与ArrayList相似。
     *  由于线程安全的特性，Vector的性能通常比ArrayList略差。
     *  可以通过指定初始容量和增长因子来提高性能。
3.  LinkedList：
    
     *  底层数据结构是双向链表。
     *  查询元素的性能较差，需要遍历链表，时间复杂度为O(n)。
     *  插入和删除元素的性能较好，只需要修改相邻节点的指针，时间复杂度为O(1)。
     *  不是线程安全的，适用于单线程环境。
     *  适用于频繁插入和删除元素的场景。

综上所述，如果需要频繁进行查询操作，可以选择ArrayList或Vector；如果需要频繁进行插入和删除操作，可以选择LinkedList。如果需要线程安全，可以选择Vector。另外，ArrayList是最常用的一种集合类，因为它在大多数场景下具有较好的性能和灵活性。

### ArrayList手动实现与分析 ###

[Java进阶（3）——手动实现ArrayList & 源码的初步理解分析 & 数组插入数据和删除数据的问题][Java_3_ArrayList _ _ _]

![在这里插入图片描述][4052061514704a7ebe2054f68813cfec.png]

### Vector的分析（线程安全） ###

![在这里插入图片描述][d9e48d9550a442d58286f2d87d88dec6.png]

> synchronize锁：线程安全

![在这里插入图片描述][d039b8bc0f9f4458976827e1376813cb.png]

### LinkedList 的手动实现与分析 ###

[Java进阶（7）——手动实现LinkedList & 内部node类的实现 & 增删改查的实现 & toString方法 & 源码的初步理解][Java_7_LinkedList _ _node_ _ _ _ toString_ _]

![在这里插入图片描述][5d5c88c93d2f497eb2bdf7db1741e1d5.png]

## 栈stack—后进先出 ##

![在这里插入图片描述][e39da02758cf4956a43a551ddc96789e.png]

栈(stack)是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫作栈的顶(top)。栈有时又叫作LIFO(后进先出)表。

对栈的基本操作有push(进栈)和pop(出栈)，前者相当于插人，后者则是删除最后插入的元素。最后插入的元素可以通过使用top例程在执行pop之前进行考查。对空栈进行的pop或top一般被认为是栈ADT中的一个错误。另一方面，当运行push时空间用尽是一个实现限制，但不是ADT错误。

![在这里插入图片描述][4b5d798977be4999b3c4e69b4069dc0e.png]

### java中stack源码分析 ###

![在这里插入图片描述][1c471a14179b484c8a347d1998b79ec3.png]

peek方法和pop方法

*  peek()方法用于查看栈顶元素，但不会将其从栈中移除。它返回栈顶元素的值，并不改变栈的状态。如果栈为空，则会抛出EmptyStackException异常。
 *  pop()方法用于移除并返回栈顶元素。它将栈顶元素从栈中弹出，并返回其值。如果栈为空，则会抛出EmptyStackException异常。

这两个方法在栈的操作中非常常用。通过peek()方法，我们可以查看栈顶元素的值，而不改变栈的状态。通过pop()方法，我们可以移除并获取栈顶元素的值，同时改变栈的状态。

![在这里插入图片描述][8a1567e8fa804faf8353c10f24a6f488.png]

### 栈的应用：检查程序括号是否闭合 ###

在这种情况下，一个有用的工具就是检验是否每件事情都能成对的程序。于是，每一个右花括号、右方括号及右圆括号必然对应其相应的左括号。序列 \[ ( ) \] 是合法的，但 \[ ( \] ) 是错误

这个简单的算法用到一个栈，叙述如下：

做一个空栈。读入字符直到文件结尾。如果字符是一个开放符号，则将其推入栈中。如果字符是一个封闭符号，则当栈空时报错。否则，将栈元素弹出。如果弹出的符号不是对应的开放符号，则报错。在文件结尾，如果栈非空则报错。

import java.util.Stack;
    
    public class ParenthesesChecker {
        
        public static boolean checkParentheses(String code) {
        
            Stack<Character> 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 -"。

后缀表达式的计算可以通过使用栈来实现。遍历后缀表达式，当遇到操作数时，将其入栈；当遇到运算符时，从栈中弹出两个操作数进行运算，并将结果入栈。最后，栈中剩下的元素即为计算结果。

![在这里插入图片描述][8051da48bf26486881605809923d5d33.png]

![在这里插入图片描述][840fafdee03e4b6f9b104e42270c722f.png]

## 队列queue—先进先出 ##

像栈一样，队列(queue)也是表。然而，使用队列时插入在一端进行而删除则在另一端进行。Queue（队列）是一种常用的数据结构，用于存储和操作元素。它遵循先进先出（FIFO）的原则，即最先进入队列的元素最先被取出。

![在这里插入图片描述][eec6ff786d7c44fc998f46e2d58fb683.png]

队列的基本操作是enqueue(入队)，它是在表的末端（叫作队尾(rear))插入一个元素，和dequeue(出队)，它是删除（并返回）在表的开头(叫作队头(front))的元素。

### Java中的queue ###

Java提供了多种实现Queue接口的类，常用的有以下几种：

1.  LinkedList：LinkedList类实现了Queue接口，可以用作队列的实现。它既可以作为队列使用，也可以作为双端队列使用。
2.  ArrayDeque：ArrayDeque类也实现了Queue接口，它是一个基于数组的双端队列。它可以在队列的两端进行插入和删除操作，因此可以作为队列或栈使用。
3.  PriorityQueue：PriorityQueue类实现了Queue接口，它是一个优先级队列。元素按照优先级进行排序，每次取出的元素都是优先级最高的。

这些类都实现了Queue接口，因此具有类似的方法，如offer()用于添加元素到队列尾部，poll()用于取出队列头部的元素并删除它，peek()用于查看队列头部的元素但不删除它，isEmpty()用于判断队列是否为空，size()用于获取队列的大小等。

import java.util.LinkedList;
    import java.util.Queue;
    
    public class QueueExample {
        
        public static void main(String[] args) {
        
            Queue<String> 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 + 分模块构建 & 解决大量注册案例][RabbitMQ_1_ _ RabbitMQ_ _ Docker_ _ RabbitMQ_helloworld _ _ _]

[https://www.rabbitmq.com/][https_www.rabbitmq.com]

![在这里插入图片描述][3061aa903cfc40db8dcfe6df6947826c.png]

> [RabbitMQ基础（2）——发布订阅/fanout模式 & topic模式 & rabbitmq回调确认 & 延迟队列（死信）设计][RabbitMQ_2_fanout_ _ topic_ _ rabbitmq_ _]

![在这里插入图片描述][1d70379045e4403e943d8025c87811bc.png]

--------------------

## 总结 ##

[37b9b460dcc3436d86f5551a5de174ff.png]: https://img-blog.csdnimg.cn/37b9b460dcc3436d86f5551a5de174ff.png
[4dbc79f7d0644171a356ae7f7bf221f6.png]: https://img-blog.csdnimg.cn/4dbc79f7d0644171a356ae7f7bf221f6.png
[Java_3_ArrayList _ _ _]: https://blog.csdn.net/Pireley/article/details/132326323
[4052061514704a7ebe2054f68813cfec.png]: https://img-blog.csdnimg.cn/4052061514704a7ebe2054f68813cfec.png
[d9e48d9550a442d58286f2d87d88dec6.png]: https://img-blog.csdnimg.cn/d9e48d9550a442d58286f2d87d88dec6.png
[d039b8bc0f9f4458976827e1376813cb.png]: https://img-blog.csdnimg.cn/d039b8bc0f9f4458976827e1376813cb.png
[Java_7_LinkedList _ _node_ _ _ _ toString_ _]: https://blog.csdn.net/Pireley/article/details/132459677
[5d5c88c93d2f497eb2bdf7db1741e1d5.png]: https://img-blog.csdnimg.cn/5d5c88c93d2f497eb2bdf7db1741e1d5.png
[e39da02758cf4956a43a551ddc96789e.png]: https://img-blog.csdnimg.cn/e39da02758cf4956a43a551ddc96789e.png
[4b5d798977be4999b3c4e69b4069dc0e.png]: https://img-blog.csdnimg.cn/4b5d798977be4999b3c4e69b4069dc0e.png
[1c471a14179b484c8a347d1998b79ec3.png]: https://img-blog.csdnimg.cn/1c471a14179b484c8a347d1998b79ec3.png
[8a1567e8fa804faf8353c10f24a6f488.png]: https://img-blog.csdnimg.cn/8a1567e8fa804faf8353c10f24a6f488.png
[8051da48bf26486881605809923d5d33.png]: https://img-blog.csdnimg.cn/8051da48bf26486881605809923d5d33.png
[840fafdee03e4b6f9b104e42270c722f.png]: https://img-blog.csdnimg.cn/840fafdee03e4b6f9b104e42270c722f.png
[eec6ff786d7c44fc998f46e2d58fb683.png]: https://img-blog.csdnimg.cn/eec6ff786d7c44fc998f46e2d58fb683.png
[RabbitMQ_1_ _ RabbitMQ_ _ Docker_ _ RabbitMQ_helloworld _ _ _]: https://blog.csdn.net/Pireley/article/details/132178423
[https_www.rabbitmq.com]: https://www.rabbitmq.com/
[3061aa903cfc40db8dcfe6df6947826c.png]: https://img-blog.csdnimg.cn/3061aa903cfc40db8dcfe6df6947826c.png
[RabbitMQ_2_fanout_ _ topic_ _ rabbitmq_ _]: https://blog.csdn.net/Pireley/article/details/132204466
[1d70379045e4403e943d8025c87811bc.png]: https://img-blog.csdnimg.cn/1d70379045e4403e943d8025c87811bc.png