【线性表，队列和栈，栈溢出，链表和顺序表的特点】

线性表

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

1.线性表的顺序存储结构

2.线性表的链式存储结构

单链表
双向链表
循环链表

---

栈和队列

栈( stack)是限定仅在表尾进行插入或删除操作的线性表。因此,对栈来说,表尾端有其特殊含义,称为栈顶( top),相应地,表头端称为栈底(bottom)。不含元素的空表称·为空栈。

栈的两种表现形式 （后进先出）
1.顺序栈
2链栈

1.顺序栈

顺序栈,即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。

通常的习惯做法是以 top=0表示空栈,鉴于C语言中数组的下标约定从0开始,则当以C作描述语言时,如比设定会带来很大不便;

另一方面,由于栈在使用过程中所需最大空间的大小很难估计。因此，一般来说,在初始化设空栈时不应限定栈的最大容量。一个较合理的做法是:先为戈分配一个基本容量,然后在应用过程中,当栈的空间不够使用时再逐段扩大。为此,可设定两个常量:STACKZ INIT_ SIZE(存储空间初始分配量)和STACKINCREMENT(存储空间分配增量),并以下述类型说明作为顺序栈的定义。

顺序栈的思路：

尾插（top指针）尾删。O（1）
改查操作：O（1）

---

2 链栈

链栈的存储结构与单链表的存储结构相同。由于栈是在栈顶进行删除和添加元素的，
因此，
将链表的首部作为栈顶最方便。而且没有必要像单链表那样为了操作简单而附加一个头结点。
1
2
3

栈顶放在单链表的头部。可以不用头结点

---

删除和插入

头插头删（方便操作）O(1)
改查操作：O（n）

栈的其他应用：函数的递归
函数的每次调用会开辟一个栈帧。调用的方式就是栈的后进先出的方式。
函数的递归次数过多会导致一个题外话：栈溢出（stack overflow）

---

栈溢出（stack overflow）

栈溢出概念：
栈溢出指的是程序向栈中某个变量中写入的字节数超过了这个变量本身所申请的字节数，因而导致栈中与其相邻的变量的值被改变。

栈溢出的原因：

1. 局部数组过大。当函数内部的数组过大时，有可能导致堆栈溢出。局部变量是存储在栈中的，因此这个很好理解。解决这类问题的办法有两个，一是增大栈空间,二是改用动态分配，使用堆（heap）而不是栈（stack）。

2. 递归调用层次太多。递归函数在运行时会执行压栈操作，当压栈次数太多时，也会导致堆栈溢出。

3. 指针或数组越界。这种情况最常见，例如进行字符串拷贝，或处理用户输入等等。

---

队列

和栈相反﹐队列(queue)是一种先进先出( first in lirst out,统15为 FIFO))的线性表。它只允许在表的一端进行插入,而在另一端删除元素。
1.队列的链式存储结构

实现：尾插头删（先进先出）

尾插是O(1)（rear域记录队尾指针的位置。）
删除是O（1）
改查操作是 O（n）

---

队列的顺序存储结构

插入是O(1)（rear域记录队尾指针的位置。）
删除是O（1）
改查操作是 O（n）

假设当前为队列分配的最大空间为6,则当队列处于图3.12(d)的状态时不可再继续插入新的队尾元素,否则会因数组越界而遭致程序代码被破坏。然而此时又不宜如顺序栈那样,进行存储再分配扩大数组空间,因为队列的实际可用空间并未占满。一个较巧妙的办法是将顺序队列臆造为一个环状的空间,如图

---

数组和链表的区别

数组的特点：

数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。 数组的插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。但数组的随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。并且数组不利于扩展，数组定义的空间不够时要重新定义数组。

1

链表的特点：

链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。不指定大小，扩展方便。链表大小不用定义，数据随意增删。

---

各自的优缺点

数组的优点：

1. 随机访问性强

2. 查找速度快

数组的缺点:

1. 插入和删除效率低

2. 可能浪费内存

3. 内存空间要求高，必须有足够的连续内存空间。

4. 数组大小固定，不能动态拓展

链表的优点:

1. 插入删除速度快

2. 内存利用率高，不会浪费内存

3. 大小没有固定，拓展很灵活。

链表的缺点:

不能随机查找，必须从第一个开始遍历，查找效率低

链表和顺序表具体使用哪个要看具体的场景。所以知道他们的特点就好。

---

看完以上的内容做一个总结：
队列的栈的顺序实现和链表实现的插入删除操作的时间复杂度都是O（1）。
改查只有顺序表的栈是O（1），其他都是的操作都是O（n）。
总体来看都差不太多，栈和队列具体使用线性还是链表要看具体的场景。