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