/**
* 底层是数组
*/
public class MyStack {
private long [] arr; // 底层是数组
private int top = -1; // 核心【栈顶的索引（指针）】
public MyStack() {
super();
arr = new long[10];
}
public MyStack(int capacity) {
super();
arr = new long[capacity]; // 自定义长度
}
/**
* 压栈
* @param value
*/
public void push(long value) {
if(isFull())
throw new IllegalArgumentException("Stack is full");
arr[++top] = value;
}
/**
* 弹栈【每次都是从栈顶取出元素】
* @return
*/
public long pop() {
if(isEmpty()) // 当栈空的时候，就不能弹栈了
throw new IllegalArgumentException("Stack is empty");
return arr[top--];
}
/**
* 查看栈顶的元素
* @return
*/
public long peek() {
if(isEmpty()) // 当栈空的时候，就不能弹栈了
throw new IllegalArgumentException("Stack is empty");
return arr[top];
}
/**
* 判断栈是否是空的
* @return
*/
public boolean isEmpty() {
return top == -1;
}
/**
* 判断是否满栈了
* @return
*/
public boolean isFull() {
return top == arr.length-1;
}
}
队列
/**
* 自定义队列 FIFO : 先进先出 【底层是数组】
*/
public class MyQueue {
private long [] arr; // 底层是数组
private int front = 0; // 队头索引
private int rear = 0; // 队尾索引
private int elements = 0; // 队列中实际的元素个数
public MyQueue() {
super();
arr = new long[10];
}
public MyQueue(int capacity) {
super();
arr = new long[capacity]; // 自定义长度
}
/**
* 入队列【从队尾添加元素】
* @param value
*/
public void enqueue(long value) {
if(isFull())
throw new QueueException("Queue is full");
arr[rear++] = value;
elements++;
}
/**
* 出队列 【从队头取出元素】
* @return
*/
public long dequeue() {
if(isEmpty())
throw new QueueException("Queue is empty");
elements--;
return arr[front++];
}
/**
* 查看队头的元素
* @return
*/
public long top() {
if(isEmpty())
throw new QueueException("Queue is empty");
return arr[front];
}
/**
* 判断队列是否是空的
* @return
*/
public boolean isEmpty() {
return elements == 0;
}
/**
* 队列满了
* @return
*/
public boolean isFull() {
return elements == arr.length;
}
/**
* 队列中的元素个数
* @return
*/
public int size() {
return elements;
}
}
二分查找树
/**
* 二叉查找树【二叉搜索树】
* 1. 底层 Node
* 2. 树根root
*/
public class BinarySearchTree {
private Node root; // 树根
public BinarySearchTree() {
super();
}
/**
* 二叉树的添加【口诀 ： 左小右大】
* @param value
* @return true 添加成功 false 添加失败了
*/
public boolean add(long value) {
Node node = new Node(value); // 添加的新节点
if(root == null) { // 空树
root = node; // 把新添加的第一个元素作为树根
return true;
}
Node parent = null; // 当前节点的父节点
Node current = root; // 每次都要从树根去查询
for(;;) {
parent = current; // 确定当前节点的父节点
if(value < current.data) { // 左小：值小的放节点的左边
current = current.leftChild;
if(current == null) {
parent.leftChild = node;
return true;
}
}else if(value > current.data) { // 右大：值大的放节点的右边
current = current.rightChild;
if(current == null) {
parent.rightChild = node;
return true;
}
}else { // 节点值相等了：去重
return false; // TreeSet的去重原理【重复的节点不会添加】
}
}
}
/**
* 根据值来找二叉树中的节点(递归思想)
* 时间复杂度O(log2n) ~ O(n) , 近似于二分查找
* @param value
* @return
*/
public Long find(long value) {
if(root == null) // 空树
return null;
Node current = root; // 每次查询都要从树根开始
while(value != current.data) { // 没要找到此节点时，则继续遍历左/右子节点来查找
if(value < current.data) { // 左小
current = current.leftChild;
}else { // 右大
current = current.rightChild;
}
if(current == null) { // 找到树的最后一个节点都还没有找到该数值的节点
return null;
}
}
return current.data;
}
/**
* 获取树根
* @return
*/
public Node getRoot() {
return root;
}
/**
* 递归 ： 从任意节点进行前序遍历【根左右】
* @param localNode
*/
public void preOrder(Node localNode) {
if(localNode != null) {
//1. 前序遍历根节点
System.out.println(localNode);
//2. 前序遍历左子节点
preOrder(localNode.leftChild);
//3. 前序遍历右子节点
preOrder(localNode.rightChild);
}
}
/**
* 递归 ： 从任意节点进行中序遍历 【左根右】
* @param localNode
*/
public void inOrder(Node localNode) {
if(localNode != null) {
//1. 中序遍历左子节点
inOrder(localNode.leftChild) ;
//2. 中序遍历根节点
System.out.println(localNode);
//3. 中序遍历右子节点
inOrder(localNode.rightChild) ;
}
}
/**
* 递归 ： 从任意节点进行后序遍历 【左右根】
* @param localNode
*/
public void postOrder(Node localNode) {
if(localNode != null) {
//1. 后序遍历左子节点
postOrder(localNode.leftChild);
//2. 后序遍历右子节点
postOrder(localNode.rightChild);
//3. 后序遍历根节点
System.out.println(localNode);
}
}
/**
* 树结构的底层节点类
*/
@SuppressWarnings("unused")
class Node{
private long data; // 数据域
private Node leftChild; // 当前节点的左子节点
private Node rightChild; // 当前节点的右子节点
public Node(long data) {
super();
this.data = data;
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
@Override
public String toString() {
return String.valueOf(data);
}
}
}双向链表
/**
* 双向链表
* 1. 底层是Node（data, next ,previous）
* 2. first头节点 last尾结点
*/
public class DoubleLinkedList {
private Node first; // 头节点
private Node last; // 尾节点
private int elements; // 链表中真实的节点个数
public DoubleLinkedList() {
super();
}
/**
* 判断是否是空链表
*
* @return
*/
public boolean isEmpty() {
return first == null;
}
/**
* 从链表头部添加元素
* @param value
*/
public void addFirst(Object value) {
Node node = new Node(value);
if (first == null) { // 空链表
last = node; // 指定尾节点
}else { // 不是空链表时
first.previous = node;
}
node.next = first;
first = node;
elements++;
}
/**
* 从链表尾部添加节点
*
* @param value
*/
public void addLast(Object value) {
Node node = new Node(value);
if (first == null) { // 空链表
first = node; // 指定尾节点
} else {
last.next = node; // 图步骤1： 向链表尾部追加节点
node.previous = last; // 图步骤2 ：把曾经的last变为倒数第二个节点
}
last = node; // 图步骤3 ： 新添加的节点就是尾部节点
elements++;
}
/**
* 从链表尾部添加节点
* @param value
*/
public void add(Object value) {
addLast(value);
}
/**
* 删除链表的头节点
* @return
*/
public Object removeFirst() {
if(first == null) // 空链表不用删除
return null;
Node removeNode = first; // 临时保存被删除的头节点
if(removeNode.next == null) { // 删除到链表只剩余最后一个节点时
last = null;
}else {
removeNode.next.previous = null; // 头节点是不会存在previous的
}
first= first.next;
elements--;
return removeNode.data;
}
/**
* 删除链表的尾节点
* @return
*/
public Object removeLast() {
if(first == null) // 空链表不用删除
return null;
Node removeNode = last; // 临时保存被删除的头节点
if(removeNode.next == null) { // 链表只剩余最后一个元素了
first = null;
}else { // 链表中还有节点
removeNode.previous.next = null; // 尾节点时没有下一个节点的
}
last = last.previous;
elements--;
return removeNode.data;
}
@Override
public String toString() {
Node current = first; // 双向链表从头节点开始一个个遍历元素
StringBuilder builder = new StringBuilder();
builder.append("[");
while (current != null) {
builder.append(current);
current = current.next;
if (current != null) {
builder.append(", ");
}
}
builder.append("]");
return builder.toString();
}
/**
* 从链表尾部向前遍历（倒序）
* @return
*/
public String reverse() {
Node current = last; // 双向链表从尾节点开始一个个遍历元素
StringBuilder builder = new StringBuilder();
builder.append("[");
while (current != null) {
builder.append(current);
current = current.previous;
if (current != null) {
builder.append(", ");
}
}
builder.append("]");
return builder.toString();
}
/**
* 查找节点 (双向链表可以从头节点也可以从尾节点查找) 1~1000
* @param value
* @return
*/
public Object find(Object value) {
// 双端链表要从头节点first开始查找元素
Node current = first;
while (current != null) {
if (current.data == value) {
return current.data;
}
current = current.next; // 遍历
}
return null;
}
/**
* 根据数据值来删除对应的链表节点
* @param obj
* @return
*/
public Object remove(Object value) {
if(first == null) // 空链表不能删除节点
return null;
//1.遍历查找需要删除的节点
Node current = first; // 当前遍历的节点
while(current.data != value) { // 判断节点的值是否是要删除的值
if(current.next == null) // 已经找到链表的最后一个节点了
return null;
current = current.next; // 遍历思想
}
//2.删除查找到的节点
if(current == first) { // 删除的就是头节点元素
if(current.next == null)// 处理 ： 链表中就一个元素，且删除的就是这个元素时
last = null;
first = current.next;
}else { // 删除的中间节点或尾结点
current.previous.next = current.next; // current给删除了（current就成为垃圾，GC）
}
elements--;
return current.data;
}
/**
* 链表中真实的节点个数
* @return
*/
public int size() {
return elements;
}
private class Node { // 底层Node节点类
private Object data; // 数据域
private Node next; // 指针域（保存的是下一个节点的引用）
private Node previous; // 指针域（保存的是上一个节点的引用）
public Node(Object data) {
super();
this.data = data;
}
@Override
public String toString() {
return String.valueOf(data);
}
}
}
![BUUCTF [极客大挑战 2019]EasySQL 1](https://img-blog.csdnimg.cn/direct/d5f64a03a0f44d1e96c8de9d38765f2e.png)
![[微信小程序] 入门笔记2-自定义一个显示组件](https://img-blog.csdnimg.cn/direct/4f11639794bb454ba7f8c5bb3144d775.png)
