数据结构初阶——栈和队列

目录

栈

1. 栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和 删除操作的一端称为栈顶，另一端称为栈底。

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

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

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

2. 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

还需要一个capacity变量来记录栈中容量，不够了要扩容。

3. 栈的初始化与销毁

4. 入栈

由于栈的性质，只有入栈时插入数据，那就不用单独写一个扩容的函数了，top记录的是栈中的数据个数，也记录下一个入栈的位置下标，和顺序表差别不大，也比不过多介绍了。

5. 出栈

这里就需要判断一下，第一点就是传入的指针不能为NULL，第二点就是栈中至少还有数据，不能为空。那就需要写一个函数判断栈中是不是空。

6. 获取栈顶元素

栈顶的下标就是top-1，获取栈顶元素就是找到数组中下标为top-1的数据，返回就可以了，当然还是要判断栈中是不是空的。

7. 获取栈中有效元素个数

直接返回top就可以了 。

测试栈

那这里为什么不写一个打印函数呢，是由于栈的性质，只能对栈顶的元素操作，所以接下来就测试一下这个栈。

这里也只是拿数组来实现栈的结构，也可以用链表来实现，使用什么数据结构要看场景，这些都可以自己决定。

队列

1. 队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出

FIFO(First In First Out) 入队列：进行插入操作的一端称为**队尾 出队列：进行删除操作的一端称为队头 **

2. 队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

虽然前面学了双向带头循环链表，但是俗话说的好，杀鸡焉用牛刀，这里就没必要写那么牛的结构了，直接写一个单链表就可以了，加不加头节点可以自己决定，我这里就不加了。

3. 队列的初始化与销毁

既然要尾插和头删，这里就定义了两个指针head和tail，一个记录头节点，一个记录尾节点。

一开始都初始化成NULL；销毁的时候，因为入队的时候都是malloc的，销毁时候每个节点都要free，再把head和tail置成NULL。

4. 入队

入队和入栈都没有单独写申请空间的函数，只有这两个函数才需要申请空间，就直接写在函数中了。 还要判断一开始是空链表的情况。

5. 出队

首先还是判断链表中有没有数据，使用next记录head->next，free(head)；再把next赋给head就可以了，但这样就出现了问题。

6. 获取队列头部和尾部元素

判断是不是空，直接返回相应的值，很简单。

7. 获取队列中有效元素个数

这个可以在结构体中定义一个size，每次入队就++，出队就--，还可以直接定义一个size。

最后返回多少个就可以了。

测试队列

结语

   觉得栈和队列还是很简单的，比起顺序表和链表，已经很简单了。当然，之后还会有栈和队列的oj题的，那就放到后面再介绍，这一篇就介绍到这里了，感谢各位！！！