分类: Java 数据结构

标签: LinkedList LinkList 双向链表 链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。—-摘自百度百科。

只包含下一个节点的指针，这样的链表叫单向链表，如果还包含上一个链表的指针叫双向链表。在双向链表里，如果一个节点的上一个节点地址为空，则表示该节点为第一个节点，如果下一个节点的地址为空，则表示该接点为最后一个节点，如果两个都为空，表示该链表只有一个元素（数据不为空）或链表为空（数据为空）。 如果最后一个节点的下一个节点地址为第一个节点，这样的链表叫循环链表。

分类: Java 数据结构

标签: FIFO queue 先进先出 队列

队列和栈相反，是先进先出（FIFO，first in first out）的数据集合。就跟排队打饭一样，最先进入队伍的总是最先离开。

队列元素的操作一般由入列（enQueue）和出列（deQueue）组成。 按照通常理解，如果队首的人离开，队伍中所有的人将往前挪一个位置，在下面的代码里，我没有这么做，因为如果每次出列都进行一次平移，就造成了多次元素交换，影响效率，当然如果你不在乎可以进行平移。取而代之的是，用两个索引head跟tail来标记当前队首跟队尾元素的索引，避免了移位。在这里，没有实现队列的自动增长，使用索引来标记队首队尾元素，增加了自动增长的难度，其实也很简单，只是暂时觉得没有必要实现。

分类: Java 数据结构

标签: lifo stack 后进先出 栈

栈是一种后进先出（LIFO，last in first out）的数据集合。可以把栈看成餐馆中用来放盘子的、里面安装了弹簧的栈，盘子弹出的顺序跟被压入的顺序正好相反，因为在每一时刻，只有最顶上的盘子是可以拿到的。

栈中操作元素的方法通常为两种，压入（push）与弹出（pop）。先下的代码用java数组实现了栈，加入了栈的自动增长，关于自动增长要说的是，有些算法对于自动增长的时机以及自动增长的容量有特殊研究，这里只是简单的采用当数组满后将数组长度翻倍的做法。代码中自定义的异常StackOverFlowException只是简单实现了RuntimeException中的String构造方法，这里就不再给出，读者可以自行使用RuntimeException替代。对于泛型的使用请参考java中关于泛型的用法。