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()