栈的定义

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

• 允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈
• 栈又称为后进先出的线性表，简称LIFO结构
• 注意：
  • 栈是一个线性表，栈元素具有线性关系，即前驱后继关系
  • 表尾指的是栈顶
  • 栈底是固定的，最先进栈的只能在栈底
• 栈的插入操作，叫做进栈，也称压栈、入栈
• 栈的删除操作，叫做出栈，也有的叫做弹栈

进栈出栈变化形式

栈的抽象数据类型

• 插入和删除操作：push和pop

栈的顺序存储结构

• 下标为0的一端作为栈底
• 定义一个top变量来指示栈顶元素在数组中的位置
• 存储栈的长度为stacksize，则top位置必须小于stacksize
• 当栈存在一个元素时，top等于0,因此把空栈的判定条件定为top等于-1
• 栈的结构定义：
  

进栈操作

出栈操作

两栈共享空间

• 关键思路：它们是在数组的两端，向中间靠拢
• 两指针之间相差1,即top1+1=top2栈满
• 共享代码：
  
• 插入元素代码：
  
• 删除元素代码：
  

栈的链式存储结构及实现

栈的链式存储结构

• 简称链栈
• 栈顶放在单链表的头部
• 链栈是不需要头结点的
• 对于空栈来说，链表的原定义是头指针指向空，栈链的空其实就是top=NULL
• 结构代码：
  

进栈操作

• 元素值为e的新结点是s，top为栈顶指针
• 代码:
  

出栈操作

• p存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p

栈的作用

简化了程序设计的问题，划分了不同的关注层次，使得思考范围缩小，更加聚焦于解决问题的核心
现在许多的高级语言，都有对栈结构的封装

栈的应用-递归

斐波那契数列的实现

递归定义

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

栈的应用——四则运算表达式求值

后缀表示法定义

• 不用括号的后缀表示法，我们也把它称为逆波兰表示
  eg：9+(3-1)*3+10/2用后缀表示法应该是9 3 1-3* + 10 2 / +
• 所有的符号都是要在运算数字的后面出现

中缀表达式转后缀表达式

• 标准四则运算表达式，叫做中缀表达式
• 规则：
  1. 从左到右遍历中缀表达式的每个数字和符号，若是数字就输出
  2. 若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号则栈顶符号依次出栈输出，并将当前符号进栈
  3. 一直到最终输出后缀表达式为止

队列的定义

• 操作系统和客服系统中，都是应用了一种数据结构来实现刚才提到的先进先出的排队功能，这就是队列

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

• 队列是一种先进先出(First in First out)的线性表，简称FIFO，允许插入的那一端称为队尾，允许删除的那一端称为队头

循环队列

队列顺序存储的不足

• 为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，当front等于rear时，是空队列

循环队列定义

• 解决假溢出的办法就是后面满了，再从头开始，也就是头尾相接的循环，我们把这种称为循环队列
• 为了避免front等于rear时，无法判断队列状态，则修改其条件，保留一个元素空间

若队列的最大尺寸为QueueSize,那么队列满的条件是(rear+1)%QueueSize == front

• 当rear>front时，队列长度为rear-front，当rear<front时，队列长度是QueueSize-front+rear
• 通用的计算队列长度公式：
  (rear-front+QueueSize)%QueueSize
• 单是顺序存储，若不是循环队列，算法的时间性能不高
• 循环队列面临数组可能会溢出的问题

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

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称链队列

• 为了操作上的方便，我们将队头指针指向链队列的头结点，队尾指针指向终端结点

入队操作

• 其实就是在链表尾端插入结点

出队操作

• 头结点的后继结点出队，将头结点的后继改为它后面的结点
• 若链表头结点外只剩下一个元素时，将rear指向头结点

总结回顾

• 栈(stack)是限定仅在表尾进行插入和删除操作的线性表
• 队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

结尾诗

人生，就像是一个很大的栈演变。出生时你赤条条地来到人世，慢慢地长大，渐渐地变老，最终还得赤条条地离开世间
人生，又仿佛是一天一天小小的栈重现。童年父母每天抱你不断地进出家门，壮年你每天奔波于家与事业之间，老年你每天独自蹒跚于养老院的门里屋前
人生，更需要有进栈出栈精神的体现。在哪里跌到，就应该在哪里爬起来。无论陷入何种困境，只要抬头就能仰望蓝天，就有希望，不断进取，你就可以让出头之日重现。困难不会永远存在，强者才能勇往直前
人生，其实就是一个大大的队列演变。无知童年、快乐少年，稚嫩青年，成熟中年，安逸晚年
人生，又是一个小小的队列重现。春夏秋冬年年轮回，早中晚夜循环天天。变化的是时间，不变的是你对未来执著的信念
人生，更需要有队列精神的体现。南极到北极，不过是南纬90度到北纬90度的队列，如果你中途犹豫，临时转向，也许你就只能和企鹅永远相伴。可事实上，无论哪个方向，只要你坚持到底，你都可以到达终点