队列、链表
本总结主要是以“尚硅谷Java算法教程”的学习教程为主，加上一些个人的理解
目录
- 队列、链表
-
- 队列
- 环形队列
- 链表
-
- 单链表
- 双向链表
- 单向环形链表（实现约瑟夫环）
队列
-
队列介绍
队列是个有序列表，可以用数组和链表表示
遵循先入先出原则
示意图如下：
个人数据结构与算法学习总结-队列、链表队列、链表 -
数组模拟队列
实现功能：出队列、显示队列、查看队列头元素
- 代码实现：
package datastructure.queue;
import java.util.Scanner;
public class ArrayQueueDemo {
public static void main(String[] args) {
//测试一把
//创建一个队列
ArrayQueue queue = new ArrayQueue(3);
char key = ' '; //接收用户输入
Scanner scanner = new Scanner(System.in);//
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): 查看队列头的数据");
key = scanner.next().charAt(0);//接收一个字符
switch (key) {
case 's':
queue.show();
break;
case 'a':
System.out.println("输出一个数");
int value = scanner.nextInt();
queue.add(value);
break;
case 'g': //取出数据
try {
int res = queue.get();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': //查看队列头的数据
try {
int res = queue.headQueue();
System.out.printf("队列头的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': //退出
scanner.close();
loop = false;
break;
default:
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;
front = -1;
rear = -1;
arr = new int[maxSize];
}
// 判断队列是否满
public boolean isFull() {
return rear == maxSize - 1;
}
// 判断队列是否为空
public boolean isEmpty() {
return front == rear;
}
//增加元素
public void add(int n) {
if (isFull()) {
System.out.println("队列已满，无法再加入");
return;
}
rear += 1;
arr[rear] = n;
}
//获取队列元素，出队列
public int get() {
if (isEmpty()) {
throw new RuntimeException("队列已空，无法再出列");
}
front += 1;
return arr[front];
}
//显示队列所有的元素，不出队列
public void show() {
if (isEmpty()) {
System.out.println("队列空的，没有数据~~");
return;
}
for(int i =front+1;i<=rear;i++){
System.out.printf("arr[%d]=%d\n", i, arr[i]);
}
}
// 显示队列的头数据， 注意不是取出数据
public int headQueue() {
// 判断
if (isEmpty()) {
throw new RuntimeException("队列空的，没有数据~~");
}
return arr[front + 1];
}
}
环形队列
充分利用数组，实现环形队列（取模）
代码实现：
package datastructure.queue;
import java.util.Scanner;
public class circleQueueDemo {
public static void main(String[] args) {
//测试一把
System.out.println("测试数组模拟环形队列的案例~~~");
// 创建一个环形队列
CircleArray queue = new CircleArray(4); //说明设置4, 其队列的有效数据最大是3
char key = ' '; // 接收用户输入
Scanner scanner = new Scanner(System.in);//
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): 查看队列头的数据");
key = scanner.next().charAt(0);// 接收一个字符
switch (key) {
case 's':
queue.show();
break;
case 'a':
System.out.println("输出一个数");
int value = scanner.nextInt();
queue.add(value);
break;
case 'g': // 取出数据
try {
int res = queue.get();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': // 查看队列头的数据
try {
int res = queue.head();
System.out.printf("队列头的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': // 退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
class CircleArray {
private int maxSize; // 表示数组的最大容量
private int front;
private int rear; // 队列尾
private int[] arr; // 该数据用于存放数据, 模拟队列
public CircleArray(int maxSize) {
this.maxSize = maxSize;
front = 0;
rear = 0;
arr = new int[maxSize];
}
// 判断队列是否满
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
// 判断队列是否为空
public boolean isEmpty() {
return front == rear;
}
// 添加数据到队列
public void add(int n) {
// 判断队列是否满
if (isFull()) {
System.out.println("队列满，不能加入数据~");
return;
}
arr[rear] = n;
rear = (rear + 1) % maxSize;
}
// 获取队列的数据, 出队列
public int get() {
// 判断队列是否空
if (isEmpty()) {
// 通过抛出异常
throw new RuntimeException("队列空，不能取数据");
}
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
// 显示队列的所有数据
public void show() {
// 遍历
if (isEmpty()) {
System.out.println("队列空的，没有数据~~");
return;
}
for (int i = front; i < front + (rear + maxSize - front) % maxSize; i++)//(rear+maxSize-front)%maxSize得到的是队列的长度
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
// 显示队列的头数据， 注意不是取出数据
public int head() {
// 判断
if (isEmpty()) {
throw new RuntimeException("队列空的，没有数据~~");
}
return arr[front];
}
}
链表
链表是以节点的方式来存储,是链式存储。
每个节点包含 data 域， next 域：指向下一个节点。
链表的各个节点不一定是连续存储。
链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。
单链表
结构如下
代码实现案例
package datastructure.linkedlist;
import java.util.ArrayList;
import java.util.Stack;
public class SingleLinkedListDemo {
public static void main(String[] args) {
//进行测试
//先创建节点
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
//创建要给链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
//加入
singleLinkedList.add(hero1);
singleLinkedList.add(hero2);
singleLinkedList.add(hero3);
singleLinkedList.add(hero4);
System.out.println("原来链表的情况~~");
singleLinkedList.list();
//反转
// System.out.println("反转后");
// reversetList2(singleLinkedList.getHead());
// singleLinkedList.list();
//查看倒数元素
findLastIndexNode(singleLinkedList.getHead(), 2);
}
//将单链表反转
public static void reversetList(HeroNode head) {
//如果当前链表为空，或者只有一个节点，无需反转，直接返回
if (head.next == null || head.next.next == null) {
return;
}
HeroNode temp = head.next;
HeroNode newHead = new HeroNode(0, "", "");
HeroNode next = null;
while (temp != null) {
next = temp.next;
temp.next = newHead.next;
newHead.next = temp;
temp = next;
}
head.next = newHead.next;
}
//反转方法2
//可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
public static void reversetList2(HeroNode head) {
if (head.next == null) {
return;//空链表，不能打印
}
Stack<HeroNode> stack = new Stack<>();
HeroNode temp = head.next;
while (temp != null) {
stack.push(temp);
temp = temp.next;
}
while (stack.size() > 0) {
System.out.println(stack.pop());
}
}
//查找单链表中的倒数第k个结点 【新浪面试题】
//思路
//使用快慢指针
public static void findLastIndexNode(HeroNode head, int k) {
//判断如果链表为空，返回null
if (head.next == null) {
return;//没有找到
}
HeroNode fast = head;
HeroNode slow = head;
int index = 0;
while (fast.next != null) {
index += 1;
fast = fast.next;
if (index >= k) {
slow = slow.next;
}
}
if (index<k) {
System.out.println("链表长度小于k，查询不到");
} else {
System.out.println("倒数" + k + "元素为" + slow);
}
}
}
//定义SingleLinkedList 管理我们的英雄
class SingleLinkedList {
//先初始化一个头节点, 头节点不要动, 不存放具体的数据
private HeroNode head = new HeroNode(0, "", "");
//返回头节点
public HeroNode getHead() {
return head;
}
//添加节点到单向链表
//思路，当不考虑编号顺序时
//1. 找到当前链表的最后节点
//2. 将最后这个节点的next 指向 新的节点
public void add(HeroNode heroNode) {
//因为head节点不能动，因此我们需要一个辅助遍历 temp
HeroNode temp = head;
//遍历链表，找到最后
while (temp.next != null) {
temp = temp.next;
}
temp.next = heroNode;
}
//第二种方式在添加英雄时，根据排名将英雄插入到指定位置
//(如果有这个排名，则添加失败，并给出提示)
public void addByOrder(HeroNode heroNode) {
//因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
//因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
HeroNode temp = head;
boolean flag = false; // flag标志添加的编号是否存在，默认为false
while (temp.next != null) {
if (temp.next.no > heroNode.no) {
break; //位置找到，就在temp的后面插入
} else if (temp.next.no == heroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
//不能添加，说明编号存在
System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
} else {
heroNode.next = temp.next;
temp.next = heroNode;
temp.next = heroNode;
}
}
//修改节点的信息, 根据no编号来修改，即no编号不能改.
//说明
//1. 根据 newHeroNode 的 no 来修改即可
public void update(HeroNode newHeroNode) {
//判断是否空
if (head.next == null) {
System.out.println("链表为空~");
return;
}
//找到需要修改的节点, 根据no编号
//定义一个辅助变量
HeroNode temp = head;
boolean flag = false; //表示是否找到该节点
while (temp != null) {
if (temp.no == newHeroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {
//没有找到
System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
}
}
//删除节点
//思路
//1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
//2. 说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较
public void del(int no) {
HeroNode temp = head;
boolean flag = false; // 标志是否找到待删除节点的
while (temp.next != null) {
if (temp.next.no == no) {
//找到的待删除节点的前一个节点temp
flag = true;
break;
}
temp = temp.next; //temp后移，遍历
}
//判断flag
if (flag) { //找到
//可以删除
temp.next = temp.next.next;
} else {
System.out.printf("要删除的 %d 节点不存在\n", no);
}
}
//显示链表[遍历]
public void list() {
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//因为头节点，不能动，因此我们需要一个辅助变量来遍历
HeroNode temp = head.next;
while (temp != null) {
//输出节点的信息
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 + "]";
}
}
双向链表
单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除节点，总是找到temp,temp是待删除节点的前一个节点。
代码实现：
package datastructure.linkedlist;
public class DoubleLinkedListDemo {
}
class DoubleLinkedList {
private HeroNode2 head = new HeroNode2(0, "", "");
public HeroNode2 getHead() {
return head;
}
//添加节点到单向链表
public void add(HeroNode2 heroNode) {
//因为head节点不能动，因此我们需要一个辅助遍历 temp
HeroNode2 temp = head;
//遍历链表，找到最后
while (temp.next!= null) {
temp = temp.next;
}
temp.next = heroNode;
heroNode.pre =temp;
}
// 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样
// 只是 节点类型改成 HeroNode2
public void update(HeroNode2 newHeroNode) {
//判断是否空
if (head.next == null) {
System.out.println("链表为空~");
return;
}
//找到需要修改的节点, 根据no编号
//定义一个辅助变量
HeroNode2 temp = head;
boolean flag = false; //表示是否找到该节点
while (temp != null) {
if (temp.no == newHeroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {
//没有找到
System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
}
}
//删除
public void del(int no){
HeroNode2 temp = head;
boolean flag = false; // 标志是否找到待删除节点的
while (temp.next != null) {
if (temp.next.no == no) {
//找到的待删除节点的前一个节点temp
flag = true;
break;
}
temp = temp.next; //temp后移，遍历
}
//判断flag
if (flag) { //找到
//可以删除
temp.pre.next = temp.next;
// 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
if (temp.next != null) {
temp.next.pre = temp.pre;
}
} else {
System.out.printf("要删除的 %d 节点不存在\n", no);
}
}
public void list()
{
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//因为头节点，不能动，因此我们需要一个辅助变量来遍历
HeroNode2 temp = head.next;
while (temp != null) {
//输出节点的信息
System.out.println(temp);
//将temp后移， 一定小心
temp = temp.next;
}
}
}
//定义HeroNode ， 每个HeroNode 对象就是一个节点
class HeroNode2 {
public int no;
public String name;
public String nickname;
public HeroNode2 next; //指向下一个节点
public HeroNode2 pre;//指向上一个节点
//构造器
public HeroNode2(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 + "]";
}
}
单向环形链表（实现约瑟夫环）
结构如图示
Josephu（约瑟夫环问题）
Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
代码实现：
package datastructure.linkedlist;
public class Josephu {
public static void main(String[] args) {
// 测试一把看看构建环形链表
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5);// 加入5个小孩节点
circleSingleLinkedList.show();
//测试一把小孩出圈是否正确
circleSingleLinkedList.countBoy(1, 2, 5); // 2->4->1->5->3
}
}
class CircleSingleLinkedList {
// 创建一个first节点,当前没有编号
private Boy first = null;
// 添加小孩节点，构建成一个环形的链表
public void addBoy(int nums) {
// nums 做一个数据校验
if (nums < 1) {
System.out.println("nums的值不符合规则，请重新输入");
return;
}
Boy temp = null;
for (int i = 1; i <= nums; i++) {
Boy boy = new Boy(i);
if (i == 1) {
first = boy;
first.next=first; // 构成环
temp = first; // 让curBoy指向第一个小孩
} else {
temp.next=boy;
boy.next=first;
temp = boy;
}
}
}
//遍历
public void show(){
// 判断链表是否为空
if (first == null) {
System.out.println("没有任何小孩~~");
return;
}
Boy temp =first;
while(temp.next!=first){
System.out.print(temp.no+"\t");
temp=temp.next;
}
System.out.println(temp.no+"\t");
}
// 根据用户的输入，计算出小孩出圈的顺序
/**
*
* @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 pre =first;
while(pre.next!=first)
{
pre=pre.next;//初始化，指向first的前一个元素
}
//先移动到第K个元素
for(int j = 0; j < startNo - 1; j++) {
first = first.next;
pre=pre.next;
}
//当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次, 然后出圈
//这里是一个循环操作，知道圈中只有一个节点
while(pre!=first){
for(int i =1;i<countNum;i++){
first = first.next;
pre=pre.next;
}
System.out.printf("小孩%d出圈\n", first.no);
first=first.next;
pre.next=first;
}
System.out.printf("小孩%d出圈\n", first.no);
}
}
class Boy{
public int no;// 编号
public Boy next; // 指向下一个节点,默认null
public Boy(int no){
this.no=no;
}
}