- 数组
- 链表
- 栈
- 队列
数组学习数据结构与算法之美记录，之前已经看数据结构与算法视频过了三遍，每次看完就结束，这次一定学习+动手，后续每天或每周抽出时间做题保持学习状态
一段连续存储的空间，可以通过下标定位到对应位置的线性结构
链表由多个节点组成，每个节点有一或两个指针指向其它节点，构成的线性结构。
种类：
- 单向链表
package com.zsl.datastructalgorithm.date20220625; import lombok.Data; public class SingleLinkedList{ // 头 private Node head; // 尾 private Node tail; // 大小 private int size = 0; public void add(T obj) { Node node = new Node<>(); node.obj = obj; if (head == null) { head = node; tail = node; size = 1; } else { tail.next = node; tail = node; ++size; } } public T get(int index) { if (size == 0) { return null; } T obj = null; if (index < size) { Node currNode = head; for (int i = 0; i < index; i++) { currNode = currNode.next; } obj = currNode.obj; } return obj; } public boolean remove(int index) { // 边界处理(空链表、索引无效) if (size == 0 || index >= size || index < 0) { return false; } // 特殊处理 if (index == 0) { if (size == 1) { head = null; tail = null; return true; } else { head = head.next; } } // 查找索引元素 Node prevNode = null; Node currNode = head; for (int i = 0; i < index; i++) { prevNode = currNode; currNode = currNode.next; } // 移除节点 assert prevNode != null; prevNode.next = currNode.next; // 末尾处理 if (index == --size) { tail = prevNode; } return true; } public void reverse() { if (size < 2) { return; } tail = head; Node currNode = head; Node nextNode = currNode.next; head.next = null; for (int i = 0; i < size - 1; i++) { currNode = nextNode; nextNode = nextNode.next; currNode.next = head; head = currNode; } } @Override public String toString() { return "SingleList{" + "head=" + head + ", tail=" + tail + ", size=" + size + '}'; } @Data public static class Node { private T obj; private Node next; } public static void main(String[] args) { SingleLinkedList list = new SingleLinkedList<>(); for (int i = 0; i < 10; i++) { list.add(i); } System.out.println(list); list.remove(4); System.out.println(list); list.reverse(); System.out.println(list); } }
- 双向链表
- 环链表（单或双向）
正确写出链表代码六个技巧：
- 理解指针或引用的含义
- 警惕指针丢失和内存泄漏
- 利用哨兵简化实现难度
- 重点留意边界条件处理
- 举例画图，辅助思考
- 多写多练
LIFO后进先出，一种操作受限的线性表数据结构
种类
- 顺序栈：用数组实现
package com.zsl.datastructalgorithm.date20220626;
public class Stack {
// 数组元素
private Integer[] elements;
// 容量
private final int capacity;
// 当前栈存储元素个数
private int size;
public Stack(int capacity) {
this.elements = new Integer[capacity];
this.capacity = capacity;
this.size = 0;
}
public boolean push(Integer element) {
// 边界处理
if (size == capacity) {
return false;
}
elements[size++] = element;
return true;
}
public Integer pop() {
// 边界处理
if (size == 0) {
return null;
}
return elements[--size];
}
public Integer peek() {
// 边界处理
if (size == 0) {
return null;
}
return elements[size - 1];
}
public static void main(String[] args) {
Stack stack = new Stack(10);
for (int i = 0; i < 16; i++) {
System.out.println(String.format("%02d:push number: %d, 结果:%s", i, i, stack.push(i)));
}
for (int i = 0; i < 16; i++) {
Integer pop = stack.pop();
System.out.println(String.format("%02d:pop 结果:%d", i, pop));
}
}
}
- 链式栈：用链表实现
FIFO先进先出，也是一种操作受限的线性表数据结构
种类 --> 存储形式
- 顺序队列（单、双、环）
package com.zsl.datastructalgorithm.date20220626;
public class ArrayQueue {
// 元素数组
private Integer[] elements;
// 头
private int head;
// 尾
private int tail;
// 容量
private final int capacity;
public ArrayQueue(int capacity) {
this.elements = new Integer[capacity];
this.head = 0;
this.tail = 0;
this.capacity = capacity;
}
public boolean enqueue(Integer element) {
// 判断队列是否有空闲
if (tail + 1 == head) return false;
elements[tail++] = element;
// 边界处理
if (tail == capacity) tail = 0;
return true;
}
public Integer dequeue() {
// 判断是否有元素
if (tail == head) return null;
Integer element = elements[head++];
// 边界处理
if (head == capacity) head = 0;
return element;
}
public static void main(String[] args) {
ArrayQueue arrayQueue = new ArrayQueue(10);
for (int i = 0; i < 16; i++) {
System.out.println(String.format("%02d:enqueue element=%02d, 结果 %s", i, i, arrayQueue.enqueue(i)));
if (i == 7) {
System.out.println(String.format("%02d:dequeue ,结果 %s", i, arrayQueue.dequeue()));
}
if (i == 14) {
System.out.println(String.format("%02d:dequeue ,结果 %s", i, arrayQueue.dequeue()));
}
}
for (int i = 0; i < 14; i++) {
System.out.println(String.format("%02d:dequeue ,结果 %s", i, arrayQueue.dequeue()));
}
}
}
- 链式队列（单、双、环）
扩展
- 阻塞队列：应用于生产者-消费者
- 并发队列：保障线程安全（加锁）
