# 数据结构和算法
# 稀疏数组和队列
# 稀疏 sparsearray 数组
先看一个实际的需求 。
编写的五子棋程序中，有存盘退出和续上盘的功能。
分析问题：
因为该二维数组的很多值是默认值 0，因此记录了很多没有意义的数据 -> 使用稀疏数组对二维数组进行压缩。
基本介绍。
当一个数组中大部分元素为 0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是：
- 记录数组一共有几行几列，有多少个不同的值。
- 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。
二维数组 转 稀疏数组的思路：
- 遍历 原始的二维数组，得到有效数据的个数 sum
- 根据 sum 就可以创建稀疏数组
sparse int[sum + 1][3] - 将二维数组的有效数据存入到稀疏数组
稀疏 数组转原始的二维数组的思路：
- 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的
chessArr2 = int[11][11] - 再读取稀疏数组后几行的数据，并赋给 原始的二维数组即可。
代码实现：
public static void main(String ... args){ | |
// 创建二维数组 棋盘，地图 | |
int[][] arr = new int[11][11]; | |
arr[1][2] = 1; | |
arr[2][3] = 2; | |
arr[5][5] = 2; | |
// 输出二维数组中的数据 | |
System.out.println("原始的二维数组"); | |
for(int[] item:arr){ | |
for(int i:item){ | |
System.out.printf("%d\t",i); | |
} | |
System.out.println(); | |
} | |
// 将二维数组 转 稀疏数组的思路 | |
//1. 先遍历二维数组，得到非 0 数据个数 | |
int count = 0; | |
for(int i = 0;i < arr.length;i ++){ | |
for(int j = 1;j < arr[i].length;j ++){ | |
if(arr[i][j] != 0){ | |
count ++; | |
} | |
} | |
} | |
System.out.println("二维数组中有效数据的个数："+count); | |
int[][] sparse = new int[count+1][3]; | |
// 给稀疏数组赋值，记录原二维数组的样子 11 行 11 列 n 个有效数据 这样的 | |
for(int i = 0;i < arr.length;i ++){ | |
sparse[0][0] = arr.length; | |
sparse[0][1] = arr[i].length; | |
sparse[0][2] = count; | |
} | |
// 遍历二维数组，将非 0 的值存放到稀疏数组中 | |
// 定义一个计数器来记录第几个非 0 的数据 | |
int count1 = 0; | |
for(int i = 0;i < arr.length;i ++){ | |
for(int j = 0;j < arr.length;j ++){ | |
if(arr[i][j] != 0){ | |
// 左右记录坐标，最右记录值，所以 count1 有多少有效数据就记录多少行 | |
count1 ++; | |
// 左边记录行坐标，右边记录列坐标 | |
// 记录第 count1 行 0 列的非 0 数据的行坐标 | |
sparse[count1][0] = i; | |
// 记录第 count1 行 1 列的非 0 数据的列坐标 | |
sparse[count1][1] = j; | |
// 最右边记录 当前有效的数据 | |
sparse[count1][2] = arr[i][j]; | |
} | |
} | |
} | |
// 输出稀疏数组的值 | |
for(int[] item:sparse){ | |
for(int i:item){ | |
System.out.printf("%d\t",i); | |
} | |
System.out.println(); | |
} | |
// 将稀疏数组 恢复为 原始的二维数组 | |
//1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组 | |
int[][] arr1 = new int[sparse[0][0]][sparse[0][1]]; | |
// 输出的二维数组的数据全都是为 0 的 | |
//for(int[] item:arr1){ | |
// for(int i:item){ | |
// System.out.printf("%d\t",i); | |
// } | |
// System.out.println(); | |
//} | |
//2. 再读取稀疏数组后几行的数据 (从第二行开始)，并赋给 原始的二维数组即可 | |
for(int i = 1;i < sparse.length;i ++){ | |
//sparse 第 i 行的第 2 列是存储二维数据的值的位置 | |
arr1[sparse[i][0]][sparse[i][1]] = sparse[i][2]; | |
} | |
// 输出的二维数组的数据 | |
for(int[] item:arr1){ | |
for(int i:item){ | |
System.out.printf("%d\t",i); | |
} | |
System.out.println(); | |
} | |
} |
运行结果：
原始的二维数组
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
二维数组中有效数据的个数：3
输出稀疏数组的值
11 11 3
1 2 1
2 3 2
5 5 2
输出稀疏数组恢复后的数据
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
# 队列
银行排队的案例：
队列介绍：
- 队列是一个有序列表，可以用数组或是链表来实现。
- 遵循先入先出的原则，即：先存入队列的数据，要先取出，后存入的要后取出。
- 示意图 (使用数组模拟队列示意图)：
# 数组模拟队列
- 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中 maxSize 是该队列的最大容量。
- 因为队列的输出，输入是分别从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列全后端的下标，front 会随着数据输出而改变，而 rear 则是随着数据输入而改变。如下图所示：
- 当我们将数据存入队列时称为 "addQueue"，"addQueue" 的处理需要有两个步骤：思路分析
- 将尾指针往后移：rear+1, 当 front == rear [空]
- 若尾指针 rear 小于队列的最小下标 maxSize - 1, 则将数据存入 rear 所指的数组元素中，否则无法存入数据。rear == maxSize - 1 [队列满]。
代码实现：
public class ArrayQueueDemo { | |
public static void main(String ... args){ | |
Scanner sc = new Scanner(System.in); | |
// 测试一把 | |
// 初始化队列 | |
ArrayQueue arrayQueue = new ArrayQueue(3); | |
// 接受用户输入 | |
char event_key = ' '; | |
boolean loop = true; | |
while(loop){ | |
// 显示菜单 | |
System.out.println("s(show): 显示队列"); | |
System.out.println("e(exit): 退出程序"); | |
System.out.println("a(add): 添加数据到队列"); | |
System.out.println("g(get): 从队列取出数据"); | |
System.out.println("h(head): 查看队列头的数据"); | |
System.out.println("============================"); | |
event_key = sc.next().charAt(0); | |
switch(event_key){ | |
case 's': | |
arrayQueue.showQueue(); | |
break; | |
case 'e': | |
sc.close(); | |
loop = false; | |
break; | |
case 'a': | |
System.out.println("请添加数据到队列中"); | |
int num = sc.nextInt(); | |
arrayQueue.addQueue(num); | |
break; | |
case 'g': | |
try{ | |
int value = arrayQueue.getQueue(); | |
System.out.println(value); | |
}catch(Exception e){ | |
System.out.println(e.getMessage()); | |
} | |
break; | |
case 'h': | |
try{ | |
int head = arrayQueue.headQueue(); | |
System.out.println(">> "+head); | |
}catch(Exception e){ | |
System.out.println(e.getMessage()); | |
} | |
break; | |
default: | |
System.out.println("请选择存在项"); | |
break; | |
} | |
} | |
System.out.println(">> 程序退出"); | |
} | |
} | |
// 使用数组模拟队列 - 编写一个 ArrayQueue 类 | |
class ArrayQueue { | |
// 表示数组的最大容量 | |
private int maxSize; | |
// 头：当取出元素时就向上移动，尾：当加入元素时就向上移动 | |
// 队列头 | |
private int front; | |
// 队列尾 | |
private int rear; | |
// 该数组用于存放数据，模拟队列 | |
private int[] arr; | |
// 创建队列的构造器 | |
public ArrayQueue (int maxSize) { | |
this.maxSize = maxSize; | |
arr = new int[maxSize]; | |
// 指向队列头部，分析出 front 是指向队列头的前一个位置 | |
front = -1; | |
// 指向队列尾，指向队列尾的数据 (即就是队列最后一个数据) | |
rear = -1; | |
} | |
// 判断队列是否满 | |
public boolean isFull(){ | |
return rear == maxSize - 1; | |
} | |
// 判断队列是否为空 | |
public boolean isEmpty(){ | |
return rear == front; | |
} | |
// 添加数据到队列 | |
public void addQueue(int n){ | |
// 判断队列是否满 | |
if(isFull()){ | |
System.out.println("队列满了不能加入数据了"); | |
return; | |
} | |
//rear 向后移 | |
rear++; | |
// 向数组中添加数据 | |
arr[rear] = n; | |
} | |
// 获取队列数据，出队列 | |
public int getQueue(){ | |
// 判断队列是否为空 | |
if(isEmpty()){ | |
// 抛出异常会导致程序停止相当于 return 终止程序了所以下面不能再写代码了 | |
throw new RuntimeException("队列为空"); | |
} | |
//front 向前移 | |
front++; | |
// 取出当前 front 位置的数组元素 | |
int result = arr[front]; | |
arr[front] = 0; | |
return result; | |
} | |
// 显示队列的所有数据 | |
public void showQueue(){ | |
// 判断队列是否为空 | |
if(isEmpty()){ | |
System.out.println("数组为空，没有数据"); | |
return; | |
} | |
// 数组遍历元素 | |
for(int i = 0;i < arr.length;i ++){ | |
System.out.printf(">> arr[%d]=%d\n",i,arr[i]); | |
} | |
} | |
// 显示队列头数据，注意：不能取出数据 | |
public int headQueue(){ | |
// 判断队列是否为空 | |
if(isEmpty()){ | |
throw new RuntimeException("队列为空"); | |
} | |
return arr[front + 1]; | |
} | |
} |
问题分析和优化：
- 目前数组使用一次就不能用，没有达到复用的效果
- 将这个数组使用算法，改进成一个环形的数组 取模:
%的方式来完成 (使用一个算法)。
# 数组模拟环形队列
对前面的数组模拟队列的优化，充分利用数组，因此将数组看做是一个环形的。(通过取模的方式来实现即可)
分析说明：
- 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定，这个在做判断队列满的时候需要注意 (rear + 1) % maxSize == front [满]
- rear == front [空]
- 测试示意图：
思路如下:
front 变量的含义做一个调整： front 就指向队列的第一个元素，也就是说 arr [front] 就是队列的第一个元素
front 的初始值 = 0
rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置。因为希望空出一个空间做为约定.
rear 的初始值 = 0
当队列满时，条件是 (rear + 1) % maxSize == front 【满】
对队列为空的条件， rear == front 空
当我们这样分析， 队列中有效的数据的个数 (rear + maxSize - front) % maxSize //rear = 1 front = 0
我们就可以在原来的队列上修改得到，一个环形队列
代码实现：
@SuppressWarnings("all") | |
public class ArrayQueueDemo01 { | |
public static void main(String ... args){ | |
Scanner sc = new Scanner(System.in); | |
// 测试一把 | |
// 初始化环形队列 | |
ArrayQueue01 arrayQueue = new ArrayQueue01(4);// 说明设置 4, 其队列的有效数据最大是 3. 空出了一个约定空间 | |
// 接受用户输入 | |
char event_key = ' '; | |
boolean loop = true; | |
while(loop){ | |
// 显示菜单 | |
System.out.println("s(show): 显示队列"); | |
System.out.println("e(exit): 退出程序"); | |
System.out.println("a(add): 添加数据到队列"); | |
System.out.println("g(get): 从队列取出数据"); | |
System.out.println("h(head): 查看队列头的数据"); | |
System.out.println("============================"); | |
event_key = sc.next().charAt(0); | |
switch(event_key){ | |
case 's': | |
try{ | |
arrayQueue.showQueue(); | |
}catch(Exception e){ | |
System.out.println(e.getMessage()); | |
} | |
break; | |
case 'e': | |
sc.close(); | |
loop = false; | |
break; | |
case 'a': | |
try{ | |
System.out.println("请添加数据到队列中"); | |
int num = sc.nextInt(); | |
arrayQueue.addQueue(num); | |
}catch(Exception e){ | |
System.out.println(e.getMessage()); | |
} | |
break; | |
case 'g': | |
try{ | |
int value = arrayQueue.getQueue(); | |
System.out.println(value); | |
}catch(Exception e){ | |
System.out.println(e.getMessage()); | |
} | |
break; | |
case 'h': | |
try{ | |
int head = arrayQueue.headQueue(); | |
System.out.println(">> "+head); | |
}catch(Exception e){ | |
System.out.println(e.getMessage()); | |
} | |
break; | |
default: | |
System.out.println("请选择存在项"); | |
break; | |
} | |
} | |
System.out.println(">> 程序退出"); | |
} | |
} | |
@SuppressWarnings("All") | |
class ArrayQueue01 { | |
private int front; | |
private int rear; | |
private int maxSize; | |
private int[] arr; | |
public ArrayQueue01 (int maxSize){ | |
this.maxSize = maxSize; | |
arr = new int[maxSize]; | |
} | |
// 判断队列是否满 | |
public boolean isFull(){ | |
return (rear + 1) % maxSize == front; | |
} | |
// 判断队列是否为空 | |
public boolean isEmpty(){ | |
return rear == front; | |
} | |
// 添加数据到队列 | |
public void addQueue(int n){ | |
// 判断队列是否满 | |
if(isFull()){ | |
throw new RuntimeException("队列满了，不能添加数据了"); | |
} | |
// 向数组进行赋值 | |
arr[rear] = n; | |
// 将 rear 向后移，考虑环形数组所以需要使用取模 | |
rear = (rear + 1) % maxSize; | |
} | |
// 获取队列的数据，出队列 | |
public int getQueue(){ | |
// 判断是否为空 | |
if(isEmpty()){ | |
throw new RuntimeException("队列没有数据"); | |
} | |
/** | |
* 这里需要分析出 front 是指向队列的第一个元素 | |
* 1. 先把 front，对应的值保留到一个临时变量 | |
* 2. 将 front 后移，考虑取模 | |
* 3. 降临时保存的变量返回 | |
*/ | |
int value = arr[front]; | |
front = (front + 1) % maxSize; | |
return value; | |
} | |
// 显示队列中所有数据 | |
public void showQueue(){ | |
// 判断队列是否为空 | |
if(isEmpty()){ | |
throw new RuntimeException("队列没有数据"); | |
} | |
for(int i = front;i < front + size();i ++){ | |
System.out.printf(">> arr[%d]=%d\n",i % maxSize,arr[i % maxSize]); | |
} | |
} | |
// 求出当前队列有效数据的个数 | |
public int size(){ | |
return (rear + maxSize - front) % maxSize; | |
} | |
// 显示队列的头元素 | |
public int headQueue(){ | |
if(isEmpty()){ | |
throw new RuntimeException("队列为空"); | |
} | |
return arr[front]; | |
} | |
} |
# 链表
链表是有序的列表，但是它在内存中是存储如下：
小结：
- 链表是以节点方式来存储，是链式存储。
- 每个节点包含 data 域，next 域：指向下一个节点。
- 如图：发现链表的各个节点不一定是连续存储。
- 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。
单链表 (带头节点) 逻辑结构示意图如下：并不是连续存储的。
单链表的应用实例:
使用带 head 头的单向链表实现 –水浒英雄排行榜管理
- 第一种方法在添加英雄时，直接添加到链表的尾部
- 思路分析示意图：
![]()
- 第二种方式在添加英雄时，根据排名将英雄插入到指定位置
(如果有这个排名，则添加失败，并给出提示)
- 思路分析示意图：
![]()
- 修改节点功能
- 思路：先找到该节点，通过遍历，temp.name = h.name;temp.nickname = h.nickname
- 删除节点
- 思路分析示意图：
![]()
# 单链表面试题 (新浪、百度、腾讯)
单链表的常见面试题有如下:
求单链表中有效节点的个数
/*** 方法：获取到单链表的节点的个数 (如果是带头节点的链表，需求不统计头节点)
* @param h 链表的头节点
* @return 返回的就是有效节点的个数
*/
public static int getLength(HeroNode h){
// 空链表直接返回 0if(h.next == null){
return 0;
}// 定义辅助变量，没有统计头节点，通过 h.next 直接获取下一个节点的数据HeroNode temp = h.next;
int count = 0;
while(temp != null){
count++;
temp = temp.next;
}// 返回有效的个数return count;
}查找单链表中的倒数第 k 个结点 【新浪面试题】
/*** 查找单链表中的倒数第 k 个节点 [新浪面试题]
* 思路：
* 1. 编写一个方法，接受 head 节点，同时接受一个 index
* 2.index 表示是倒数第 index 个节点
* 3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
* 4. 得到 size 后，我们从链表的第一个开始遍历 (size - index) 个，就可以得到
* 5. 如果找到了，则返回该节点，否则返回 null
* @param h
* @param index
* @return
*/
public static HeroNode findLastIndexNode(HeroNode h,int index){
// 判断如果链表为空，则返回 Nullif(h.next == null){
return null;
}// 第一个遍历得到链表的长度 (节点个数)int size = getLength(h);
// 第二次遍历，size - index 位置，就是我们倒数的第 k 个节点// 先做一个 index 的校验if(index <= 0 || index > size){
return null;
}// 定义辅助变量，for 循环定位到倒数的 index 数据HeroNode cur = h.next;
for(int i = 0;i < size - index;i ++){
cur = cur.next;
}return cur;
}单链表的反转【腾讯面试题，有点难度】
- 思路分析示意图：
![]()
/*** 将单链表反转 [腾讯面试题]
* @param h
*/
public static void reverseList(HeroNode h){
// 如果当前链表为空，或者只有一个节点，无需反转，直接返回if(h.next == null || h.next.next == null){
return ;
}// 定义一个辅助变量，帮助我们遍历原来的链表HeroNode cur = h.next;
// 指向当前节点 [cur] 的下一个节点HeroNode next = null;
HeroNode reverseHead = new HeroNode(0,"","");
// 遍历原来的链表，每遍历一个节点，就将其取出，并放在心的链表 reverseHead 的最前端while(cur != null){
// 先暂时保存当前节点的下一个节点，因为后面需要使用next = cur.next;
// 将 cur 的下一个节点指向新的链表的最前端cur.next = reverseHead.next;
// 将 cur 连接到新的链表上reverseHead.next = cur;
// 让 cur 后移cur = next;
}// 将 head.next 指向 reverseHead.next, 实现单链表的反转h.next = reverseHead.next;
}从尾到头打印单链表 (<font style="color:red"> 不破坏链表结构 </font>)【百度，要求方式 1：反向遍历 。 方式 2：Stack 栈】
- 思路分析示意图：
![]()
/*** 利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
* 这样就能保证链表本身的结构不发生变化
* @param h
*/
public static void reversePrint(HeroNode h){
// 判断链表是否为空if(h.next == null){
return;
}// 创建一个栈，将各个节点压入栈Stack<HeroNode> stack = new Stack<HeroNode>();
HeroNode cur = h.next;
// 将链表的所有节点压入栈while(cur != null){
// 入栈stack.push(cur);
// 向后移动，遍历节点cur = cur.next;
}// 将栈中的节点进行打印，pop 出栈while(stack.size() > 0){
System.out.println(stack.pop());
}}
完整代码实现：
@SuppressWarnings("all") | |
public class SingleLinkedList { | |
public static void main(String ... args){ | |
// 进行测试 | |
// 创建几个节点 | |
HeroNode h = new HeroNode(1,"松江","及时雨"); | |
HeroNode h1 = new HeroNode(2,"卢俊义","玉麒麟"); | |
HeroNode h2 = new HeroNode(3,"吴用","智多星"); | |
HeroNode h3 = new HeroNode(4,"林冲","豹子头"); | |
// 创建链表并加入链表中 | |
SingleLinkedListTwo linkedList = new SingleLinkedListTwo(); | |
// linkedList.add(h); | |
// linkedList.add(h3); | |
// linkedList.add(h2); | |
// linkedList.add(h1); | |
linkedList.addByOrder(h); | |
linkedList.addByOrder(h3); | |
linkedList.addByOrder(h2); | |
linkedList.addByOrder(h1); | |
System.out.println("正常情况下链表的数据"); | |
linkedList.list(); | |
linkedList.reverseList(linkedList.getHead()); | |
System.out.println("反转后的链表数据"); | |
linkedList.list(); | |
System.out.println("逆序打印链表的数据"); | |
linkedList.reversePrint(linkedList.getHead()); | |
/* | |
// 显示链表中的数据 | |
System.out.println ("修改之前的数据"); | |
linkedList.list (); | |
// 测试修改节点的代码 | |
HeroNode h02 = new HeroNode (2,"小卢","玉麒麟～～"); | |
linkedList.update (h02); | |
// 显示链表中的数据 | |
System.out.println ("修改之后的数据"); | |
linkedList.list (); | |
linkedList.del (2); | |
System.out.println ("删除后的数据"); | |
linkedList.list (); | |
linkedList.del (4); | |
System.out.println ("删除后的数据"); | |
linkedList.list (); | |
// 获取单链表的有效个数 | |
System.out.println ("返回有效数据个数："+linkedList.getLength (linkedList.getHead ())); | |
// 得到倒数第 k 个数据 | |
HeroNode result = linkedList.findLastIndexNode (linkedList.getHead (),1); | |
System.out.println ("倒数第 k 个节点的数据："+result); | |
*/ | |
} | |
} | |
// 定义 SingleLinkedListTwo 管理节点 | |
class SingleLinkedListTwo { | |
// 初始化头结点 | |
private HeroNode head = new HeroNode(0,"",""); | |
public HeroNode getHead(){ | |
return head; | |
} | |
/** | |
* 将单链表反转 | |
* @param h | |
*/ | |
public static void reverseList(HeroNode h){ | |
// 如果当前链表为空，或者只有一个节点，无需反转，直接返回 | |
if(h.next == null || h.next.next == null){ | |
return ; | |
} | |
// 定义一个辅助变量，帮助我们遍历原来的链表 | |
HeroNode cur = h.next; | |
// 指向当前节点 [cur] 的下一个节点 | |
HeroNode next = null; | |
HeroNode reverseHead = new HeroNode(0,"",""); | |
// 遍历原来的链表，每遍历一个节点，就将其取出，并放在心的链表 reverseHead 的最前端 | |
while(cur != null){ | |
// 先暂时保存当前节点的下一个节点，因为后面需要使用 | |
next = cur.next; | |
// 将 cur 的下一个节点指向新的链表的最前端 | |
cur.next = reverseHead.next; | |
// 将 cur 连接到新的链表上 | |
reverseHead.next = cur; | |
// 让 cur 后移 | |
cur = next; | |
} | |
// 将 head.next 指向 reverseHead.next, 实现单链表的反转 | |
h.next = reverseHead.next; | |
} | |
/** | |
* 利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果 | |
* 这样就能保证链表本身的结构不发生变化 | |
* @param h | |
*/ | |
public static void reversePrint(HeroNode h){ | |
// 判断链表是否为空 | |
if(h.next == null){ | |
return; | |
} | |
// 创建一个栈，将各个节点压入栈 | |
Stack<HeroNode> stack = new Stack<HeroNode>(); | |
HeroNode cur = h.next; | |
// 将链表的所有节点压入栈 | |
while(cur != null){ | |
// 入栈 | |
stack.push(cur); | |
// 向后移动，遍历节点 | |
cur = cur.next; | |
} | |
// 将栈中的节点进行打印，pop 出栈 | |
while(stack.size() > 0){ | |
System.out.println(stack.pop()); | |
} | |
} | |
// 添加节点到单向链表 | |
/** | |
* 思路：当不考虑编号顺序时 | |
* 1. 找到当前链表的最后节点 | |
* 2. 将最后这个节点的 next，指向 新的节点 | |
* @param h | |
*/ | |
public void add(HeroNode h){ | |
// 因为 head 节点不能动，因此我们需要一个辅助变量 temp | |
HeroNode temp = head; | |
// 遍历链表，找到最后 | |
while(true){ | |
// 找到链表的最后 | |
if(temp.next == null){ | |
break; | |
} | |
// 如果没有找到最后，就将 temp 后移 | |
temp = temp.next; | |
} | |
// 当退出 while 循环是，那么 temp 就指向了链表的最后 | |
// 将最后这个节点的 next，指向 新的节点 | |
temp.next = h; | |
} | |
/** | |
* 第二中方式在添加人物时，根据排名也就是编号，将人物插入到指定位置 | |
* (如果有这个排名，则添加失败，并给出提示) | |
* @param h | |
*/ | |
public void addByOrder(HeroNode h){ | |
// 因为头节点不能动，因此我们仍然通过一个辅助指针 (变量) 来帮助找到添加的位置 | |
// 因为单链表，因为我们找的 temp 是位于添加位置的前一个节点，否则插入不了 | |
HeroNode temp = head; | |
// 标示添加的编号是否存在，默认为 false | |
boolean flag = false; | |
while(true){ | |
// 说明 temp 已经在链表的最后 | |
if(temp.next == null){ | |
break; | |
} | |
// 位置找到，就在 temp 的后面插入 | |
if(temp.next.no > h.no){ | |
break; | |
// 说明希望添加的节点的编号已经存在了 | |
}else if(temp.next.no == h.no){ | |
flag = true; | |
break; | |
} | |
// 后移 | |
temp = temp.next; | |
} | |
if(flag){ | |
System.out.printf("添加的人物编号%d已经存在,不能重复添加",h.no); | |
}else{ | |
h.next = temp.next; | |
temp.next = h; | |
} | |
} | |
/** | |
* 修改节点的信息，根据 no 编号来修改，即 no 编号不能改 | |
* 说明： | |
* 1. 根据 h 的 no 来修改即可 | |
* @param h | |
*/ | |
public void update(HeroNode h){ | |
// 判断链表是否为空 | |
if(head.next == null){ | |
System.out.println("链表为空"); | |
return; | |
} | |
// 找到需要修改的节点，根据 no 编号 | |
// 定义一个辅助变量 | |
HeroNode temp = head.next; | |
// 标志 标记是否找到 | |
boolean flag = false; | |
while(true){ | |
// 判断是否遍历到链表的最后 | |
if(temp == null){ | |
break; | |
} | |
// 判断是否找到 | |
if(temp.no == h.no){ | |
flag = true; | |
break; | |
} | |
temp = temp.next; | |
} | |
if(flag){ | |
temp.name = h.name; | |
temp.nickName = h.nickName; | |
System.out.println("被修改的人物编号："+h.no); | |
}else{ | |
System.out.println("没有找到需要修改的编号，无法进行修改"); | |
} | |
} | |
/** | |
* 删除节点 | |
* 思路： | |
* 1.head 不能动，因此我们需要一个 temp 辅助节点找到待删除节点的前一个节点 | |
* 2. 说明我们在比较时，是 temp.next.no 和 需要删除的节点的 no 比较 | |
* @param no | |
*/ | |
public void del(int no){ | |
// 定义临时变量 | |
HeroNode temp = head; | |
// 标志，记录是否找到待删除节点 | |
boolean flag = false; | |
while(true){ | |
// 判断是否到链表的最后 | |
if(temp.next == null){ | |
break; | |
} | |
// 判断是否找到要删除的节点 | |
if(temp.next.no == no){ | |
// 标志设置可执行 | |
flag = true; | |
break; | |
} | |
// 向后移动 | |
temp = temp.next; | |
} | |
// 判断标志 | |
if(flag){ | |
// 将 temp 下一个引用指向 temp 下下个 next 那么中间的就没有引用了 jvm 就会做垃圾回收机制将其处理 | |
temp.next = temp.next.next; | |
}else{ | |
System.out.println("删除节点不存在"); | |
} | |
} | |
/** | |
* 查找单链表中的倒数第 k 个节点 [新浪面试题] | |
* 思路： | |
* 1. 编写一个方法，接受 head 节点，同时接受一个 index | |
* 2.index 表示是倒数第 index 个节点 | |
* 3. 先把链表从头到尾遍历，得到链表的总的长度 getLength | |
* 4. 得到 size 后，我们从链表的第一个开始遍历 (size - index) 个，就可以得到 | |
* 5. 如果找到了，则返回该节点，否则返回 null | |
* @param h | |
* @param index | |
* @return | |
*/ | |
public static HeroNode findLastIndexNode(HeroNode h,int index){ | |
// 判断如果链表为空，则返回 Null | |
if(h.next == null){ | |
return null; | |
} | |
// 第一个遍历得到链表的长度 (节点个数) | |
int size = getLength(h); | |
// 第二次遍历，size - index 位置，就是我们倒数的第 k 个节点 | |
// 先做一个 index 的校验 | |
if(index <= 0 || index > size){ | |
return null; | |
} | |
// 定义辅助变量，for 循环定位到倒数的 index 数据 | |
HeroNode cur = h.next; | |
for(int i = 0;i < size - index;i ++){ | |
cur = cur.next; | |
} | |
return cur; | |
} | |
/** | |
* 方法：获取到单链表的节点的个数 (如果是带头节点的链表，需求不统计头节点) | |
* @param h 链表的头节点 | |
* @return 返回的就是有效节点的个数 | |
*/ | |
public static int getLength(HeroNode h){ | |
// 空链表直接返回 0 | |
if(h.next == null){ | |
return 0; | |
} | |
// 定义辅助变量，没有统计头节点，通过 h.next 直接获取下一个节点的数据 | |
HeroNode temp = h.next; | |
int count = 0; | |
while(temp != null){ | |
count++; | |
temp = temp.next; | |
} | |
// 返回有效的个数 | |
return count; | |
} | |
/** | |
* 显示链表的数据 [遍历] | |
*/ | |
public void list(){ | |
// 判断链表是否为空 | |
if(head.next == null){ | |
System.out.println("链表为空"); | |
return; | |
} | |
// 因为头节点不能动，因此我们需要一个辅助变量来进行遍历 | |
HeroNode temp = head.next; | |
while(true){ | |
// 判断是否到链表的最后 | |
if(temp == null){ | |
// 结束循环 | |
break; | |
} | |
// 输出节点信息 | |
System.out.println(temp); | |
// 将 temp 向后移动，不后移就是死循环 | |
temp = temp.next; | |
} | |
} | |
} | |
// 定义 HeroNode 每个 HeroNode 对象就是一个节点 | |
class HeroNode { | |
public int no; | |
public String name; | |
public String nickName; | |
// 指向下一个节点 | |
public HeroNode next; | |
// 构造器 初始化 | |
public HeroNode(int no, String name, String nickName) { | |
this.no = no; | |
this.name = name; | |
this.nickName = nickName; | |
} | |
@Override | |
public String toString() { | |
return "HeroNode{" + | |
"no=" + no + | |
", name='" + name + '\'' + | |
", nickName='" + nickName + '\'' + | |
'}'; | |
} | |
} |
# 双向链表应用实例
使用带 head 头的双向链表实现 –水浒英雄排行榜
管理单向链表的缺点分析:
- 单向链表，查找的方向只能是一个方向，而双向链 表可以向前或者向后查找。
- 单向链表不能自我删除，需要靠辅助节点 ，而双向 链表，则可以自我删除，所以前面我们单链表删除 时节点，总是找到 temp,temp 是待删除节点的前一 个节点 (认真体会).
- 示意图帮助理解删除
分析 双向链表的遍历，添加，修改，删除的操作思路 ===》代码实现
- 遍历 方和 单链表一样，只是可以向前，也可以向后查找
- 添加 (默认添加到双向链表的最后)
- 先找到双向链表的最后这个节点
- temp.next = newHeroNode
- newHeroNode.pre = temp;
- 修改 思路和 原来的单向链表一样.
- 删除
- 因为是双向链表，因此，我们可以实现自我删除某个节点
- 直接找到要删除的这个节点，比如 temp
temp.pre.next = temp.next
temp.next.pre = temp.pre;
代码实现：
@SuppressWarnings("all") | |
public class DoubleLinkedListDemo { | |
public static void main(String ... args){ | |
System.out.println("双向链表的测试"); | |
DoubleLinkedList du = new DoubleLinkedList(); | |
HeroNode01 h = new HeroNode01(1,"松江","及时雨"); | |
HeroNode01 h1 = new HeroNode01(2,"卢俊义","玉麒麟"); | |
HeroNode01 h2 = new HeroNode01(3,"吴用","智多星"); | |
HeroNode01 h3 = new HeroNode01(4,"林冲","豹子头"); | |
du.addByOrder(h); | |
du.addByOrder(h3); | |
du.addByOrder(h2); | |
du.addByOrder(h1); | |
// System.out.println ("修改前的数据"); | |
du.list(); | |
// HeroNode01 h01 = new HeroNode01 (2,"小卢","玉麒麟～～"); | |
// du.update(h01); | |
// System.out.println ("修改后的数据"); | |
// du.list(); | |
// | |
// du.del(1); | |
// du.del(3); | |
// System.out.println ("删除后的数据"); | |
// du.list(); | |
} | |
} | |
class DoubleLinkedList { | |
// 初始化头节点，这个节点不动 | |
HeroNode01 head = new HeroNode01(0,"",""); | |
// 返回头节点 | |
public HeroNode01 getHead(){ | |
return head; | |
} | |
/** | |
* 有序添加元素 | |
* @param h | |
*/ | |
public void addByOrder(HeroNode01 h){ | |
HeroNode01 temp = head; | |
boolean flag = false; | |
while(true){ | |
if(temp.next == null){ | |
break; | |
} | |
if(temp.next.no > h.no){ | |
break; | |
}else if(temp.next.no == h.no){ | |
flag = true; | |
break; | |
} | |
temp = temp.next; | |
} | |
if(flag){ | |
System.out.printf("节点的主键(%d)存在重复",temp.next.no); | |
}else{ | |
/** | |
* 为防止出现空指针情况，需要对 temp 节点位置进行判断 | |
* 若双向链表尚未达尾端，则需要将 h 节点与其相邻的后面的节点进行连接 | |
*/ | |
if(temp.next != null){ | |
h.next = temp.next; | |
temp.next.pre = h; | |
} | |
// 无论双向链表是否达尾端，都需要将 h 节点与其相邻的前面的节点进行连接 | |
temp.next = h; | |
h.pre = temp; | |
} | |
} | |
/** | |
* 双向链表删除节点 | |
* 说明： | |
* 1. 对于双向链表，我们可以直接找到要删除这个节点 | |
* 2. 找到后，自我删除即可，而不用说找到删除节点的前一个节点然后进行删除 | |
* @param no | |
*/ | |
public void del(int no){ | |
HeroNode01 temp = head.next; | |
if(head.next == null){ | |
System.out.println("链表为空"); | |
return; | |
} | |
boolean flag = false; | |
while(true){ | |
if(temp == null){ | |
break; | |
} | |
if(temp.no == no){ | |
flag = true; | |
break; | |
} | |
temp = temp.next; | |
} | |
if(flag){ | |
/** | |
* 如果删除最后一个节点 | |
* 让当前要删除的节点的前一个节点的 next 指向下一个节点 | |
* 而后一个节点是 null 所以 next 为 null | |
*/ | |
temp.pre.next = temp.next; | |
/** | |
* 如果是最后一个节点执行下面操作会出现异常 | |
* 最后一个节点的 next 是空的 | |
* 所以 next 为 null 就不可能有 pre 因此就产生了问题 | |
* 最后一个节点的时候就不需要执行下面的操作了，否则报错 PointerException | |
* 判断后一个节点是否为 null 解决报错问题 | |
*/ | |
if(temp.next != null){ | |
temp.next.pre = temp.pre; | |
} | |
}else{ | |
System.out.println("没有可删除节点"); | |
} | |
} | |
public void update(HeroNode01 n){ | |
boolean flag = false; | |
if(head.next == null){ | |
System.out.println("链表为空"); | |
return ; | |
} | |
HeroNode01 temp = head.next; | |
while(true){ | |
if(temp.next == null){ | |
break; | |
} | |
if(temp.no == n.no){ | |
flag = true; | |
break; | |
} | |
temp = temp.next; | |
} | |
if(flag){ | |
temp.name = n.name; | |
temp.nickName = n.nickName; | |
System.out.println("修改的编号为："+temp.no); | |
}else{ | |
System.out.println("没有可修改的编号"); | |
} | |
} | |
// 双向链表的添加 | |
public void add(HeroNode01 h){ | |
HeroNode01 temp = head; | |
while(true){ | |
if(temp.next == null){ | |
break; | |
} | |
temp = temp.next; | |
} | |
temp.next = h; | |
h.pre = temp; | |
} | |
// 遍历双向链表的数据 | |
public void list(){ | |
// 判断链表是否为空 | |
if(head.next == null){ | |
System.out.println("链表为空"); | |
return ; | |
} | |
// 因为头结点不能动，所以需要使用辅助变量 | |
HeroNode01 temp = head.next; | |
while(true){ | |
// 遍历是否循环到链表最后 | |
if(temp == null){ | |
break; | |
} | |
System.out.println(temp); | |
temp = temp.next; | |
} | |
} | |
} | |
class HeroNode01 { | |
// 指向下一个节点，默认为 null | |
public HeroNode01 next; | |
// 指向前一个节点，默认为 null | |
public HeroNode01 pre; | |
public int no; | |
public String name; | |
public String nickName; | |
public HeroNode01(int no, String name, String nickName) { | |
this.no = no; | |
this.name = name; | |
this.nickName = nickName; | |
} | |
@Override | |
public String toString() { | |
return "HeroNode01{"+ | |
"no=" + no + | |
", name='" + name + '\'' + | |
", nickName='" + nickName + '\'' + | |
'}'; | |
} | |
} |
# 单向环形链表应用场景
Josephu (约瑟夫、约瑟夫环) 问题
Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
提示：用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。
单向环形链表介绍
Josephu 问题
ØJosephu 问题
Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
Ø 提示
用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。
Ø 示意图说明
约瑟夫问题 - 创建环形链表的思路图解：
约瑟夫问题 - 小孩出圈的思路分析图：
Josephu 代码实现：
package com.atguigu.linkedlist; | |
public class Josepfu { | |
public static void main(String[] args) { | |
// 测试一把看看构建环形链表，和遍历是否 ok | |
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(); | |
circleSingleLinkedList.addBoy(125);// 加入 5 个小孩节点 | |
circleSingleLinkedList.showBoy(); | |
// 测试一把小孩出圈是否正确 | |
circleSingleLinkedList.countBoy(10, 20, 125); // 2->4->1->5->3 | |
//String str = "7*2*2-5+1-5+3-3"; | |
} | |
} | |
// 创建一个环形的单向链表 | |
class CircleSingleLinkedList { | |
// 创建一个 first 节点，当前没有编号 | |
private Boy first = null; | |
// 添加小孩节点，构建成一个环形的链表 | |
public void addBoy(int nums) { | |
//nums 做一个数据校验 | |
if (nums < 1) { | |
System.out.println("nums的值不正确"); | |
return; | |
} | |
Boy curBoy = null; // 辅助指针，帮助构建环形链表 | |
// 使用 for 来创建我们的环形链表 | |
for (int i = 1; i <= nums; i++) { | |
// 根据编号，创建小孩节点 | |
Boy boy = new Boy(i); | |
// 如果是第一个小孩 | |
if (i == 1) { | |
first = boy; | |
first.setNext(first); // 构成环 | |
curBoy = first; // 让 curBoy 指向第一个小孩 | |
} else { | |
curBoy.setNext(boy);// | |
boy.setNext(first);// | |
curBoy = boy; | |
} | |
} | |
} | |
// 遍历当前的环形链表 | |
public void showBoy() { | |
// 判断链表是否为空 | |
if (first == null) { | |
System.out.println("没有任何小孩~~"); | |
return; | |
} | |
// 因为 first 不能动，因此我们仍然使用一个辅助指针完成遍历 | |
Boy curBoy = first; | |
while (true) { | |
System.out.printf("小孩的编号 %d \n", curBoy.getNo()); | |
if (curBoy.getNext() == first) {// 说明已经遍历完毕 | |
break; | |
} | |
curBoy = curBoy.getNext(); //curBoy 后移 | |
} | |
} | |
// 根据用户的输入，计算出小孩出圈的顺序 | |
/** | |
* | |
* @param startNo | |
* 表示从第几个小孩开始数数 | |
* @param countNum | |
* 表示数几下 | |
* @param nums | |
* 表示最初有多少小孩在圈中 | |
*/ | |
public void countBoy(int startNo, int countNum, int nums) { | |
// 先对数据进行校验 | |
if (first == null || startNo < 1 || startNo > nums) { | |
System.out.println("参数输入有误， 请重新输入"); | |
return; | |
} | |
// 创建要给辅助指针，帮助完成小孩出圈 | |
Boy helper = first; | |
// 需求创建一个辅助指针 (变量) helper , 事先应该指向环形链表的最后这个节点 | |
while (true) { | |
if (helper.getNext() == first) { // 说明 helper 指向最后小孩节点 | |
break; | |
} | |
helper = helper.getNext(); | |
} | |
// 小孩报数前，先让 first 和 helper 移动 k - 1 次 | |
for(int j = 0; j < startNo - 1; j++) { | |
//first 和 helper 一块向后移动它们两个始终都是围绕着我个环形 first 为头 helper 为绕环形最后一个 | |
first = first.getNext(); | |
helper = helper.getNext(); | |
} | |
// 当小孩报数时，让 first 和 helper 指针同时 的移动 m - 1 次，然后出圈 | |
// 这里是一个循环操作，知道圈中只有一个节点 | |
while(true) { | |
if(helper == first) { // 说明圈中只有一个节点 | |
break; | |
} | |
// 让 first 和 helper 指针同时 的移动 countNum - 1 | |
for(int j = 0; j < countNum - 1; j++) { | |
first = first.getNext(); | |
helper = helper.getNext(); | |
} | |
// 这时 first 指向的节点，就是要出圈的小孩节点 | |
System.out.printf("小孩%d出圈\n", first.getNo()); | |
// 这时将 first 指向的小孩节点出圈 | |
first = first.getNext(); | |
helper.setNext(first); // | |
} | |
System.out.printf("最后留在圈中的小孩编号%d \n", first.getNo()); | |
} | |
} | |
// 创建一个 Boy 类，表示一个节点 | |
class Boy { | |
private int no;// 编号 | |
private Boy next; // 指向下一个节点，默认 null | |
public Boy(int no) { | |
this.no = no; | |
} | |
public int getNo() { | |
return no; | |
} | |
public void setNo(int no) { | |
this.no = no; | |
} | |
public Boy getNext() { | |
return next; | |
} | |
public void setNext(Boy next) { | |
this.next = next; | |
} | |
} |
# 栈
栈的一个实际需求
请输入一个表达式
计算式:[722-5+1-5+3-3] 点击计算【如下图】
请问：计算机底层是如何运算得到结果的？ 注意不是简单的把算式列出运算，因为我们看这个算式 7 * 2 * 2 - 5, 但是计算机怎么理解这个算式的 (对计算机而言，它接收到的就是一个字符串)，我们讨论的是这个问题。-> 栈.
栈的介绍
- 栈的英文为 (stack)
- 栈是一个先入后出 (FILO-First In Last Out) 的有序列表。
- 栈 (stack) 是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶 (Top)，另一端为固定的一端，称为栈底 (Bottom)。
- 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
- 出栈 (pop) 和入栈 (push) 的概念 (如图所示)
栈的应用场景
- 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
- 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
- 表达式的转换 [中缀表达式转后缀表达式] 与求值 (实际解决)。
- 二叉树的遍历。
- 图形的深度优先 (depth 一 first) 搜索法。
栈的快速入门
- 用数组模拟栈的使用，由于栈是一种有序列表， 当然可以使用数组的结构来储存栈的数据内容， 下面我们就用数组模拟栈的出栈，入栈等操作。
- 实现思路分析，并画出示意图
代码实现：
public class ArrayStackDemo { | |
public static void main(String ... args){ | |
// 测试数组模拟栈是否正确 | |
// 先创建一个 ArrayStack 对象 --> 表示栈 | |
ArrayStack stack = new ArrayStack(4); | |
char key = ' '; | |
boolean flag = true; | |
Scanner sc = new Scanner(System.in); | |
while(flag){ | |
System.out.println("s(show): 展示栈数据"); | |
System.out.println("a(push): 向栈中添加数据(入栈)"); | |
System.out.println("g(pop): 弹出栈顶元素(出栈)"); | |
System.out.println("e(exit): 退出数组模拟栈程序"); | |
System.out.println("============================"); | |
key = sc.next().charAt(0); | |
switch(key){ | |
case 's': | |
try{ | |
stack.list(); | |
}catch(Exception e){ | |
System.out.println(e.getMessage()); | |
} | |
break; | |
case 'a': | |
try{ | |
System.out.println("请添加数据"); | |
int value = sc.nextInt(); | |
stack.push(value); | |
}catch(Exception e){ | |
System.out.println(e.getMessage()); | |
} | |
break; | |
case 'g': | |
try{ | |
int pop = stack.pop(); | |
System.out.printf("弹出栈顶元素：%d\n",pop); | |
}catch(Exception e){ | |
System.out.println(e.getMessage()); | |
} | |
break; | |
case 'e': | |
sc.close(); | |
flag = false; | |
break; | |
default: | |
System.out.println("请选择存在的选项"); | |
break; | |
} | |
} | |
} | |
} | |
class ArrayStack { | |
// 栈的大小 | |
private int maxSize; | |
// 数组模拟栈，数据存入该数组中 | |
private int[] stack; | |
//top 表示栈顶，初始化为 - 1 表示没有数据 | |
private int top = -1; | |
// 构造器 | |
public ArrayStack (int maxSize) { | |
this.maxSize = maxSize; | |
stack = new int[maxSize]; | |
} | |
// 栈满 | |
public boolean isFull(){ | |
return top == maxSize - 1; | |
} | |
// 栈空 | |
public boolean isEmpty(){ | |
return top == -1; | |
} | |
// 入栈 | |
public void push(int value){ | |
// 判断栈是否满了 | |
if(isFull()){ | |
throw new RuntimeException("栈满了"); | |
} | |
top++; | |
stack[top] = value; | |
} | |
// 出栈 | |
public int pop(){ | |
// 判断栈是否为空 | |
if(isEmpty()){ | |
throw new RuntimeException("栈为空"); | |
} | |
int value = stack[top]; | |
top--; | |
return value; | |
} | |
// 遍历栈，遍历时需要从栈顶开始遍历 | |
public void list(){ | |
if(isEmpty()){ | |
throw new RuntimeException("栈为空"); | |
} | |
for(int i = top;i >= 0;i --){ | |
System.out.printf(">> stack[%d] = %d\n",i,stack[i]); | |
} | |
} | |
} |
- 课堂练习，将老师写的程序改成使用链表来模拟栈
- 出栈的图解示意图
代码实现：
@SuppressWarnings("all") | |
public class LinkedListAnArrayStackDemo { | |
public static void main(String ... args) { | |
LinkedListDemo demo = new LinkedListDemo(); | |
char key = ' '; | |
boolean flag = true; | |
Scanner sc = new Scanner(System.in); | |
while(flag){ | |
System.out.println("a(push) 添加数据"); | |
System.out.println("s(list) 显示栈中所有数据"); | |
System.out.println("g(pop) 弹出栈顶元素"); | |
System.out.println("================="); | |
key = sc.next().charAt(0); | |
switch(key){ | |
case 'a': | |
try{ | |
System.out.println("请添加数据"); | |
int value = sc.nextInt(); | |
demo.add(value); | |
}catch(Exception e){ | |
System.out.println(e.getMessage()); | |
} | |
break; | |
case 'g': | |
try{ | |
int i = demo.get(); | |
System.out.println(">> 弹出元素为："+i); | |
}catch(Exception e){ | |
System.out.println(e.getMessage()); | |
} | |
break; | |
case 's': | |
try{ | |
demo.list(); | |
}catch(Exception e){ | |
System.out.println(e.getMessage()); | |
} | |
break; | |
default: | |
System.out.println("请选择存在选项"); | |
break; | |
} | |
} | |
} | |
} | |
class LinkedListDemo { | |
// 定义头节点 | |
private LinkedList stack = new LinkedList(0); | |
private LinkedList top = null; | |
public LinkedList getStack(){ | |
return stack; | |
} | |
// 入栈 | |
public void add(int h){ | |
LinkedList new_element = new LinkedList(h); | |
// 因为头节点不能动，需要一个辅助变量完成 | |
LinkedList temp = stack; | |
// 对链表进行遍历，遍历到最后一个节点即为链表的尾部，进行添加节点 | |
while(true){ | |
// 链表的最后 | |
if(temp.next == null){ | |
break; | |
} | |
// 移动节点位置 | |
temp = temp.next; | |
} | |
// 对节点的下一个节点进行赋值 | |
temp.next = new_element; | |
// 将 top 节点指向这个最后一个数据的节点 | |
top = new_element; | |
} | |
// 出栈 | |
public int get(){ | |
// 将 top 指针前移动一个 | |
// 需要重新遍历链表找到 top 节点的前一个节点，再由 top 指针指向这个节点 | |
LinkedList head = stack; | |
// 将 top 指针指向的节点出栈 | |
// 因为出站后，top 指针需要向前移动，所以需要一个辅助指针完成出栈 | |
LinkedList tmp = top; | |
// 判断栈是否为空 | |
if(head.next == null){ | |
throw new RuntimeException("栈为空"); | |
} | |
while(true){ | |
// 找到 head.next == null 节点的前一个节点 | |
if(head.next == top){ | |
break; | |
} | |
// 指针后移 | |
head = head.next; | |
} | |
// 退出循环后，找到 top 节点的前一个节点，对 head.next 节点进行删除赋值 null | |
// 因为 top.next 节点是 null, 而 head.next 节点就是 top.next 节点的上一个节点 | |
head.next = top.next; | |
// 将 top 指针指向这个节点，完成 top 指针的前移动作 | |
top = head; | |
// 返回前一个节点的 data 数据 | |
return tmp.data; | |
} | |
// 显示所有数据 | |
public void list(){ | |
LinkedList temp = stack; | |
if(temp.next == null){ | |
throw new RuntimeException("栈为空"); | |
} | |
int count = 0; | |
while(true){ | |
if(temp.next == null){ | |
break; | |
} | |
count++; | |
System.out.println(">> ("+count+")\t:\t"+temp.next.data); | |
temp = temp.next; | |
} | |
} | |
} | |
class LinkedList { | |
public int data; | |
public LinkedList next; | |
public LinkedList (int data) { | |
this.data = data; | |
} | |
} |
# 栈实现综合计算器
使用栈来实现综合计算器 - 自定义优先级 [priority]
Ø 简化思路:
- 3+2*6-2
- 30+2*6-2
- 722-5+1-5+3-4
使用栈完成表达式的计算 思路
通过一个 index 值（索引），来遍历我们的表达式
如果我们发现是一个数字，就直接入数栈
如果发现扫描到是一个符号，就分如下情况
3.1 如果发现当前的符号栈为 空，就直接入栈
3.2 如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符， 就需要从数栈中 pop 出两个数，在从符号栈中 pop 出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈 (* 计算后下一个就是当前的操作符 - 入栈)， 如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.当表达式扫描完毕，就顺序的从 数栈和符号栈中 pop 出相应的数和符号，并运行.
最后在数栈只有一个数字，就是表达式的结果
验证： 3+2*6-2 = 13
示意图：
代码实现：
@SuppressWarnings("all") | |
public class Calculator { | |
public static void main(String[] args) { | |
// 创建一个运算的表达式 | |
String expression = "(7-2)*3+1"; | |
// 创建两个栈，一个数栈，一个字符栈各自存储不同的东西 | |
ArrayStack02 numStack = new ArrayStack02(10); | |
ArrayStack02 operStack = new ArrayStack02(10); | |
// 定义需要的相关变量 | |
int index = 0;// 扫描表达式的 index 值 | |
int num1 = 0;// 从数栈中 pop 的第一个值 | |
int num2 = 0;// 从数栈中 pop 的第二个值 | |
int oper = 0;// 从字符栈中 pop 出的运算符 | |
int res = 0;// 从数栈中 pop 出两个数值计算的结果 | |
char ch = ' ';// 将每次扫描得到的 char 保存到 ch | |
String keepNum = "";// 用于拼接多位数 | |
// 开始 while 循环的扫描 expression 运算表达式 | |
while(true) { | |
// 依次得到 expression 的每一个字符 | |
ch = expression.substring(index, index+1).charAt(0); | |
// 判断 ch 是什么，然后做相应的处理 | |
if(operStack.isOper(ch)) {// 如果是运算符 | |
// 判断当前的符号栈是否为空 | |
if(!operStack.isEmpty()) { | |
// 如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符，就需要从数栈中 pop 出两个数， | |
// 这里需要判断是否此时的栈顶是否为左括号，如果是左括号不进入此循环 | |
// 我们设定的左括号是优先级大于加减乘除，所以当发现下一个进栈的符号的优先级比此时的栈顶的左括号优先级小的时候， | |
// 应该让符号直接进栈，不进行弹出左符号的运算（左括号弹出来运算是不行的） | |
if(operStack.priority(ch) <= operStack.priority(operStack.peek()) & operStack.peek() != 40) { | |
num1 = numStack.pop(); | |
num2 = numStack.pop(); | |
oper = operStack.pop(); | |
res = numStack.cal(num1, num2, oper); | |
// 把运算的结果如数栈 | |
numStack.push(res); | |
// 然后将当前的操作符入符号栈 | |
operStack.push(ch); | |
/** | |
* 进行右括号的判断。匹配左括号 | |
* 当发现进入的是右括号时就优先进行括号内的计算 | |
*/ | |
} else if(ch == 41){ | |
// 先让右括号进栈 | |
operStack.push(ch); | |
if (ch == 41) { | |
// 再把右括号弹出 | |
int oper1 = operStack.pop(); | |
// 弹出右括号后开始进行括号内运算 | |
while(true) { | |
// 右括号 | |
num1 = numStack.pop(); | |
num2 = numStack.pop(); | |
oper = operStack.pop(); | |
res = numStack.cal(num1, num2, oper); | |
// 把运算的结果如数栈 | |
numStack.push(res); | |
// 当运算到栈顶符号为左括号时候，就弹出栈顶元素左括号，结束循环 | |
if(operStack.peek() == 40) { | |
int oper2 = operStack.pop(); | |
break; | |
} | |
} | |
} | |
// 如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈. | |
} | |
else { | |
operStack.push(ch); | |
} | |
}else { | |
// 如果为空直接入符号栈 | |
operStack.push(ch); | |
} | |
} else { // 如果是数，则直接入数栈 | |
// 分析思路 | |
//1. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数 | |
//2. 在处理数，需要向 expression 的表达式的 index 后再看一位，如果是数就进行扫描，如果是符号才入栈 | |
//3. 因此我们需要定义一个变量 字符串，用于拼接 | |
// 处理多位数 | |
keepNum += ch; | |
// 如果 ch 已经是 expression 的最后一位，就直接入栈 | |
if (index == expression.length() - 1) { | |
numStack.push(Integer.parseInt(keepNum)); | |
}else{ | |
// 判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈 | |
// 注意是看后一位，不是 index++ | |
if (operStack.isOper(expression.substring(index+1,index+2).charAt(0))) { | |
// 如果后一位是运算符，则入栈 keepNum = "1" 或者 "123" | |
numStack.push(Integer.parseInt(keepNum)); | |
// 重要的！！！！！！，keepNum 清空 | |
keepNum = ""; | |
} | |
} | |
} | |
// 让 index + 1, 并判断是否扫描到 expression 最后. | |
index++; | |
if (index >= expression.length()) { | |
break; | |
} | |
} | |
// 当表达式扫描完毕，就顺序的从数栈和符号栈中 pop 出相应的数和符号，并运行 | |
while(true){ | |
// 如果符号栈为空，则计算到最后的结果，数栈中只有一个数字 [结果] | |
if(operStack.isEmpty()){ | |
break; | |
} | |
num1 = numStack.pop(); | |
num2 = numStack.pop(); | |
oper = operStack.pop(); | |
res = numStack.cal(num1,num2,oper); | |
numStack.push(res);// 入栈 | |
} | |
// 将数栈的最后数，pop 出，就是结果 | |
int res2 = numStack.pop(); | |
System.out.printf("表达式%s = %d",expression,res2); | |
} | |
} | |
@SuppressWarnings("all") | |
class ArrayStack02 { | |
// 栈的大小 | |
private int maxSize; | |
// 数组模拟栈，数据存入该数组中 | |
private int[] stack; | |
//top 表示栈顶，初始化为 - 1 表示没有数据 | |
private int top = -1; | |
// 构造器 | |
public ArrayStack02 (int maxSize) { | |
this.maxSize = maxSize; | |
stack = new int[this.maxSize]; | |
} | |
// 增加一个方法，可以返回当前栈顶的值，但是不是真正的 pop | |
public int peek(){ | |
return stack[top]; | |
} | |
// 栈满 | |
public boolean isFull(){ | |
return top == maxSize - 1; | |
} | |
// 栈空 | |
public boolean isEmpty(){ | |
return top == -1; | |
} | |
// 入栈 | |
public void push(int value){ | |
// 判断栈是否满了 | |
if(isFull()){ | |
throw new RuntimeException("栈满了"); | |
} | |
top++; | |
stack[top] = value; | |
} | |
// 出栈 | |
public int pop(){ | |
// 判断栈是否为空 | |
if(isEmpty()){ | |
throw new RuntimeException("栈为空"); | |
} | |
int value = stack[top]; | |
top--; | |
return value; | |
} | |
// 遍历栈，遍历时需要从栈顶开始遍历 | |
public void list(){ | |
if(isEmpty()){ | |
throw new RuntimeException("栈为空"); | |
} | |
for(int i = top;i >= 0;i --){ | |
System.out.printf(">> stack[%d] = %d\n",i,stack[i]); | |
} | |
} | |
/** | |
* 返回运算符的优先级，优先级是程序员来确定，优先级使用数字表示 | |
* 数字越大，则优先级越高 | |
* @return | |
*/ | |
public int priority(int oper){ | |
if(oper == '(' || oper == ')'){ | |
return 2; | |
}else if(oper == '*' || oper == '/'){ | |
return 1; | |
}else if(oper == '+' || oper == '-'){ | |
return 0; | |
}else{ | |
return -1;// 假设目前的表达式只有 + - * / | |
} | |
} | |
/** | |
* 判断是否为一个运算符 | |
* @return | |
*/ | |
public boolean isOper(char val){ | |
return val == '+' || val == '-' || val == '*' || val == '/' || val == '(' | |
|| val == ')'; | |
} | |
/** | |
* 计算方法 | |
* @return | |
*/ | |
public int cal(int num1,int num2,int oper){ | |
int res = 0; | |
//TODO 注意计算的顺序 | |
switch(oper){ | |
case '+': | |
res = num1 + num2; | |
break; | |
case '-': | |
res = num2 - num1; | |
break; | |
case '*': | |
res = num1 * num2; | |
break; | |
case '/': | |
res = num2 / num1; | |
break; | |
default: | |
System.out.println("计算错误"); | |
break; | |
} | |
return res; | |
} | |
} |
# 前缀、中缀、后缀表达式 (逆波兰表达式)
# 前缀表达式 (波兰表达式)
- 前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
- 举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6
前缀表达式的计算机求值
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
例如: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:
- 从右至左扫描，将 6、5、4、3 压入堆栈
- 遇到 + 运算符，因此弹出 3 和 4（3 为栈顶元素，4 为次顶元素），计算出 3+4 的值，得 7，再将 7 入栈
- 接下来是 × 运算符，因此弹出 7 和 5，计算出 7×5=35，将 35 入栈
- 最后是 - 运算符，计算出 35-6 的值，即 29，由此得出最终结果
# 中缀表达式
- 中缀表达式就是常见的运算表达式，如 (3+4)×5-6
- 中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作 (前面我们讲的案例就能看的这个问题)，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作 (一般转成后缀表达式.)
# 后缀表达式
- 后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后
- 中举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –
- 再比如:
| 正常的表达式 | 逆波兰表达式 |
|---|---|
| a+b | a b + |
| a+(b-c) | a b c - + |
| a+(b-c)*d | a b c - d * + |
| a+d*(b-c) | a d b c - * + |
| a=1+3 | a 1 3 + = |
后缀表达式的计算机求值
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
- 从左至右扫描，将 3 和 4 压入堆栈；
- 遇到 + 运算符，因此弹出 4 和 3（4 为栈顶元素，3 为次顶元素），计算出 3+4 的值，得 7，再将 7 入栈；
- 将 5 入栈；
- 接下来是 × 运算符，因此弹出 5 和 7，计算出 7×5=35，将 35 入栈；
- 将 6 入栈；
- 最后是 - 运算符，计算出 35-6 的值，即 29，由此得出最终结果
# 中缀转后缀表达式
大家看到，后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将 中缀表达式转成后缀表达式。
具体步骤如下：
- 初始化两个栈：运算符栈 s1 和储存中间结果的栈 s2
- 从左至右扫描中缀表达式
- 遇到操作数时，将其压 s2
- 遇到运算符时，比较其与 s1 栈顶运算符的优先级：
- 如果 s1 为空，或栈顶运算符为左括号 “(”，则直接将此运算符入栈
- 否则，若优先级比栈顶运算符的高，也将运算符压入 s1
- 否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到 (4-1) 与 s1 中新的栈顶运算符相比较
- 遇到括号时:
- 如果是左括号 “(”，则直接压入 s1
- 如果是右括号 “)”，则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到左括号为止，此时将这一对括号丢弃
- 重复步骤 2 至 5，直到表达式的最右边
- 将 s1 中剩余的运算符依次弹出并压入 s2
- 依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
示意图：
中缀表达式 转 后缀表达式的 思路步骤分析
打比方 ： 降龙十八掌 ：学习 -》 应用 [层次]
算法 -》 第一个层面： 理解算法 -》灵活运用算法
第二层： 设计算法 -》 运用 【】
举例说明：
将中缀表达式 **"1+((2+3)×4)-5"** 转换为后缀表达式的过程如下:
因此结果为 **"1 2 3 + 4 × + 5 –"**
| 扫描到的元素 | s2 (栈底 -> 栈顶) | s1 (栈底 -> 栈顶) | 说明 |
|---|---|---|---|
| 1 | 1 | 空 | 数字，直接入栈 |
| + | 1 | + | s1 为空，运算符直接入栈 |
| ( | 1 | + ( | 左括号，直接入栈 |
| ( | 1 | + ( ( | 同上 |
| 2 | 1 2 | + ( ( | 数字 |
| + | 1 2 | + ( ( + | s1 栈顶为左括号，运算符直接入栈 |
| 3 | 1 2 3 | + ( ( + | 数字 |
| ) | 1 2 3 + | + ( | 右括号，弹出运算符直至遇到左括号 |
| × | 1 2 3 + | + ( × | s1 栈顶为左括号，运算符直接入栈 |
| 4 | 1 2 3 + 4 | + ( × | 数字 |
| ) | 1 2 3 + 4 × | + | 右括号，弹出运算符直至遇到左括号 |
| - | 1 2 3 + 4 × + | - | - 与 + 优先级相同，因此弹出 +，再压入 - |
| 5 | 1 2 3 + 4 × + 5 | - | 数字 |
| 到达最右端 | 1 2 3 + 4 × + 5 - | 空 | s1 中剩余的运算符 |
代码实现：
@SuppressWarnings("all") | |
public class PolandNotation { | |
public static void main(String[] args) { | |
// 定义中缀表达式 | |
String suffixExpression = "1+((2+3)x4)-5"; | |
/** | |
* 完成将一个中缀表达式转成后缀表达式的功能 | |
* 说明： | |
* 1.1+((2+3) x4)-5 => 1 2 3 + 4 x + 5 - | |
* 2. 因为直接对 str 进行操作，不太方便，因此 先将 “1+((2+3) x4)-5” => 中缀的表达式对应的 List 即 "1+((2+3) x4)-5" | |
* => ArrayList [1,2,3,+,4,x,+,5,-] | |
* 3. 将得到的中缀表达式对应的 List => 后缀表达式对应的 List 即 ArrayList [1+((2+3) x4)-5] | |
* => ArrayList [1,2,3,+,4,x,+,5,-] | |
*/ | |
List<String> resultList = toInfixExpressionList(suffixExpression); | |
System.out.println(resultList);//[1, +, (, (, 2, +, 3, ), x, 4, ), -, 5] | |
List<String> resultList1 = parseSuffixExpressionList(resultList); | |
System.out.println(resultList1); | |
System.out.printf("逆波兰表达式运算结果: %d",calculate(resultList1)); | |
} | |
/** | |
* 将一个逆波兰表达式，依次将数据和运算符，放入到 ArrayList 中 | |
* @param suffixExpression | |
* @return | |
*/ | |
public static List<String> getListString(String suffixExpression){ | |
// 将 suffixExpression 分割 | |
List<String> list = new ArrayList<>(); | |
String[] split = suffixExpression.split(" "); | |
for(String ele:split){ | |
list.add(ele); | |
} | |
return list; | |
} | |
/** | |
* 即 ArrayList [1, +, (, (, 2, +, 3,), x, 4, ), -, 5] => ArrayList [1,2,3,+,4,*,+,5,-] | |
* 方法：将得到的中缀表达式对应的 List => 后缀表达式对应的 List | |
* @param list | |
* @return | |
*/ | |
public static List<String> parseSuffixExpressionList(List<String> list){ | |
// 定义一个栈一个集合 | |
Stack<String> stack = new Stack<>(); | |
/** | |
* 说明：因为 ls 这个栈，在整个转换过程中，没有 pop 操作，而且后面我们还需要逆序输出 | |
* 因此比较麻烦，这里我们就不用 Stack<String > 直接使用 List<String> ls | |
* Stack<String> ls = new Stack<String>(); 存储中间结果的栈 ls | |
*/ | |
List<String> ls = new ArrayList<>(); | |
// 遍历 List 集合中的数据 | |
for(String i:list){ | |
// 如果是一个数，加入 List 集合中 | |
if(i.matches("\\d+")){ | |
ls.add(i); | |
}else if(i.equals("(")){ | |
stack.push(i); | |
}else if(i.equals(")")){ | |
// 如果是右括号 ")", 则依次弹出 Stack 栈顶的运算符，并压入 List 集合，直到遇到左括号为止，此时将一对括号丢弃 | |
while(!stack.peek().equals("(")){ | |
ls.add(stack.pop()); | |
} | |
stack.pop(); | |
}else{ | |
/** | |
* 当 item 的优先级小于等于 stack 栈顶运算符，将 stack 栈顶的运算符弹出并加入到 list 中，再次转到 (4.1) 与 stack 中新的 | |
* 栈顶运算符相比较 | |
* 问题：我们缺少一个比较优先级高低的方法 | |
*/ | |
while(stack.size() != 0 && Operation.getValue(stack.peek()) >= Operation.getValue(i)){ | |
ls.add(stack.pop()); | |
} | |
// 还需要将 i 压入栈 | |
stack.push(i); | |
} | |
} | |
// 将 stack 中剩余的运算符依次弹出并加入 list 中 | |
while(stack.size() != 0){ | |
ls.add(stack.pop()); | |
} | |
return ls; | |
} | |
/** | |
* 方法：将中缀表达式转成对应的 list | |
* s = "1+((2+3) x4)-5"; | |
* @param s | |
* @return | |
*/ | |
public static List<String> toInfixExpressionList(String s){ | |
// 定义一个 List，存放中缀表达式对应的内容 | |
List<String> list = new ArrayList<>(); | |
// 这是一个指针，用于遍历中缀表达式字符串 | |
int i = 0; | |
// 对多位数的拼接 | |
String str; | |
// 每遍历到一个字符， 就放入到 ch | |
char ch; | |
do{ | |
// 如果 ch 是一个非数组，我们需要加入到 list 集合中 | |
if((ch = s.charAt(i)) < 48 || (ch = s.charAt(i)) > 57){ | |
list.add(ch + ""); | |
//i 指针后移 | |
i++; | |
}else{ | |
// 如果是一个数，需要考虑多位数 | |
// 先将 str 置成空字符串 "" '0'[48] -> '9'[57] | |
str = ""; | |
while(i < s.length() && (ch = s.charAt(i)) >= 48 && (ch = s.charAt(i)) <= 57){ | |
// 拼接多位数 | |
str += ch; | |
//i 指针后移 | |
i++; | |
} | |
list.add(str); | |
} | |
}while(i < s.length()); | |
return list; | |
} | |
/** | |
* 完成对逆波兰表达式的运算 | |
* 1. 从左至右扫描，将 3 和 4 压入栈 | |
* 2. 遇到 + 运算符，因此弹出 4 和 3 (4 为栈顶元素，3 为次顶元素), 计算出 3+4 的值，得 7，再将 7 入栈 | |
* 3. 将 5 入栈 | |
* 4. 接下来是 x 运算符，因此弹出 5 和 7，计算出 7x5=35, 将 35 入栈 | |
* 5. 将 6 入栈 | |
* 6. 最后是 - 运算符，计算出 35-6 的值，即 29，由此得出最终结果 | |
* @param list | |
* @return | |
*/ | |
public static int calculate(List<String> list){ | |
// 创建一个栈，只需要一个栈即可 | |
Stack<String> stack = new Stack<>(); | |
for(String i:list){ | |
if(i.matches("\\d+")){ | |
stack.add(i); | |
}else{ | |
//pop 出两个数，并运算，再入栈 | |
int num2 = Integer.parseInt(stack.pop()); | |
int num1 = Integer.parseInt(stack.pop()); | |
int res = 0; | |
if(i.equals("+")){ | |
res = num1 + num2; | |
}else if(i.equals("-")){ | |
res = num1 - num2; | |
}else if(i.equals("x")){ | |
res = num1 * num2; | |
}else if(i.equals("/")){ | |
res = num1 / num2; | |
}else{ | |
throw new RuntimeException("您输入的逆波兰表达式有问题不能计算"); | |
} | |
// 把结果压入栈中 | |
stack.push(res+""); | |
} | |
} | |
// 最后留在栈中的数据是运算结果 | |
return Integer.parseInt(stack.pop()); | |
} | |
} | |
// 编写一个类 Operation 可以返回一个运算符对应的优先级 | |
class Operation { | |
private static int ADD = 1; | |
private static int SUB = 1; | |
private static int MUL = 2; | |
private static int DIV = 2; | |
// 写一个方法，返回对应的优先级数字 | |
public static int getValue(String key){ | |
int result = 0; | |
switch(key){ | |
case "+": | |
result = ADD; | |
break; | |
case "-": | |
result = SUB; | |
break; | |
case "x": | |
result = MUL; | |
break; | |
case "/": | |
result = DIV; | |
break; | |
default: | |
System.out.println("操作符发生了错误"); | |
break; | |
} | |
return result; | |
} | |
} |
# 逆波兰计算器
我们完成一个逆波兰计算器，要求完成如下任务：
- 输入一个逆波兰表达式 (后缀表达式)，使用栈 (stack)，计算其结果
- 支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算
- 思路分析
- 从左至右扫描，将 3 和 4 压入栈
- 遇到 + 运算符，因此弹出 4 和 3 (4 为栈顶元素，3 为次顶元素)，计算出 3+4 的值，得 7，再将 7 入栈
- 将 5 入栈
- 接下来是 x 运算符，因此弹出 5 和 7，计算出 7x5=35，将 35 入栈
- 将 6 入栈
- 最后是 - 运算符，计算出 35-6 的值，即 29，由此得出最终结果
- 代码完成：
@SuppressWarnings("all") | |
public class PolandNotation { | |
public static void main(String[] args) { | |
// 定义逆波兰表达式 | |
// 说明：为了方便，逆波兰表达式的数字和符号使用空格隔开 | |
String suffixExpression = "3 4 + 5 x 6 -"; | |
/** | |
* 1. 先将 "3 4 + 5 x 6 -" => 放到 ArrayList 中 | |
* 2. 将 ArrayList 传递给一个方法，遍历 ArrayList 配置栈 完成计算 | |
*/ | |
List<String> listString = getListString(suffixExpression); | |
int calculate = calculate(listString); | |
System.out.println(">> 逆波兰表达式运算结果："+calculate); | |
} | |
/** | |
* 将一个逆波兰表达式，依次将数据和运算符，放入到 ArrayList 中 | |
* @param suffixExpression | |
* @return | |
*/ | |
public static List<String> getListString(String suffixExpression){ | |
// 将 suffixExpression 分割 | |
List<String> list = new ArrayList<>(); | |
String[] split = suffixExpression.split(" "); | |
for(String ele:split){ | |
list.add(ele); | |
} | |
return list; | |
} | |
/** | |
* 完成对逆波兰表达式的运算 | |
* 1. 从左至右扫描，将 3 和 4 压入栈 | |
* 2. 遇到 + 运算符，因此弹出 4 和 3 (4 为栈顶元素，3 为次顶元素), 计算出 3+4 的值，得 7，再将 7 入栈 | |
* 3. 将 5 入栈 | |
* 4. 接下来是 x 运算符，因此弹出 5 和 7，计算出 7x5=35, 将 35 入栈 | |
* 5. 将 6 入栈 | |
* 6. 最后是 - 运算符，计算出 35-6 的值，即 29，由此得出最终结果 | |
* @param list | |
* @return | |
*/ | |
public static int calculate(List<String> list){ | |
// 创建一个栈，只需要一个栈即可 | |
Stack<String> stack = new Stack<>(); | |
for(String i:list){ | |
if(i.matches("\\d+")){ | |
stack.add(i); | |
}else{ | |
//pop 出两个数，并运算，再入栈 | |
int num2 = Integer.parseInt(stack.pop()); | |
int num1 = Integer.parseInt(stack.pop()); | |
int res = 0; | |
if(i.equals("+")){ | |
res = num1 + num2; | |
}else if(i.equals("-")){ | |
res = num1 - num2; | |
}else if(i.equals("x")){ | |
res = num1 * num2; | |
}else if(i.equals("/")){ | |
res = num1 / num2; | |
}else{ | |
throw new RuntimeException("您输入的逆波兰表达式有问题不能计算"); | |
} | |
// 把结果压入栈中 | |
stack.push(res+""); | |
} | |
} | |
// 最后留在栈中的数据是运算结果 | |
return Integer.parseInt(stack.pop()); | |
} | |
} |
# 递归
递归应用场景
看个实际应用场景，迷宫问题 (回溯)， 递归 (Recursion)
递归的概念
简单的说：递归就是方法自己调用自己，每次调用时传入不同的变量。递归有助于编程者解决复杂的问题，同时可以让代码变得简洁。
递归调用机制
我列举两个小案例，来帮助大家理解递归，部分学员已经学习过递归了，这里在给大家回顾一下递归调用机制
- 打印问题
// 输出什么？ | |
public static void test(int n) { | |
if (n > 2) { | |
test(n - 1); | |
} | |
System.out.println("n=" + n); | |
} |
- 阶乘问题
// 阶乘 | |
public static int factorial(int n) { | |
if (n == 1) { | |
return 1; | |
} else { | |
return factorial(n - 1) * n; | |
} | |
} |
示意图：
递归能解决什么样的问题
递归用于解决什么样的问题
- 各种数学问题如: 8 皇后问题，汉诺塔，阶乘问题，迷宫问题，球和篮子的问题 (google 编程大赛)
- 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.
- 将用栈解决的问题 --> 递归代码比较简洁
递归需要遵守的重要规则
递归需要遵守的重要规则
- 执行一个方法时，就创建一个新的受保护的独立空间 (栈空间)
- 方法的局部变量是独立的，不会相互影响，比如 n 变量
- 如果方法中使用的是引用类型变量 (比如数组)，就会共享该引用类型的数据.
- 递归必须向退出递归的条件逼近，否则就是无限递归，出现 StackOverflowError，死归了：)
- 当一个方法执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。
# 递归 - 迷宫问题
说明:
- 小球得到的路径，和程序员 设置的找路策略有关即：找 路的上下左右的顺序相关
- 再得到小球路径时，可以先 使用 (下右上左)，再改成 (上 右下左)，看看路径是不是有变化
- 测试回溯现象
- 创建一面墙将小球堵住
// 使用二维数组模拟迷宫// 地图int[][] arr = new int[8][7];
// 生成地图的地形for(int i = 0;i < arr[0].length;i ++){
arr[0][i] = 1;
arr[arr.length - 1][i] = 1;
arr[i][0] = 1;
arr[i][arr[0].length - 1] = 1;
}// 添加地形中的一面阻碍的墙arr[3][1] = 1;
arr[3][2] = 1;
// 添加一面墙将小球堵死arr[1][2] = 1;
arr[2][2] = 1;
- 思考：如何求出最短路径？
代码实现：
public class MiGong { | |
public static void main(String[] args) { | |
// 使用二维数组模拟迷宫 | |
// 地图 | |
int[][] arr = new int[8][7]; | |
// 生成地图的地形 | |
for(int i = 0;i < arr[0].length;i ++){ | |
arr[0][i] = 1; | |
arr[arr.length - 1][i] = 1; | |
arr[i][0] = 1; | |
arr[i][arr[0].length - 1] = 1; | |
} | |
// 添加地形中的一面阻碍的墙 | |
arr[3][1] = 1; | |
arr[3][2] = 1; | |
// 添加一面墙将小球堵死 | |
// arr[1][2] = 1; | |
// arr[2][2] = 1; | |
System.out.println("输出地图情况"); | |
for(int[] temp:arr){ | |
for(int i:temp){ | |
System.out.print("\t\t"+i); | |
} | |
System.out.println(); | |
} | |
boolean flag = setWay01(arr,1,1); | |
System.out.println(flag); | |
// 输出新的地图，小球走过并标识过的地图 | |
System.out.println("小球走过并标识的 输出地图情况"); | |
for(int[] temp:arr){ | |
for(int i:temp){ | |
System.out.print("\t\t"+i); | |
} | |
System.out.println(); | |
} | |
} | |
/** | |
* 说明： | |
* 使用递归回溯给小球找路 | |
* @param arr 表示地图 | |
* @param i 表示从哪个位置开始找 | |
* @param j 表示从哪个位置开始找 | |
* i j : 表示的是地图中的位置坐标点 | |
* @return 如果找到了通路返回 true 否则返回 false | |
* 1. 规则: | |
* 如果小球找到 int [6][5] 则说明通路找到了 | |
* 2. 约定: | |
* 当 int [i][j] 为 0 时表示位置没有走过，当为 1 表示为墙不能越过，2 表示通路可以走，3 表示该位置已经走过了但是走不通 | |
* 3. 策略: | |
* 走迷宫时需要确定一个策略 (思考的方法) 下 -> 右 -> 上 -> 左。如果该点走不通再回溯 | |
*/ | |
public static boolean setWay(int[][] arr,int i,int j){ | |
if(arr[6][5] == 2){// 通路已经找到 | |
return true; | |
}else{ | |
if(arr[i][j] == 0){ // 判断如果这个点还没走过 | |
arr[i][j] = 2; | |
if(setWay(arr,i+1,j)){ // 下走 | |
return true; | |
}else if(setWay(arr,i,j+1)){ // 右走 | |
return true; | |
}else if(setWay(arr,i-1,j)){ // 上走 | |
return true; | |
}else if(setWay(arr,i,j-1)){ // 左走 | |
return true; | |
}else{ // 走不同 标记为 3 | |
arr[i][j] = 3; | |
// 返回 false | |
return false; | |
} | |
}else{ | |
// 如果 arr [i][j] != 0，可能是 1,2,3 | |
return false; | |
} | |
} | |
} | |
/** | |
* 怎么走出迷宫是代码决定的，换一种思路走出迷宫 | |
* @param arr 表示地图 | |
* @param i 表示球的位置 | |
* @param j 表示球的位置 | |
* @return 返回 true 表示走出迷宫，false 表示没有走出迷宫 | |
*/ | |
public static boolean setWay01(int[][] arr,int i,int j){ | |
if(arr[6][5] == 2){ | |
return true; | |
}else if(arr[i][j] == 0){ | |
arr[i][j] = 2; | |
if(setWay01(arr,i-1,j)){// 上 | |
return true; | |
}else if(setWay01(arr,i,j+1)){// 右 | |
return true; | |
}else if(setWay01(arr,i+1,j)){// 下 | |
return true; | |
}else if(setWay01(arr,i,j-1)){// 左 | |
return true; | |
}else{ | |
arr[i][j] = 3; | |
return false; | |
} | |
}else{ | |
return false; | |
} | |
} | |
} |
# 递归 - 八皇后问题 (回溯算法)
八皇后问题介绍
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯・贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法 (92)。
八皇后问题算法思路分析
- 第一个皇后先放第一行第一列
- 第二个皇后放在第二行第一列、然后判断是否 OK， 如果不 OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
- 继续第三个皇后，还是第一列、第二列…… 直到第 8 个皇后也能放在一个不冲突的位置，算是找到了一个正确解
- 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.
- 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4 的步骤 【示意图】
说明：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr [8] = {0 , 4, 7, 5, 2, 6, 1, 3} // 对应 arr 下标 表示第几行，即第几个皇后，arr [i] = val , val 表示第 i+1 个皇后，放在第 i+1 行的第 val+1 列
代码实现：
@SuppressWarnings("all") | |
public class Bahuanghou { | |
// 定义一个 max 表示共有多少个皇后 | |
int max = 8; | |
// 定义数组 array, 保存皇后放置位置的结果，比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3} | |
int[] array = new int[max]; | |
static int count = 0; | |
static int judgeCount = 0; | |
public static void main(String[] args) { | |
// 测试一把 ， 8 皇后是否正确 | |
Bahuanghou queue8 = new Bahuanghou(); | |
queue8.check(0); | |
System.out.printf("一共有%d解法", count); | |
System.out.printf("一共判断冲突的次数%d次", judgeCount); // 1.5w | |
} | |
// 编写一个方法，放置第 n 个皇后 | |
// 特别注意： check 是 每一次递归时，进入到 check 中都有 for (int i = 0; i < max; i++)，因此会有回溯 | |
private void check(int n) { | |
if(n == max) { //n = 8 , 其实 8 个皇后就既然放好 | |
print(); | |
return; | |
} | |
// 依次放入皇后，并判断是否冲突 | |
for(int i = 0; i < max; i++) { | |
// 先把当前这个皇后 n , 放到该行的第 1 列 | |
array[n] = i; | |
// 判断当放置第 n 个皇后到 i 列时，是否冲突 | |
if(judge(n)) { // 不冲突 | |
// 接着放 n+1 个皇后，即开始递归 | |
check(n+1); // | |
} | |
// 如果冲突，就继续执行 array [n] = i; 即将第 n 个皇后，放置在本行得 后移的一个位置 | |
} | |
} | |
/** | |
* 查看当我们放置第 n 个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突 | |
* @param n 表示第 n 个皇后 | |
* @return | |
*/ | |
private boolean judge(int n) { | |
judgeCount++; | |
for(int i = 0; i < n; i++) { | |
// 说明 | |
//1. array [i] == array [n] 表示判断 第 n 个皇后是否和前面的 n-1 个皇后在同一列 | |
//2. Math.abs (n-i) == Math.abs (array [n] - array [i]) 表示判断第 n 个皇后是否和第 i 皇后是否在同一斜线 | |
//n = 1 放置第 2 列 1 n = 1 array [1] = 1 | |
// Math.abs(1-0) == 1 Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1 | |
//3. 判断是否在同一行，没有必要，n 每次都在递增 | |
if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) { | |
return false; | |
} | |
} | |
return true; | |
} | |
// 写一个方法，可以将皇后摆放的位置输出 | |
private void print() { | |
count++; | |
for (int i = 0; i < array.length; i++) { | |
System.out.print(array[i] + " "); | |
} | |
System.out.println(); | |
} | |
} |
