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

链表

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

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

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

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

1. 链表

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

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

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;
           }
       }
   }

   ​

2. 队列实现

   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;
             }
         }
     }

3. 背包实现

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