数据结构-数组、链表、队列、栈

数组

定义

同类数据元素的集合

特点

1.数组是相同数据类型的元素的集合
2.数组中的各元素的存储是有先后顺序的,它们在内存中按照这个先后顺序连续存放在一起
3.数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。
4.元素在内存中线性连续存储,可以根据下标快速访问数组元素,但是增删效率不是很高,每一次增加或删除元素都需要大量移动元素空出插入位置或者填补删除元素的位置。

使用场景

频繁查询,很少进行增加或删除操作的情况
数组的长度是固定,一旦创建,不能更改

创建数组

1
2
3
4
Map<String,Object>[] maps = new HashMap[10]; 

int[] a2 = new int[10];
int[] a = {1,2};

链表

定义

是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

特点

存储可以不连贯,根据索引将数据联系起来,当查询元素的时候需要从开头开始去查询,所以效率比较低

使用场景

少查询,需要频繁插入或删除的情况

基本操作 增、删、改、查、反序源码

数组与链表的区别

(1)数组连续,链表不连续
(2)数组内存静态分配,链表内存动态分配
(3)数组查询时间复杂度为O(1),链表为0(n)
(4)数组增加删除的时间复杂度为O(n),链表为O(1)
(5)数组从栈中分配空间,链表从堆中分配空间

Stack 栈

定义

栈是限定仅在表头(栈顶)进行插入和删除操作的线性表。

特点

后进先出(last in first out,LIFO)的堆栈

使用场景:

实现递归以及表达式计算

主要方法及源码

E push(E item)
把项压入堆栈顶部。
E pop()
移除堆栈顶部的对象,并作为此函数的值返回该对象。
E peek()
查看堆栈顶部的对象,但不从堆栈中移除它。
boolean empty()
测试堆栈是否为空。
int search(Object o)
返回对象在堆栈中的位置,以 1 为基数。
Stack本身通过扩展Vector而来,而Vector本身是一个可增长的对象数组( a growable array of objects)那么这个数组的最大下标作为Stack的栈顶,最小下标作为Stack的栈底

1
2


队列 FIFO 先进先出

定义

队列是一种只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作的特殊的线性表。
和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

特征

每次在队尾插入一个元素是,rear增1;每次在队头删除一个元素时,front增1。随着插入和删除操作的进行,队列元素的个数不断变化,队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时,队列中没有任何元素,称为空队列。当rear增加到指向分配的连续空间之外时,队列无法再插入新元素,但这时往往还有大量可用空间未被占用,这些空间是已经出队的队列元素曾经占用过得存储单元。

使用场景

如同一个单向隧道,先进的车先出,多线程的阻塞队列管理非常有用

基本操作及源码