文/南城以南hong
这是一个知识付费，知识共享的年代。我将我每天学习的内容进行总结，既是对自己的巩固，也是对你的帮助。
考点四:栈
(1)定义:栈，实际上也是一种线性表，只不过是一种特殊的线性表，其特殊性体现在，它的插入和删除运算都只在线性表的一端进行，而另一端是封闭的，不进行任何操作。
(2)关键词:
①栈顶(top):在栈中，允许进行插入和删除操作的一端。
②栈底(bottom):在栈中，不允许进行插入和删除操作的一端。
③空栈:没有元素的栈。
④入栈:栈的插入。
⑤栈满
⑥出栈:栈的删除。
(3)特点:
①栈也被称为“先进后出表”或“后进先出表”。
②栈具有记忆作用。
(4)运算:入栈运算和出栈运算。
考点五:队列
(1)定义:队列与栈是不太相同的线性结构，它是允许在一端进行插入，而在另一端进行删除的线性表。
(2)关键词:
①尾指针（rear）:允许插入的一端称为尾部，通常用一个称为尾指针的指针指向队尾元素。
②头指针（front）:允许删除的一端称为对头，常用一个称为头指针的指针指向头元素的前一个位置。
（3）特征:队列又称为“先进先出”的线性表。本着先来先服务的原则。
（4）循环队列:
①定义:顾名思义，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，线性结构可供队列循环使用。
②S=0，表示循环队列为空。S=1，表示循环队列非空，并不表示满。
由此判断队列空和队列满:
1）当S=0，循环队列为空，不能进行退队运算，否则“下溢”。
2）当S=1，且front=rear时，循环队列满，不能进行入队运算，否则“上溢”。
(3)经典例题:
例题①在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中有几个元素？答案:3
例题②在一个容量为15的循环队列中，若头指针front=9，尾指针rear=6，则该循环队列中有几个元素？答案:12
考点六:线性链表
(1)定义:线性表的链式存储结构称为线性链表。
(2)关键词:
①数据域:用于存放数据元素的值。
②指针域:用于存放与之相关数据元素的地址，也就是指向后件结点。
(3)线性链表的插入:
在线性链表的结点x之前插入一个新元素b，过程如下
①取得一个结点，该结点号为p，其数据域为b。
②使节点p指向包含x的结点。即结点p的指针域为原结点q的指针域。
③使结点q的指针域改为p，即指向元素b。
(4)顺序表和链表的优缺点比较
①顺序表
1）优点:随机存取表中的任意结点；无须额外表示结点间的逻辑关系。
2）缺点:插入和删除运算效率低；存储空间不便于扩充；不能动态分配存储空间。
②链表
1）优点:在进行插入和删除运算时，不需要移动元素而只需要改变指针；链表的存储空间易于扩充，并且可以动态分配。
2）缺点:需要指针域来表示数据元素之间的逻辑关系；存储密度比顺序表要低。
【敬请期待下一次更新】
