计算机二级公基知识点栈及线性链表思维导图

栈是限定只在一端进行插入与删除的线性表，通常称插入、删除的这一端为栈顶，另一端为栈底。

当表中没有元素时称为空栈。

栈顶元素总是后被插入的元素，从而也是最先被删除的元素;栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。

栈是按照"先进后出"或"后进先出"的原则组织数据的。

用一维数组S(1∶m)作为栈的顺序存储空间，其中m为最大容量。

在栈的顺序存储空间S(1∶m)中，S(bottom)为栈底元素，S(top)为栈顶元素。top=0表示栈空;top=m表示栈满。

栈的基本运算有三种：

一部分用于存放数据元素值，称为数据域

另一部分用于存放指针，称为指针域。

其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。

线性表的链式存储结构称为线性链表。

在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针，用以指向其前件结点;另一个称为右指针，用以指向其后件结点。这样的表称为双向链表。

栈也是线性表，也可以采用链式存储结构。

带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。

在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。