数据结构：链表，栈，队列的知识总结与代码实现
链表数据结构详解
链表是一种动态数据结构，由一系列节点组成，每个节点包含数据域和指针域。与数组不同，链表不需要连续的内存空间，这使得它在内存管理方面更加灵活。链表的主要类型包括单向链表、双向链表和循环链表，每种类型都有其特定的应用场景。
链表节点实现
public class LinkNode { public int data; public LinkNode next; public LinkNode(int data){ this.data = data; } }这段代码定义了链表的基本组成单元。每个节点包含两个重要部分：data字段存储实际数据，next指针指向下一个节点。构造函数初始化节点时只需要传入数据值，next指针默认为null，表示当前节点是链表的末尾。
链表基本操作
public class LinkList { public LinkNode head = new LinkNode(-1); public void endInsert(int data){ LinkNode node = new LinkNode(data); LinkNode cur = head; while (cur.next != null){ cur = cur.next; } cur.next = node; } }链表类以哨兵节点head作为起始点，简化边界条件处理。endInsert方法实现了尾插法，通过遍历找到最后一个节点，然后将新节点附加其后。这种方法保持了元素的原始顺序，时间复杂度为O(n)。
链表长度计算
public int getLength(){ LinkNode cur = head; int n = 0; while (cur.next != null){ cur = cur.next; n++; } return n; }长度计算方法通过遍历整个链表并计数实现。哨兵节点不计入长度，因此从head.next开始统计。这种方法的时间复杂度为O(n)，需要访问每个节点一次。
链表遍历打印
public void print(){ LinkNode cur = head; while (cur.next != null){ System.out.print(cur.next.data+" "); cur = cur.next; } }打印方法展示了链表的标准遍历模式。通过next指针依次访问每个节点，输出其数据值。注意这里跳过了哨兵节点的数据输出，保持了接口的整洁性。
头插法实现
public void headInsert(int data){ LinkNode node = new LinkNode(data); node.next = head.next; head.next = node; }头插法将新节点直接插入到链表头部，操作仅需常数时间O(1)。这种方法建立的链表是逆序的，常用于需要快速插入的场景，如实现栈数据结构。
按索引删除节点
public void remove(int index){ LinkNode cur = head; for (int i = 0;i < index;i++){ cur = cur.next; } cur.next = cur.next.next; }删除操作首先定位到目标位置的前驱节点，然后修改其next指针跳过目标节点。这种方法的时间复杂度为O(n)，主要消耗在定位过程上，实际删除操作是O(1)。
栈数据结构解析
栈是LIFO（后进先出）的线性结构，只允许在栈顶进行操作。这种限制使得栈在各种算法中表现出色，特别是需要回溯的场景。
数组实现栈
public class Stack { int[] arr; int top = -1; public Stack(int size){ arr = new int[size]; } }这段代码使用数组作为底层存储，top指针初始化为-1表示空栈。数组实现需要预先指定大小，适合元素数量可预测的场景，访问速度快但缺乏灵活性。
入栈操作
public void push(int data){ if (top == arr.length-1){ System.out.println("栈已满"); return; } top++; arr[top] = data; }入栈前检查栈是否已满，避免数组越界。top指针先自增再存储数据，体现了栈顶动态移动的特性。这种实现的时间复杂度为O(1)。
出栈操作
public void pop(){ if (top == -1){ System.out.println("栈已空"); return; } System.out.println(arr[top]); top--; }出栈操作返回当前栈顶元素并将指针下移。检查栈空条件防止非法访问。注意这里只是打印而非返回元素值，实际应用中可能需要修改为返回数据。
队列数据结构剖析
队列是FIFO（先进先出）的线性结构，在队尾插入，队头删除。这种特性使其成为任务调度等场景的理想选择。
循环队列实现
public class Queue{ int[] arr; int r = -1; int c = -1; public Queue(int size){ arr = new int[size]; } }这段代码实现了循环队列，使用两个指针r（rear）和c（front）分别追踪队尾和队头。初始状态都为-1表示空队列。数组实现需要考虑循环利用空间的问题。
入队操作
public void push(int data){ if (r - c == arr.length){ System.out.println("队列已满"); return; } r++; arr[r % arr.length] = data; }入队操作通过模运算实现循环存储，当指针到达数组末尾时自动回到起始位置。满队列条件r-c == arr.length确保不会覆盖未处理的元素。
出队操作
public void pop(){ if (r == c){ System.out.println("队列已空"); return; } c++; System.out.println(arr[c]); }出队操作同样使用模运算处理循环，但这里简化了实现。注意指针先移动再访问数据，与栈操作顺序相反。空队列条件r == c表示没有可处理元素。