Java数据结构与算法中级篇之栈、队列、链表
源码下载地址：https://download.csdn.net/download/geduo_83/10913510
数据是基础，算法是灵魂
初级篇：Java数据结构与算法初级篇之数组、集合和散列表
中级篇：Java数据结构与算法中级篇之栈、队列、链表
高级篇：Java数据结构与算法高级篇之树
1. 概述
2. 栈
2.1 什么是栈
2.2 栈的存储结构
2.3 栈的实现
2.4 栈的特点
2.5 适用场景
3. 队列
3.1 什么是队列
3.2 队列的存储结构
3.3 队列的实现
3.4 队列的特点
3.5 适用场景
4. 链表
4.1 什么是链表
4.2 链表的数据结构
4.3 链表的特点
4.4 使用场景
4.5 相关算法
在上一篇文章我们讲了数组、集合、散列表，接下来我们来学习数据结构中非常有意思的几个数据结构--栈、队列和链表，这三个结构都有一个共同的特点都是顺序存储数据的，但是他们存储数据的方式不同，各有各的特点，如果我们把上一篇文章学习的数组作为数据结构中幼儿园级别的内容，那么今天这篇文章讲的这三个数据结构相当于小学级别的内容了。这三种数据结构也是我们面试的时候经常被问到的知识点。
栈是一种只能在一端进行插入和删除的线性数据结构。
package D栈队列.A001用数组实现一个栈;
import java.util.Arrays;
/**
* Description: <><br>
* Author: 门心叼龙<br>
* Date: 2018/11/19<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MyStack {
private int[] arr;
private int size = 0;
private int initsize = 5;
public MyStack() {
arr = new int[initsize];
}
public void push(int value) {
if (size == arr.length) {
arr = Arrays.copyOf(arr, size * 2);
}
arr[size++] = value;
}
public int pop() {
if (size == 0) {
throw new IndexOutOfBoundsException("栈里面数组为空了");
}
return arr[--size];
}
public int size() {
return size;
}
}栈的特点是显而易见的，只能在一端进行操作，遵循先进后出或者后进先出的原则。
2.5.1 逆序输出
由于栈有先进后出的特点，所以逆序输出是其中一个非常简单的应用。首先把要存储的元素按顺序入栈，然后把所有的元素都出栈，轻松实现逆序输出。
2.5.2 进制转换
我们可以通过求余法，将十进制转化为其它进制，比如要转为二进制，把十进制数除以2，记录余数0入栈，然后继续将商除以2，记录余数1入栈，一直商等于0为止，最后余数倒着写过来就行了。
2.5.3 方法栈
函数调用的过程就是不断的压栈的过程，当函数返回结果的时候就是不断的弹栈的过程。
2.5.4 Activity栈
做过Android开发的同学都知道Activity的打开就是一个不断压栈的过程，当我们点击返回键的时候就是一个不断弹栈的过程。
队列是一种只能在一端进行插入和在另一端删除的线性数据结构。
package D栈队列.A002用数组实现一个队列;
/**
* Description: <><br>
* Author: 门心叼龙<br>
* Date: 2018/11/19<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MyQueue {
private int head = 0;
private int tail = 0;
private final int[] arr;
public MyQueue() {
arr = new int[5];
}
// 塞数据
public boolean put(int value) {
if (head == (tail + 1) % arr.length) {
System.out.println("队列已经满了...");
return false;
}
arr[tail] = value;
tail = (tail + 1) % arr.length;
return true;
}
public int poll() {
if (head == tail) {
System.out.println("队列已经空了");
return -1;
}
int item = arr[head];
arr[head] = 0;
head = (head + 1) % arr.length;
return item;
}
}先进先出或者后进后出。
3.5.1 排队
只要和排队有关的场景，都可以使用队列的数据结构来解决问题。比如春节抢购火车票、双十一的抢购活动。
3.5.2 Handler消息队列
做过Android开发的都知道，Android系统有一个非常重要的消息队列机制Handler，其数据结构就是一个典型的队列。
链表是由一系列的节点组成的，当前元素都持有对下家元素的引用，栈和队列都是申请一段连续的内存空间，然后进行顺序存储数据，而链表是一种物理上非连续的存储结构，数据元素之间的顺序是通过每个元素的指针关联的。
a.链表在对队头或者队尾进行插入或删除的操作效率都非常高，时间复杂度都是O(1)
a.物理空间不连续，空间开销大。
b.查找元素需要顺序查找，元素越靠后效率越低。
链表的劣势就是查找中间元素时需要遍历，一般而言，链表也经常配合其他的数据结构一起使用，例如散列表、栈、队列等。
4.5.1 实现一个链表
ListNote.java:
package E链表.A001实现一个链表;
/**
* Description: <><br>
* Author: 门心叼龙<br>
* Date: 2018/11/19<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class ListNode {
public int data;
public ListNode next;
public ListNode(int val) {
this.data = val;
}
public ListNode() {
this.data = data;
}
public void setNext(ListNode next) {
this.next = next;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public ListNode getNext() {
return next;
}
}MyListLink.java:
package E链表.A001实现一个链表;
/**
* Description: <用数组实现一个链表><br>
* Author: 门心叼龙<br>
* Date: 2018/11/20<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MyListLink {
private ListNode first;
private ListNode last;
private int size;
public void addLast(int value) {
ListNode listNote = new ListNode();
listNote.setData(value);
if (first == null) {
first = listNote;
} else {
last.setNext(listNote);
}
last = listNote;
size++;
}
public ListNode getListLink() {
return first;
}
}MainAlgorithm.java
package E链表.A001实现一个链表;
/**
* Description: <用数组实现一个链表><br>
* Author: 门心叼龙<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args) {
MyListLink listLink = new MyListLink();
listLink.addLast(1);
listLink.addLast(3);
listLink.addLast(2);
listLink.addLast(11);
ListNode headnode = listLink.getListLink();
while (headnode != null) {
System.out.println(headnode.data);
headnode = headnode.next;
}
}
}4.5.2 检查链表有没有环
package E链表.A002检查链表有没有环;
import java.util.HashSet;
import E链表.A001实现一个链表.ListNode;
/**
* Description: <检查链表有没有环><br>
* Author: 门心叼龙<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAgorithm {
public static void main(String[] args) {
ListNode listNote = new ListNode(0);
ListNode listNote1 = new ListNode(1);
ListNode listNote2 = new ListNode(2);
ListNode listNote3 = new ListNode(3);
listNote.setNext(listNote1);
listNote1.setNext(listNote2);
listNote2.setNext(listNote3);
listNote3.setNext(listNote1);
boolean loop = checkLoop(listNote);
System.out.println(loop);
}
// 计数法
public static boolean checkLoop1(ListNode listNote) {
HashSet<ListNode> hashSet = new HashSet<>();
ListNode temp = listNote;
while (temp != null) {
if (hashSet.contains(temp)) {
return true;
} else {
hashSet.add(temp);
}
temp = temp.next;
}
return false;
}
// 差速发
private static boolean checkLoop(ListNode listNote) {
ListNode slow = listNote;
ListNode fast = listNote;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
// 只要有环必然会相遇
if (fast == slow) {
return true;
}
}
return false;
}
}4.5.3 查找有环链表的入口节点
package E链表.A003查找有环链表的入口节点;
import E链表.A001实现一个链表.ListNode;
/**
* Description: <查找有环链表的入口节点><br>
* Author: 门心叼龙<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAgorithm {
public static void main(String[] args) {
ListNode listNote = new ListNode(0);
ListNode listNote1 = new ListNode(1);
ListNode listNote2 = new ListNode(2);
ListNode listNote3 = new ListNode(3);
listNote.setNext(listNote1);
listNote1.setNext(listNote2);
listNote2.setNext(listNote3);
listNote3.setNext(listNote1);
ListNode firstNode = getFirstNode(listNote);
System.out.println(firstNode.data);
}
// 查找有环链表的入口节点
private static ListNode getFirstNode(ListNode listNote) {
// 如果链表有环，请找到其入口节点
ListNode slow = listNote;
ListNode fast = listNote;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (fast == null || fast.next == null) {
return null;
}
// 重置slow指针
slow = listNote;
// 如果没有相遇则继续往下走
// 定理:从头结点到入口节点的距离等于从相遇节点到入口节点的距离*****
// 因为：2(m + x) = m + x + y + x;
// 所以：2m+2x = m + 2x + y
// 得出：m = y;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}4.5.6 翻转一个链表
package E链表.A004翻转一个链表;
import java.util.ArrayList;
import java.util.List;
import E链表.A001实现一个链表.ListNode;
import E链表.A001实现一个链表.MyListLink;
/**
* Description: <翻转一个链表><br>
* Author: 门心叼龙<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args) {
MyListLink link = new MyListLink();
link.addLast(0);
link.addLast(1);
link.addLast(3);
link.addLast(6);
ListNode listNote = reverseListNode(link.getListLink());
while (listNote != null) {
System.out.println(listNote.getData());
listNote = listNote.next;
}
}
// 指针法
private static ListNode reverseListNode2(ListNode listNote) {
// 声明的头指针
ListNode head = listNote;
// 申明一个尾指针
ListNode tail = listNote;
// 声明一个next指针
ListNode next = listNote.next;
// 计算链表的长度
int size = 0;
ListNode temp = listNote;
while (temp != null) {
size++;
temp = temp.next;
}
while (size > 1) {
// 缓存一个next
ListNode nextNext = next.next;
// 更改next的next指针
next.next = head;// 反向了
// 移动head指针的指向
head = next;
// 移动next指针的指向
next = nextNext;
size--;
}
// 此时链表有环，干掉环
tail.next = null;
return head;
}
// 数组法
private static ListNode reverseListNode(ListNode listNote) {
// 翻转一个链表
ListNode tempNode = listNote;
// 把链表的值都放入List集合里面
// 通过翻转数组来翻转集合
List<ListNode> list = new ArrayList<>();
while (tempNode != null) {
list.add(tempNode);
tempNode = tempNode.next;
}
ListNode headNode = null;
for (int i = list.size() - 1; i >= 0; i--) {
if (headNode == null) {
headNode = new ListNode();
headNode = list.get(i);
headNode.next = list.get(i - 1);
} else {
if (i == 0) {
list.get(i).next = null;
} else {
list.get(i).next = list.get(i - 1);
}
}
}
return headNode;
}
}4.5.7 删除链表倒数第N个节点
package E链表.A005删除链表中的倒数第N个节点;
import E链表.A001实现一个链表.ListNode;
import E链表.A001实现一个链表.MyListLink;
/**
* Description: <删除链表中的倒数第N个元素><br>
* Author: 门心叼龙<br>
* Date: 2018/11/23<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args){
MyListLink myListLink = new MyListLink();
myListLink.addLast(0);
myListLink.addLast(1);
myListLink.addLast(2);
myListLink.addLast(3);
myListLink.addLast(4);
//删除倒数第2个元素
ListNode head = removeReIndex(myListLink.getListLink(), 3);
while(head != null){
System.out.println(head.data);
head = head.next;
}
}
private static ListNode removeReIndex(ListNode listNode, int n) {
ListNode head = listNode;
ListNode pb = listNode;
ListNode pa = listNode;
int i = 0;
while(i < n ){
pa = pa.next;
i++;
}
while(pa.next != null){
pa = pa.next;
pb = pb.next;
}
pb.next = pb.next.next;
return head;
}
}4.5.8 合并两个有序链表
package E链表.A006合并两个排好序的链表;
import E链表.A001实现一个链表.ListNode;
import E链表.A001实现一个链表.MyListLink;
/**
* Description: <合并两个排好序的链表><br>
* Author: 门心叼龙<br>
* Date: 2018/11/22<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args) {
MyListLink myListLink = new MyListLink();
myListLink.addLast(0);
myListLink.addLast(2);
myListLink.addLast(4);
MyListLink myListLink1 = new MyListLink();
myListLink1.addLast(1);
myListLink1.addLast(3);
myListLink1.addLast(40);
myListLink1.addLast(50);
ListNode listNode = mergerListNode(myListLink.getListLink(), myListLink1.getListLink());
while (listNode != null) {
System.out.println(listNode.data);
listNode = listNode.next;
}
}
public static ListNode mergerListNode(ListNode listNode1, ListNode listNode2) {
ListNode head = new ListNode(0);
ListNode tail = head;
while (listNode1 != null && listNode2 != null) {
if (listNode1.data < listNode2.data) {
tail.next = listNode1;
listNode1 = listNode1.next;
} else {
tail.next = listNode2;
listNode2 = listNode2.next;
}
tail = tail.next;
}
tail.next = listNode1 != null ? listNode1 : listNode2;
return head.next;
}
}源码下载地址：https://download.csdn.net/download/geduo_83/10913510
问题反馈
在使用中有任何问题，欢迎反馈给我，可以用以下联系方式跟我交流
- QQ：303704981
- email：[email protected]
- weibo：@geduo_83
关于作者
var geduo_83 = {
nickName : "门心叼龙",
site : "http://www.weibo.com/geduo83"
}