Java进阶-我的算法学习之路——《我的Java打怪日记》

链表

基础数据类型 背包、队列、栈

背包：是一种不支持从中删除元素的集合数据类型，它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素（用例也可以检查是否为空或者获取背包中元素的数量）。迭代的顺序不确定且与用例无关；队列：队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。；

栈：主要作用表现为一种数据结构，是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

链表

定义：是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

下压堆栈代码实现

public class StackDemo Item implements Iterable Item {
 private int N;
 private Node first;
 private class Node {
 Item item;
 Node next;
 * 链表是否为空
 * @return
 public boolean isEmpty() {
 return N == 0;
 * 链表大小
 * @return
 public int size() {
 return N;
 * 添加
 * @param item
 public void push(Item item) {
 Node old = first;
 first = new Node();
 first.item = item;
 first.next = old;
 N++;
 * 删除最上面的节点
 * @return
 public Item pop() {
 Item t = first.item;
 first = first.next;
 N--;
 return t;
 @Override
 public Iterator Item iterator() {
 return new StackDemoIterator();
 private class StackDemoIterator implements Iterator Item {
 private Node current = first;
 @Override
 public boolean hasNext() {
 return current != null;
 @Override
 public Item next() {
 Item t = current.item;
 current = current.next;
 return t;
}

?

队列实现

public class QueueDemo Item implements Iterable Item {
 private Node first;
 private Node last;
 private int N;
 private class Node {
 Item item;
 Node next;
 * 队列事否为空
 * @return
 public boolean isEntity() {
 return first == null;
 * 队列的大小
 * @return
 public int size() {
 return N;
 * 向队列中添加元数
 * @param item
 public void enqueue(Item item) {
 Node oldLast = last;
 last = new Node();
 last.item = item;
 last.next = null;
 if (isEntity()) first = last;
 else oldLast.next = last;
 N++;
 * 取出最先进入队列的元数，并从队列中删除
 * @return
 public Item dequeue() {
 Item item = first.item;
 first = first.next;
 if (isEntity()) last = null;
 N--;
 return item;
 @Override
 public Iterator Item iterator() {
 return new QueueDemoIterator();
 private class QueueDemoIterator implements Iterator Item {
 private Node current = first;
 @Override
 public boolean hasNext() {
 return current != null;
 @Override
 public Item next() {
 Item item = current.item;
 current = current.next;
 return item;
 }

背包实现

? 背包的实现同栈的一样，仅是把pop()实现既可，push()改为add()

本文转自网络，原文链接：https://developer.aliyun.com/article/785422
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！