5.栈的应用
5.1大数加法
9992992347234947324732498327427342472987427427984724274
+
9990920943824283492834824820984028348204209384029293
思路：9293 + 978
5.2后缀表达式
中序表达式：日常生活中编写的都是中序表达式。
a + b - c
后缀表达式：把运算符写在后面的表达式，也称为逆波兰记法
中序：a+b 后缀：ab+
中序：a + b - c 后缀：ab+c-
中序：a + b * c 后缀：abc*+
除运算符之外的内容，依次填写
使用一个栈记录运算符
入栈：新入栈的运算符比栈里的运算符优先级要高。如果是(进行入栈操作
出栈：新入栈的运算符没有栈里的运算符优先级高，栈里的运算符需要出栈，新运算符入栈。如果是)出栈直到(
将以下中序表达式转换成后续表达式
中序：8-(3+2*6)/5+2^2 后缀：8326*+5/-22^+
中序：2*9+3-2*(10-3)/14 后缀：29*3+2103-*14/-
中序：A+B*(C*D-E) 后缀：ABCD*E-*+
中序：a+b*c+(d*e+f)*g 后缀：abc*+de*f+g*+
中序：9+(3-1)*3+10/2 后缀：931-3*+102/+
5.3汉诺塔Hanoi
游戏规则
共3个柱子，在一根柱子上，从下往上按照大小顺序摞着N片圆盘。把圆盘开始按大小顺序重新摆放在另一根柱子上
规定：在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
算法
package hanoi; public class TestHanoi { private static int count = 0; /** * * @param n 需要移动的盘子数 * @param x 第一个柱子 起始 * @param y 第二个柱子 过渡 * @param z 第三个柱子 最后 */ public static void hanoi(int n, char x, char y , char z) { if(n == 1) { //只有一个盘子 move(x, 1, z); } else { hanoi(n-1, x, z ,y); // n上面的盘子，从x柱子，通过z柱子，移动到y柱子 move(x, n, z); //n盘子，从x柱子，移动到z柱子 hanoi(n-1, y, x, z); // n上面的盘子目前在y柱子，从y柱子，通过x柱子，移动到z柱子。 } } /** * * @param x 第一个柱子 * @param n 需要移动的盘子号 * @param z 第三个柱子 */ private static void move(char x, int n, char z) { count++; System.out.println("第"+count+"次移动"+n+"号盘子，从"+x+"柱子到"+z+"柱子"); } public static void main(String[] args) { hanoi(4,'x','y','z'); } }
6.队列
6.1定义
队列是一个特殊的线性表。
只允许在表尾进行插入操作
只允许在表头进行删除操作
队列操作特点：
先进先出（FIFO，First In First Out）
or 后进后出（LILO，Last In Last Out）
术语：
队尾rear：进行插入操作的一端。
队首front：进行删除操作的一端。
入队offer：进行插入操作，称为入队。
出队poll：进行删除操作，称为出队。
队列两种存储结果分类：
* 使用顺序存储的称为顺序队列
* 使用链式存储称为链队列。
7.顺序队列
7.1顺序队列
顺序队列的存储结构中，需要分配一块地址连续的存储区域来一次存放队列中从队首到队尾的所有元素。
操作总结：
front表示队首，进行出队操作时，front进行计数。
rear表示队尾，进行入队操作时，rear进行计数。
front == rear == 0 空队列。
操作步骤：
入队操作：
出队操作
存在问题：假溢出，数组的最后一个元素已经添加数据，但队列没有满。
解决方案：使用循环顺序队列解决“假溢出”问题。
7.2循环顺序队列
循环顺序队列：就是在逻辑上队首和队尾连接在一起。
存在问题：队首front和队尾rear重叠时，无法表示队列是满了，还是空的。
解决方案：
方案1：设计一个计数器（整数变量num，入队+1，出队-1，如果num=0就是空）
方案2：设计一个标识变量（flag=0出队，flag=1入队，重叠后0表示空，1表示满）
方案3：少用一个存储单位
// 队列空 front == rear; // 队列满 (rear + 1) % maxSize == front; //余数操作 5 % 5 = 0; 2 % 5 = 2;
7.3循环顺序队列类
循环顺序队列，在逻辑上是一个循环，也就是队首和队尾连接。
循环顺序队列，物理上就是一个数组。
public Class CircleQueue { private Object[] queueElem; //物理数组 private int front; //队首 private int rear; //队尾 }
/
7.4算法：循环顺序队列入队
public void offer(Object x) { if( (rear+1) % queueElem.length == front ) { // 1.判断，如果已经满了，抛异常 throw new RuntimeException('队列满了'); } else { queueElme[ rear ] = x; // 2.没有满进行入队操作 rear = (rear + 1) % queueElem.length; // 3.队尾rear累加1，但最后时需要归零 } }
7.5算法：循环顺序队列出队
public Object poll() { if( front == rear ) { // 判断 空 返回null return null; } Object data = queueElem[front]; // 如果不为空，获得队首front元素 front = (front + 1) % queueElem.length; // 队首+1，且需要归零 return data; }
