数据结构之线性表，栈和队列_线性表栈和队

1.线性表

  1.1顺序表

  1.2链表

2.栈

  2.1数组栈

3.队列

  3.1链式队列

数据结构可以说是人必须学习的一门重要的课程了，它的难度可谓不小，今天这篇博客详细介绍了线性表，栈和队列的介绍以及实现，希望能给大家带来帮助。

1.线性表

概念：用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。

特点：逻辑上相邻的数据元素，物理次序也是相邻的。只要确定好了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的储存结构，我们通常用动态内存开辟的方法来开辟顺序表内存。

1.1顺序表

因此基于线性表的特点，我们要实现的顺序表接口有以下几种：

1.顺序表的初始化

2.顺序表的尾部插入数据

3.顺序表的头部插入数据

4.顺序表的数据查找

5.顺序表的尾部删除数据

6.顺序表的头部删除数据

7.顺序表的打印

8.顺序表的销毁

顺序表的初始

顺序表的头部插入数据

顺序表的头部插入数据

顺序表的数据查找（找到了返回下标，没找到返回-1）

顺序表的尾部删除数据

顺序表的头部删除数据

顺序表的打印

顺序表的销毁

以上就是简单实现的顺序表了，接口还不算太多。
 

顺序表的优缺点

优点：无须为表中元素之间的逻辑关系而增加额外的存储空间；可以快速的存取表中任一位置的元素。
缺点：插入和删除操作需要移动大量元素；当线性表长度较大时，难以确定存储空间的容量；造成存储空间的“碎片”。

1.2链表

单链表的基本概念
在链式结构中，除了要存储数据元素的信息外，还要存储它的后继元素的存储地址。因此，为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。我们吧把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。
n个结点（ai的存储映像）链结成一个链表，即为线性表（a1, a2, …, an）的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。

实现链表的接口：

1.链表的数据头插

2.链表的数据尾插

3.链表的数据头删

4.链表的数据尾删

5.链表的数据查找

6.链表的数据插入

7.链表的数据打印

8.链表的销毁

链表的数据存储方式

这个图表是增添新的节点的函数，其原理和顺序表的类似。

1.链表的数据头插

链表的数据尾插

链表的数据头删

链表的数据尾删

链表的数据查找

链表的数据插入

链表的数据打印

链表的销毁

以上是单项链表的实现，结构算简单，后边还有双向链表，循环链表，双向循环链表等等复杂链表，感兴趣的小伙伴可以去了解一下

2.1数组栈

栈（Stack）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。

栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构

栈这类数据结构可以既可以用顺序表来实现（也称数组实现）也可以用链表来实现

但由于栈数据的先进后出的特性，我们一般采用后者方法来实现。

实现数组栈的接口：

1.数组栈的初始化

2.栈顶数据入栈

3.栈顶数据出栈

4.数组栈数据打印

5.数组栈销毁

6.查找栈顶数据

7.判断数组栈是否为空

8.求数组栈数据个数

数组栈的初始化

栈顶数据入栈

栈顶数据出栈

数组栈数据打印

数组栈销毁

查找栈顶数据

判断数组栈是否为空

求数组栈数据个数

以上是数组栈的接口实现，需要注意的是定义结构体变量的时候要定义地址变量

3.1链式队列

队列的定义
队列（queue）是只允许在一端进行插入操作，在另一端进行删除操作的线性表，简称“队”。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。

允许插入的一端称为队尾（rear），允许删除的一端称为队头(front)。

向队列中插入新的数据元素称为入队，新入队的元素就成为了队列的队尾元素。

从队列中删除队头元素称为出队，其后继元素成为新的队头元素。

同栈这个数据结构一样，队列的实现也可以用顺序表和链表，在本篇博客，我们用链表队列来实现一个简单的栈结构

实现链式队列的接口：

1.队列的初始化

2.队列的销毁

3.队尾的数据插入

4.队头的数据出队列

5.判断队列是否为空

6.取队头的数据

7.取队尾的数据

8.求队列数据的个数

队列的初始化

队列的销毁

队尾的数据插入

队头的数据出队列

判断队列是否为空

取队头的数据

取队尾的数据

求队列数据的个数

以上就是对简单队列函数接口的实现了，后面还有更为复杂的循环队列

小伙伴们可以去leetcode上面找相关的题目来做

总结：看似我们今天实现了四个不同结构的结构，其实本质上就是顺序表和链表的区别，二者相关与不同的地方颇多。

顺序表和链表的比较
1、存取(读写)方式
顺序表可以顺序存取,也可以随机存取,链表只能从表头顺序存取元素。例如在第i个位置上执行存或取的操作,顺序表仅需一次访问,而链表则需从表头开始依次访问i次。

2、逻辑结构与物理结构
采用顺序存储时,逻辑上相邻的元素,对应的物理存储位置也相邻。而采用链式存储时,逻辑上相邻的元素,物理存储位置则不一定相邻,对应的逻辑关系是通过指针链接来表示的。

3、查找、插入和删除操作
对于按值查找,顺序表无序时,两者的时间复杂度均为O(n);顺序表有序时,可采用折半查找,此时的时间复杂度为O(log2n)。
对于按序号查找,顺序表支持随机访问,时间复杂度仅为O(1),而链表的平均时间复杂度为O(n)。顺序表的插入、删除操作,平均需要移动半个表长的元素。链表的插入、删除操作,只需修改相关结点的指针域即可。由于链表的每个结点都带有指针域,故而存储密度不够大。

4、空间分配
顺序存储在静态存储分配情形下,一旦存储空间装满就不能扩充,若再加入新元素,则会出现内存溢出,因此需要预先分配足够大的存储空间。预先分配过大,可能会导致顺序表后部大量闲置;预先分配过小,又会造成溢出。动态存储分配虽然存储空间可以扩充,但需要移动大量元素,导致操作效率降低,而且若内存中没有更大块的连续存储空间,则会导致分配失败。链式存储的结点空间只在需要时申请分配,只要内存有空间就可以分配,操作灵活、高效。

对于今天的博客分享就到这里，希望能帮助到大家！