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

这篇具有很好参考价值的文章主要介绍了Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

引出


1.抽象数据类型Abstract data type的概念;
2.表list,java中的ArrayList和linkedlist以及vector的分析;
3.栈stack的分析以及应用;
4.队列queue的理解,以及rabbitmq的应用;文章来源地址https://www.toymoban.com/news/detail-669962.html

抽象数据类型(abstract data type,ADT)

Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list

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

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

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

Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list

表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学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list

Vector的分析(线程安全)

Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list

synchronize锁:线程安全

Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list

LinkedList 的手动实现与分析

Java进阶(7)——手动实现LinkedList & 内部node类的实现 & 增删改查的实现 & toString方法 & 源码的初步理解

Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list

栈stack—后进先出

Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list

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

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

Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list

java中stack源码分析

Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list

peek方法和pop方法

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

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

Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list

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

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

这个简单的算法用到一个栈,叙述如下:

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

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 -"。

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

Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list

Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list

队列queue—先进先出

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

Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list

队列的基本操作是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 + 分模块构建 & 解决大量注册案例

https://www.rabbitmq.com/

Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list

RabbitMQ基础(2)——发布订阅/fanout模式 & topic模式 & rabbitmq回调确认 & 延迟队列(死信)设计

Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue,Java,数据结构,java,list


总结

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

到了这里,关于Java学数据结构(1)——抽象数据类型ADT & 表List、栈Stack和队列Qeue的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构学习记录——什么是堆(优先队列、堆的概念、最大堆最小堆、优先队列的完全二叉树表示、堆的特性、堆的抽象数据类型描述)

    目录 优先队列 若采用数组或链表实现优先队列  数组 链表 有序数组 有序链表 总结 若采用二叉搜索树来实现优先队列 最大堆 堆的概念 优先队列的完全二叉树表示 堆的两个特性  结构性 有序性 【例】最大堆和最小堆 【例】不是堆 堆的抽象数据类型描述 优先队列 (Prio

    2024年02月02日
    浏览(51)
  • Python中List类型数据结构广泛应用于各种场景中。然而,在数据分析和可视化过程中,经常需要将List转换为Pandas的DataFrame对象。那么如何将...

    Python中List类型数据结构广泛应用于各种场景中。然而,在数据分析和可视化过程中,经常需要将List转换为Pandas的DataFrame对象。那么如何将List转换为DataFrame对象呢?本文将介绍如何使用Python中Pandas库将List转换为DataFrame,并进一步将其转换为字符串。 将Python List转换为Pandas D

    2024年02月15日
    浏览(52)
  • java -- 简单的数据结构、List接口和Collections类

    数据结构 : 数据用什么样的方式组合在一起。 数据存储的常用结构有:栈、队列、数组、链表 栈: stack ,又称堆栈,它是运算受限的线性表,其限制是仅允许在标的一端进行插入和删除操作,不允许在其他任何位置进行添加、查找、删除等操作。 采用该结构的集合,对元素

    2023年04月10日
    浏览(52)
  • Java02-迭代器,数据结构,List,Set ,Map,Collections工具类

    目录 什么是遍历? 一、Collection集合的遍历方式 1.迭代器遍历 方法 流程 案例 2. foreach(增强for循环)遍历 案例 3.Lamdba表达式遍历 案例 二、数据结构 数据结构介绍 常见数据结构 栈(Stack) 队列(Queue) 链表(Link) 散列表(Hash Table) 树(Tree) List接口 ArraysList集合 Linked

    2024年02月14日
    浏览(52)
  • [JAVA数据结构] 认识 Iterable、Collection、List 的常见方法签名以及含义

            (一)Iterable                 1. 介绍                 2. 常见方法         (二)Collection                 1. 介绍                  2. 常见方法         (三) List                  1. 介绍                 2. 常见方法

    2024年02月02日
    浏览(44)
  • Java02-迭代器,数据结构,List,Set ,TreeSet集合,Collections工具类

    目录 什么是遍历? 一、Collection集合的遍历方式 1.迭代器遍历 方法 流程 案例 2. foreach(增强for循环)遍历 案例 3.Lamdba表达式遍历 案例 二、数据结构 数据结构介绍 常见数据结构 栈(Stack) 队列(Queue) 链表(Link) 散列表(Hash Table) 树(Tree) List接口 ArraysList集合 Linked

    2024年02月14日
    浏览(46)
  • 数据结构---栈(Stack)

    栈是一种 线性 数据结构 栈是\\\" 后进先出 (LIFO---Last In First Out)\\\"的数据结构(盘子的叠放:当服务员将新的盘子放在餐桌上时,他们通常会将盘子放在已有的盘子堆的顶部。当顾客用完盘子后,服务员会从堆顶取走盘子。这个过程就类似于栈的入栈和出栈操作。) 规定只能从 栈顶

    2024年01月21日
    浏览(40)
  • 数据结构——栈(Stack)

    目录 1.栈的介绍 2.栈工程 2.1 栈的定义 2.1.1 单链表实现栈 2.1.2 数组实现栈 2.1.2.1 静态数组栈 2.1.2.2 动态数组栈 2.2 栈的函数接口 2.2.1 栈的初始化 2.2.2 栈的数据插入(入栈) 2.2.3 栈的数据删除(出栈) 2.2.4 判断栈是否为空 2.2.5 取栈顶数据 2.2.6 栈数据统计 2.2.7 栈销毁 3. 栈总

    2024年01月21日
    浏览(42)
  • 【算法基础】java基础——基本结构、数据类型、表达式、语句

    Java程序的基本结构:         一段Java程序或者一个静态库,会用到下面7种语法         1、原始数据类型:在计算机程序中精确到定义整数、浮点数、布尔值等         2、语句:通过创建变量并对其赋值,它们能够被组合为类似数学公式定义的表达式         3、数组  

    2024年01月16日
    浏览(44)
  • 【数据结构】栈(Stack)实现详解

    🚩 纸上得来终觉浅, 绝知此事要躬行。 🌟主页:June-Frost 🚀专栏:数据结构 🔥该文章主要了解实现栈的相关操作。  栈是一种特殊的线性表,其只允许在 固定的一端 进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶,另一端称为栈底 。栈中的数据元

    2024年02月08日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包