数据结构与算法（Java 语言描述）【四】

常用数据结构

栈

• 特点：

  • 一般没有长度限制，比较典型的实现就是JVM中的每个线程中的栈实现，具体如下图

• 逻辑结构：是一种特殊的线性结构，只能在线性结构的一端进行操作，称之为栈顶，可以进行入栈、出栈

• 物理结构：存储在连续的内存空间中

• 优点：主要满足一些特定的业务场景，如程序中普通数据类型和引用的存储、异常信息调用链的存储、一些语法检查工具等

• 缺点：无

• Java语言中栈的定义方法如下

  Stack data = new Stack<>();

• 详细示例见附件中的StackDemo.java

队列

• 特点：

  • 一般没有容量限制，但会设置一个初始容量

  • 类似于一个自来水管道，水流从一边注入，另外一边流出，具体如下图

• 逻辑结构：也是一种特殊的线性结构，可以在线性结构的两端进行操作，但只能在一端添加数据，另一端获取数据，分别称之为入队、出队

• 物理结构：有数组实现和链表实现，数组实现存储在连续的内存空间中，在链表实现则无些要求

• 优点：主要满足一些特定场景的应用，如日志处理、流量消峰；除了程序逻辑中的简单应用，有很多高性能的消息队列组件，如RabbitMQ、kafka等

• 缺点：无

• Java语言中队列的定义如下

  Queue data = new ArrayBlockingQueue(10);

• 详细示例见附件中的QueueDemo.java

【备注：部分图片来自网络】