【Java】距离我上次知道栈和队列有多简单还是在上次_java学校的自助午餐提供圆形和方形的三明治，分别用数字0和1表示。所有学生站在一个队列里，每个学生

那么接下来，就让我来讲讲道理!

引子

栈、队列和线性表一样都是一种线性的数据结构，各个元素之间呈线性关系，但是和一般的线性结构又存在着不同。

对栈所实施的操作限定在表尾，主要的操作为进栈、出栈、取栈顶的元素

对队列所实施的操作限定在表头和表尾，主要操作为表尾入队、表头出队、表头取对头元素

一、栈

1.1 概念

栈的操作有先进后出的特点

在生活中这样的例子到处都是，使用盘子时，总是会自上而下的取走盘子，洗盘子时，总是会自下而上的将盘子堆叠在一起。一摞厚厚的书，想要拿到压在下面的书，比较安全的做法就是将上面的书一本一本的取走，再拿到想拿的书，再一本一本将书放在上面。

规律总结：无论是取盘子、书，放盘子、书，都只在最上端进行，遵循着后放入的先取出的原则

栈的使用就是如此，先进后出，后进先出。只允许在固定的一段进行插入元素（即入栈）删除元素（出栈），该端被称为栈顶，那么另一端就为栈底。栈顶会一直随着插入删除变化着，栈底一直固定不变。

1.2 实例

1.2.1 不可能的出栈顺序

题目：
已知一个栈的入栈序列是 mnxyz ，则不可能出现的出栈顺序是？

A.mnxyz B.xnyzm C.nymxz D.nmyzx

题解：

该题目的重点在于入栈后也可以直接又出栈

选项A: 显而易见的，五个元素分别都入栈后又直接出栈，成立
选项B: mnx依次入栈，x出栈，n再出栈，y入栈后又出栈，z入栈后又出栈，m最后出栈，成立
选项C: mn依次入栈，n出栈，xy依次入栈，y出栈，下一个若是出栈必定是x而不是m，错误

选项D: mn依次入栈，n出栈，m出栈，xy依次入栈，y出栈，z入栈后出栈，x最后出栈，成立

答案：C

1.2.2 中缀表达式转后缀表达式

表达式有三种不同的记法，即前缀、中缀、后缀表达式，我们日常生活中常用的表达式是中缀表达式，运算符在操作数的中间，前缀表达式的运算符在操作数的前面，后缀表达式的运算符在操作数的后面。

例如：

中缀表达式：(((2 + 3) * 4) - (6 / 2))

前缀表达式：- * + 2 3 4 / 6 2

后缀表达式: 2 3 + 4 * 6 2 / -

对于人们来说，中缀表达式的形式更易于计算，另外两种没有办法一时间看出来写的是什么

对于计算机来说不然，前缀、后缀表达式的计算更为简单，因此在计算表达式的时候，计算机都会将中缀表达式转化为前缀或后缀表达式

就拿中缀表达式转后缀表达式为例，说一个最简便的转换方式：

1. 按照运算符的优先级依次加上()
2. 依次将运算符移动到对应的括号的后面（如果是转换为前缀表达式的话则移动到括号前面）
3. 去掉括号，得到后缀表达式

以表达式((2 + 3) * 4)为例

图解：

后缀表达式计算的方式：

1. 如果后缀表达式为数字，就依次入栈
2. 如果遇见运算符，就从栈中弹出一个数字放在运算符的右侧，再弹出一个数字放在运算符的左侧
3. 计算后，将计算结果入栈
4. 循环往复，直到栈中没有数字，就完成了整个计算过程

1.3 自我实现

可以用顺序表的方式来实现栈，也可以用链表的方式来实现栈，相对而言，顺序表的实现更加方便简单，这里就用顺序表来实现栈。

栈的顺序存储结构是指使用一组地址连续的存储单元来依次存放自栈底到栈顶的数据元素，采用顺序的存储方式存储的栈叫做顺序栈，在这里实现这个栈的类 MyStack 就叫顺序栈类

在此处，使用了一维数组int[] elem来存储栈中的数据元素，设置合适的初始长度；使用变量 usedSized 来记录栈中的数据元素的个数，如果想要删除一个元素(出栈)，使其减一，如果想要入栈，使其加一，如果想要清空栈，就可以使其为0

实现方法：

• public MyStack()

  初始化数组的长度

• public boolean isFull()

  当发现栈中的元素的个数和数组的长度相等，代表栈满，返回 true，否则返回 false

• public void push(int val)

  将数据元素val推入栈中，如果栈满，则将实现栈的数组进行扩容，再将数据元素放到数组下标为 usedSized 的地方，数组大小加一

• public boolean empty()

  判断栈是否为空，当发现 usedSized 大小为0，返回 true，否则返回 false

• public int peek()

  如果栈不为空，则返回栈顶的数据元素；如果为空，就报异常，提示“栈空了”

• public int pop()

  如果栈不为空，usedSized 大小减一，则删除栈顶的数据元素并将其返回；如果为空，就报异常，提示“栈空了”