参考资料：

xx

 

线性结构

线性结构是一种有序数据项的集合。其中每个数据都有唯一的前驱和后继(第一个和最后一个可能存在例外)。

数组(Array)

数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合，用的是连续的内存空间。

链表(Linked list)

相比于数组，链表的存储在物理上存在非连续性，宏观看起来像一条链一样，按一定的顺序存储元素。

• 单链表：头结点的HEAD 指针指向第一个存储单元，每一个存储单元(结点)既包含数据元素，也包含指向下一个元素存储单元的指针，单链表最后一个存储单元的指针指向NULL。
• 循环链表：与单链表不同之处在于，最后一个结点的指针不是指向NULL，而是指向第一个结点(和头结点的指向一样)。 
• 双向链表：除了第一个结点和最后一个结点外，每个结点既包含该点的数据，也包含指向上一个结点和下一个结点的指针，也就是有两个指针。第一个结点没有头指针，最后一个结点没有尾指针。
• 双向循环链表：循环链表和双向链表二者结合起来，也就是说3中的最后一个结点的尾指针指向第一个结点(的数据)，第一个结点的头指针指向最后一个结点。

 

栈(Stack)

栈是一种特殊的线性表，只能在一个表的一个固定端进行数据结点的插入和删除操作。先进后出，后进先出，可以想象一下叠起来的自助餐盘。

应用：浏览器的前进、倒退功能，编辑器/IDE中的撤销、取消撤销功能，程序代码中的函数调用、递归、四则运算等等都是基于堆栈这种数据结构来实现的(不太懂)。

抽象数据类型“栈”定义为如下的操作：

• Stack() 创建一个空栈，不包含任何数据项。
• push(item) 将item加入栈顶，无返回值。
• pop() 将栈顶元素移除，并返回，栈被修改。
• peek() “窥视”栈顶的数据顶，返回栈顶的数据但不移除，栈不被修改。
• isEmpty() 返回栈是否为空栈

 

Stack Operation	Stack Contents	Return Value
s= Stack()	[]	Stack object
s.isEmpty()	[]	True
s.push(4)	[4]
s.push('dog')	[4,'dog']
s.peek()	[4,'dog']	'dog'
s.push(True)	[4,'dog',True]
s.size()	[4,'dog',True]	3
s.isEmpty()	[4,'dog',True]	False
s.push(8.4)	[4,'dog',True,8.4]
s.pop()	[4,'dog',True]	8.4
s.pop()	[4,'dog']	True
s.size()	[4,'dog']	2