算法与数据结构线性表之栈和队列

         Hello大家好！ 很高兴与大家见面！ 给生活添点快乐，开始今天的编程之路。

我的博客:<但愿.

我的专栏:C语言、题目精讲、算法与数据结构、C++

欢迎点赞，关注

一     栈

1概念：栈是⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出的原则。

2结构：栈的一端是开的，一端是闭合的

 3栈的使用方法：压/出栈

压栈：栈的插⼊操作叫做进栈/压栈/⼊栈， ⼊数据在栈顶 。

出栈：栈的删除操作叫做出栈。 出数据也在栈顶 。

4  栈底层结构选型 

    4.1 栈底层结构选择： 栈的实现⼀般可以使⽤数组或者链表实现。那它们的区别在哪？它们的区别主要在 内存上因为在内存上假如是一个整型栈数组的内存是4个字节，而链表的内存是8个字节。第二个方面是数组在物理空间（内存地址空间）上是连续的，而链表在物理空间上是不一定连续的这就存在内存碎片问题。 所以通过在内存问题上我们选择数组作为栈的底层结构更合适。

4.2栈顶的选择：上面我们通过在内存问题上我们选择了数组作为栈的底层，由于栈的一端是开的一端是闭合的【即只能从栈顶对栈操作】这就引出一个问题我们应该选择数组的哪端作为栈顶，这里我们要通过时间复杂度来分析，我们对 数组的头部操作时间复杂度是O(n) ，而 对数组的尾部操作时间复杂度是O（1） ，所以我们应该 将数组的尾部作为栈顶 。

5栈对应的结构和各种方法的实现

5.1各种方法的声明：

Stack.h

5.2各种方法的实现：

Stack.c

二   队列

1概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出的原则。

2结构

 3入/出队列

⼊队列：进⾏插⼊操作的⼀端称为 队尾

出队列：进⾏删除操作的⼀端称为 队头

4队列底层结构选型

4.1队列底层结构选择：队列也可以数组和链表的结构实现。哪我们到底选择哪种作为队列的底层结构，这里我们选择链表，因为我们我们对数组头部进行操作的时间复杂度我O（n)。

4.2队列队头与队尾的选择

我们对单链表进行分析：

第一种将头节点作为队头

第二种将尾节点作为队头

  从上面两种情况来看不管使用哪种总有一种时间复杂度为O（n)说明这种方法是不好的，哪怎么解决这个问题呢？方法一：使用双向链表，但是双向链表相对于单向链表在空间上有存在不足所以这也不是最优解；方法二：因为我们的队列进行操作只是的队头和队尾操作那么我们可以定义两个结构体一个定义节点，一个定义队头和队尾【只是最优解】。

5栈对应的结构和各种方法的实现

5.1各种方法的声明：

Queue.h

5.2各种方法的实现：

Queue.c

好了，今天的内容就分享到这，我们下期再见！