栈

栈（stack）是限定仅在表尾进行插入和删除的线性表

把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。

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

理解栈需要注意：

首先它是一个线性表，也就是说，栈元素具有线性关系，即：前驱后继关系。只不过它是一种特殊的线性表而已。

其次在线性表的表尾进行插入和删除，这里的表尾指的是栈顶(top)而非栈底。

栈的插入操作叫进(压\入)栈

栈的删除操作叫做出栈

栈操作图

1、栈的顺序存储结构

对于栈而言，栈普通情况、空栈和栈满的情况示意图如下

线性存储1

对于栈的插入，即进栈操作，其实就是做如下图所示的处理；

push操作需要注意的是：

/*栈满*/

/*栈顶指针增加一*/

/*将新插入元素赋值给栈顶空间*/

pop操作需要注意的是：

/*若栈不空，再删除*/

/*将要删除的栈顶元素赋值返回*/

/*栈顶指针减一*/

线性存储2

2、栈的链式存储

栈只是栈顶来做插入和删除操作，单链表也有头指针而栈顶指针也是必须的，所以可以使用栈顶放在单链表的头部，由于已经有了栈顶在头部啦，所以不需要头结点啦(入下图)

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间

对于空栈来说，链表元定义是头部指针指向空，那么链栈的空其实就是top=NULL的时候

链式存储1

栈的链式存储（进栈操作）

对于进栈push操作，假设元素为e的新结点是s，top为栈顶指针（如下图所示）

链式存储2

栈的链式存储出栈操作

假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可

链式存储3

栈的作用：

递归

程序临时变量都是存放在栈中