java">/*** 底层是数组*/
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;}
}队列
java">/*** 自定义队列 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;}
}
二分查找树
java">/*** 二叉查找树【二叉搜索树】* 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;}@Overridepublic String toString() {return String.valueOf(data);}}
}双向链表
java">
/*** 双向链表* 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;}@Overridepublic 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;}@Overridepublic String toString() {return String.valueOf(data);}}
}
