目录

栈

1. 栈的概念及结构

2. 栈的实现

3. 栈的初始化与销毁

4. 入栈

5. 出栈

6. 获取栈顶元素

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

测试栈

队列

1. 队列的概念及结构

2. 队列的实现

3. 队列的初始化与销毁

4. 入队

5. 出队

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

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

测试队列

结语

栈

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题的，那就放到后面再介绍，这一篇就介绍到这里了，感谢各位！！！