目录
栈
栈数据结构特点：先入栈的数据后出，此数据结构常用的方法有：入栈push、出栈pop、查看栈顶元素peek等，下方示例以数组实现栈结构。
package com.ginko.datastructure;
import lombok.extern.slf4j.Slf4j;
/**
* 基于数组实现的栈
*/
@Slf4j
public class ArrayStack {
private int arr[];//栈存放的数据
private int top;//栈顶索引
/**
* 构造栈
* @param capacity 栈容量
*/
public ArrayStack(int capacity) {
arr = new int[capacity];
top = -1;//初始top为-1
}
/**
* 出栈，从栈顶获取元素
* @return
*/
public int pop() {
if(top == -1) {
throw new RuntimeException("栈为空，无法出栈...");
}
return arr[top--];//出栈后，栈顶下移
}
/**
* 入栈
* @param value 入栈数据
* @return
*/
public void push(int value) {
if(top == arr.length -1) {
throw new RuntimeException("栈已满，无法入栈...");
}
arr[++top] = value;//入栈，先将栈顶++
}
/**
* 获取栈顶数据
* @return
*/
public int peek() {
if(top == -1) {
throw new RuntimeException("栈为空，没有栈顶数据...");
}
return arr[top];
}
public static void main(String[] args) {
ArrayStack arrayStack = new ArrayStack(5);
arrayStack.push(100);
arrayStack.push(90);
arrayStack.push(80);
arrayStack.push(60);
arrayStack.push(50);
log.info("出栈数据：{}",arrayStack.pop());
log.info("出栈数据：{}",arrayStack.pop());
log.info("栈顶数据：{}",arrayStack.peek());
}
}
测试效果如下，复合预期：
队列
队列数据结构特点：先入队列的数据先出，此数据结构常用的方法有：入对enQueue、出对deQueue等，下方示例以数组实现队列结构。
package com.ginko.datastructure;
import lombok.extern.slf4j.Slf4j;
/**
* 基于数组实现的队列
*/
@Slf4j
public class ArrayQueue {
private int arr[];//存放队列元素
private int head;//队列头指针
private int tail;//队列尾指针
private int size;//队列里面数据的个数
/**
* 构造队列
* @param capacity 队列容量
*/
public ArrayQueue(int capacity) {
arr = new int[capacity];
head = 0;
tail = -1;
size = 0;//队列没有数据
}
/**
* 入队
* @param value 加入队列的值
*/
public void enQueue(int value) {
//队列满了就不能入队
if(size == arr.length) {
throw new RuntimeException("队列已满，无法加入队列...");
}
//加入队列加载数组的末尾
arr[++tail] = value;
size ++;//队列数据自增
}
/**
* 出队，从队列头获取数据
*/
public int deQueue() {
//队列满了就不能入队
if(size == 0) {
throw new RuntimeException("队列为空，无法出队列...");
}
//从队列头获取数据
size--;//队列数据减少
return arr[head++];
}
public static void main(String[] args) {
ArrayQueue arrayQueue = new ArrayQueue(5);
arrayQueue.enQueue(10);
arrayQueue.enQueue(20);
arrayQueue.enQueue(30);
arrayQueue.enQueue(40);
arrayQueue.enQueue(50);
log.info("出队数据：{}",arrayQueue.deQueue());
log.info("出队数据：{}",arrayQueue.deQueue());
log.info("队列元素个数：{}",arrayQueue.size);
}
}
测试效果如下，复合预期：
链表
链表数据结构特点：通过前后指针串联起来完整的数据，包含单向链表、双向链表等，下方示例演示单向链表，核心方法有链表插入元素，删除元素，遍历链表等。
package com.ginko.datastructure;
import lombok.extern.slf4j.Slf4j;
/**
* 链表，单向链表，在链表的末尾加入数据
*/
@Slf4j
public class LinkList {
Node head;//头节点
int size;//链表中节点的个数
public LinkList() {
head = null;
size = 0;
}
/**
* 加入链表，加入链表的末尾
* @param value
*/
public void addElement(int value) {
if(head == null) {
//加入链表头
head = new Node(value,null);
size ++;//链表中节点的个数
return;
}
//找到此链表的末尾节点,遍历后temp节点就是末尾节点
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
//新建末尾节点的下一个节点,然后设置末尾节点
Node tailNodeNext = new Node(value,null);
temp.next = tailNodeNext;
size ++;//链表中节点的个数
}
/**
* 删除链表中的元素，核心是找到删除节点的位置
* @param value 要删除的链表数据
*/
public void delElement(int value) {
if(head == null) {
throw new RuntimeException("链表为空,无法删除元素...");
}
//删除表头节点
if(head.value == value) {
//要删除表头
Node headNext = head.next;
//直接将head next设置为表头就删除表头了
head = headNext;
size--;//链表中节点的个数
}else {
//非表头节点，需要遍历整个链表，查询出要删除的节点的上一个节点temp
Node temp = head;
while (temp.next != null && temp.next.value != value) {
temp = temp.next;
}
if(temp.next.value == value) {
if(temp.next != null) {
temp.next = temp.next.next;//跳过要删除的节点，指向下一个节点
}else {
temp.next = null;
}
}
size--;//链表中节点的个数
}
}
/**
* 输出链表节点数据
*/
public void outputLinkInfo() {
Node headNode = head;
while (headNode != null) {
log.info("节点数据：{}",headNode.value);
headNode = headNode.next;
}
}
public static void main(String[] args) {
LinkList linkList = new LinkList();
linkList.addElement(10);
linkList.addElement(20);
linkList.addElement(30);
linkList.addElement(40);
linkList.addElement(50);
linkList.outputLinkInfo();
log.info("链表节点数量:{}",linkList.size);
linkList.delElement(20);
linkList.delElement(50);
linkList.outputLinkInfo();
log.info("链表节点数量:{}",linkList.size);
}
}
/**
* 链表中的节点
*/
class Node{
int value;//节点的值
Node next;//链表指针，指向下一个节点
public Node(int value,Node next) {
this.value = value;
this.next = next;
}
}
测试效果如下，复合预期：
