数据结构：栈、队列、链表
目录
栈
队列
链表
栈
栈数据结构特点：先入栈的数据后出，此数据结构常用的方法有：入栈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 {//非表头节点，需要遍历整个链表，查询出要删除的节点的上一个节点tempNode 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;}
}
测试效果如下，复合预期：
