引言
本文主要介绍了一些常用的数据结构，包括链表、栈、队列、递归、哈希表和有序表。
1.链表结构
单链表节点结构：
class Node { public int value; public Node next; public Node(int data) { value = data; } }
双向链表节点结构：
class DoubleNode { public int value; public DoubleNode last; public DoubleNode next; public DoubleNode(int data) { value = data; } }
简单练习：
1）单链表和双链表如何反转
2）把给定值都删除
实现如下：
// 反转单链表 public static Node reverseLinkedList(Node head) { Node pre = null; Node next = null; while (null != head) { next = head.next; head.next = pre; pre = head; head = next; } return pre; } // 反转双向链表 public static DoubleNode reverseDoubleList(DoubleNode head) { DoubleNode pre = null; DoubleNode next = null; while (null != head) { next = head.next; head.next = pre; head.last = next; pre = head; head = next; } return pre; } // 删除单链表元素 public static Node removeValue(Node head, int num) { // 跳过链表头部值为num的部分 while (head != null) { if (head.value != num) { break; } head = head.next; } // 头节点为第一个值不为num的节点 Node pre = head; Node cur = head; while (cur != null) { // pre始终保持其值不等于num if (num == cur.value) { pre.next = cur.next; } else { pre = cur; } cur = cur.next; } return head; } // 删除双向链表元素 public static DoubleNode removeValue(DoubleNode head, int num) { // 跳过头节点 while (head != null) { if (head.value != num) { break; } head = head.next; } if (head != null) { head.last = null; } DoubleNode cur = head, pre = head; while (cur != null) { if (cur.value == num) { pre.next = cur.next; cur.last = null; } else { pre = cur; } cur = cur.next; } return head; }
Java和C++在垃圾回收方面存在区别：
当一块内存空间所对应的变量或引用不存在时，就会自动释放这块内存，Java存在内存泄漏的原因是因为变量的生命周期不同，例如一个生命周期较短的方法中对一个生命周期更长的数据结构进行了操作，但是调用结束时并没有恢复，简单来说，内存空间找不到对应变量或引用就会被释放，否则就不会被释放；
C++ 内存泄漏是因为声明的变量忘记释放，必须手动调用函数释放。
2.栈和队列
栈：数据先进后出，犹如弹匣；
队列：数据先进先出，好似排队。
栈和队列的实现：
（1）基于双向链表
package structure02; /** * @author Corley * @date 2021/10/7 14:02 * @description LeetCodeAlgorithmZuo-structure02 */ public class LinkedListQueueStack { /* 自定义节点 */ static class Node<T> { public Node<T> last; public Node<T> next; public T value; public Node(T value) { this.value = value; } } /* 自定义双向链表 */ static class DoubleLinkedList<T> { public Node<T> head; public Node<T> tail; public void addFromHead(T value) { Node<T> cur = new Node<>(value); if (null == head) { head = cur; tail = cur; } else { cur.next = head; head.last = cur; head = cur; } } public void addFrombottom(T value) { Node<T> cur = new Node<>(value); if (null == head) { head = cur; tail = null; } else { cur.last = tail; tail.next = cur; tail = cur; } } public T popFromHead() { if (null == head) { return null; } T res = head.value; if (head == tail) { head = null; tail = null; } else { head = head.next; head.last = null; } return res; } public T popFromBottom() { if (null == head) { return null; } T res = tail.value; if (head == tail) { head = null; tail = null; } else { tail = tail.last; tail.next = null; } return res; } public boolean isEmpty() { return null == head; } } /* 自定义栈 */ static class Stack<T> { private final DoubleLinkedList<T> stack; public Stack() { stack = new DoubleLinkedList<>(); } public void push(T value) { stack.addFromHead(value); } public T pop() { return stack.popFromHead(); } public boolean isEmpty() { return stack.isEmpty(); } } /* 自定义队列 */ static class Queue<T> { private final DoubleLinkedList<T> queue; public Queue() { queue = new DoubleLinkedList<>(); } public void push(T value) { queue.addFromHead(value); } public T pop() { return queue.popFromBottom(); } public boolean isEmpty() { return queue.isEmpty(); } } }
（2）基于数组
使用数组时，需要考虑数组的大小问题，这里选择使用固定长度的数组来实现。
其中，数组实现较麻烦，如下：
实现如下：
package structure02; /** * @author Corley * @date 2021/10/7 14:50 * @description LeetCodeAlgorithmZuo-structure02 * 使用环形数组RingBuffer的思想实现队列 */ public class ArrayQueueStack { static class Queue { private final int[] arr; private int pushi; // 加元素的下标 private int pulli; // 取元素的下标 private int size; private final int limit; // 队列大小 public Queue(int limit) { arr = new int[limit]; pushi = 0; pulli = 0; size = 0; this.limit = limit; } public void push(int num) { if (size == limit) { throw new RuntimeException("队列已满，不能再添加元素！"); } size++; arr[pushi] = num; pushi = nextIndex(pushi); } public int pull() { if (isEmpty()) { throw new RuntimeException("队列已空，不能再取元素！"); } size--; int res = arr[pulli]; pulli = nextIndex(pulli); return res; } public boolean isEmpty() { return 0 == size; } private int nextIndex(int index) { return index < (limit - 1) ? (index + 1) : 0; } } class Stack { int[] arr; int size; int limit; public Stack(int limit) { arr = new int[limit]; this.limit = limit; size = 0; } public void push(int num) { if (size == limit) { throw new RuntimeException("栈已满，不能再添加元素！"); } arr[size++] = num; } public int pop() { if (0 == size) { throw new RuntimeException("栈已空，不能再取元素！"); } return arr[--size]; } } }
既然语言都提供了这些结构和API，为什么还需要手写代码：
1）算法问题无关语言；
2）语言提供的API是有限的，当有新的功能是API不提供的就需要改写；
3）任何软件工具的底层都是最基本的算法和数据结构，这是绕不过去的。
实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能
1)pop: push、getMin操作的时间复杂度都是O(1)；
2)设计的栈类型可以使用现成的栈结构。
实现思路1如下：
维护两个栈，一个栈保存数据，另一个栈保存到当前高度的最小值，如下：
实现如下：
static class MinStack1 { private final Stack<Integer> stackData; private final Stack<Integer> stackMin; public MinStack1() { this.stackData = new Stack<>(); this.stackMin = new Stack<>(); } public void push(int num) { if (this.stackMin.isEmpty()) { this.stackMin.push(num); } else if (num < this.stackMin.peek()) { this.stackMin.push(num); } else { this.stackMin.push(this.stackMin.peek()); } this.stackData.push(num); } public int pop() { if (this.stackData.isEmpty()) { throw new RuntimeException("Your stack is empty!"); } stackMin.pop(); return stackData.pop(); } public int getMin() { if (this.stackData.isEmpty()) { throw new RuntimeException("Your stack is empty!"); } return stackMin.peek(); } }
实现思路2如下：
维护两个栈，一个栈保存数据，一个栈保存到当前高度的最小值，但是只有当当前要入栈的数≤之前（栈下面）的最小值时才入最小栈，会节省一些空间，但是会增加时间，因为增加了逻辑判断，如下：
实现如下：
static class MinStack2 { private final Stack<Integer> stackData; private final Stack<Integer> stackMin; public MinStack2() { this.stackData = new Stack<>(); this.stackMin = new Stack<>(); } public void push(int num) { if (this.stackMin.isEmpty()) { this.stackMin.push(num); } else if (num <= this.stackMin.peek()) { this.stackMin.push(num); } this.stackData.push(num); } public int pop() { if (this.stackData.isEmpty()) { throw new RuntimeException("Your stack is empty!"); } int res = stackData.pop(); if (res == getMin()) { stackMin.pop(); } return res; } public int getMin() { if (this.stackData.isEmpty()) { throw new RuntimeException("Your stack is empty!"); } return stackMin.peek(); } }
栈和队列的常见面试题：
1)如何用栈结构实现队列结构；
2)如何用队列结构实现栈结构。
用队列实现栈：
用两个队列来实现，包括原始队列和辅助队列，如下：
两个队列角色互相切换。
实现如下：
static class TwoQueueStack<T> { private Queue<T> queue; private Queue<T> help; public TwoQueueStack() { queue = new LinkedList<>(); help = new LinkedList<>(); } public void push(T value) { queue.offer(value); } public T pop() { while (queue.size() > 1) { help.offer(queue.poll()); } T res = queue.poll(); Queue<T> tmp = queue; queue = help; help = tmp; return res; } public T peek() { while (queue.size() > 1) { help.offer(queue.poll()); } T res = queue.poll(); help.offer(res); Queue<T> tmp = queue; queue = help; help = tmp; return res; } public boolean isEmpty() { return queue.isEmpty(); } }
