一、栈的定义

　　栈的定义：栈是限定仅在表尾进行插入和删除的操作的线性表。

　　允许插入和删除的一段称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表，简称LIFO结构。

　　栈元素具有线性关系，即前驱后继关系，只不过他是一种特殊的线性表。他的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。

　　栈的插入操作，叫做进栈，也称压栈、入栈。

　　栈的删除操作，叫做出栈，也有的叫做弹栈。

二、栈的抽象数据类型

　　因为栈也是一个线性表，所以，线性表的顺序存储和链式存储对于栈也同样适用。

三、栈的顺序存储结构及实现

　　1、栈的顺序存储结构

　　

　　2、进栈操作

　　

　　3、出栈操作

　　

　　4、栈的链式存储结构

　　　　链栈的操作绝大多数都和单链表类似，只是在插入和删除上特殊一些。

　　5、栈的作用

　　　　栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。反之，像数组等，因为要分散精力去考虑数组的下标增减等问题，反而掩盖了问题的本质。

　　6、递归

　　　　栈有一个很重要的作用是在程序设计语言中实现了递归。比如：斐波那契数列

　　　　递归：把一个直接调用自己或通过调用语句间接调用自己的函数，称作递归函数。每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。

　　　　递归与迭代区别：迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会消耗大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。

四、队列的定义

　　队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为对头。

五、队列的链式存储结构及实现

　　

 

 六、总结

　　栈和队列大部分操作和单链表类似，不再做详细介绍。