摘要：棧的實現棧這種數據結構非常有用但其實是非常簡單的。其實棧頂元素反映了在嵌套的層級關系中，最新的需要匹配的元素。

【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現，全部文章大概的內容如下：
Arrays(數組)、Stacks(棧)、Queues(隊列)、LinkedList(鏈表)、Recursion(遞歸思想)、BinarySearchTree(二分搜索樹)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(優先隊列)、SegmentTree(線段樹)、Trie(字典樹)、UnionFind(并查集)、AVLTree(AVL 平衡樹)、RedBlackTree(紅黑平衡樹)、HashTable(哈希表)

源代碼有三個：ES6（單個單個的 class 類型的 js 文件） | JS + HTML（一個 js 配合一個 html）| JAVA (一個一個的工程)

全部源代碼已上傳 github，點擊我吧，光看文章能夠掌握兩成，動手敲代碼、動腦思考、畫圖才可以掌握八成。

本文章適合 對數據結構想了解并且感興趣的人群，文章風格一如既往如此，就覺得手機上看起來比較方便，這樣顯得比較有條理，整理這些筆記加源碼，時間跨度也算將近半年時間了，希望對想學習數據結構的人或者正在學習數據結構的人群有幫助。

棧也是一種線性結構

相比數組來說相應的操作更少，

棧對應的操作是數組的子集，

因為它的本質就是一個數組，

并且它有比數組更多的限制。

棧的本質就是一個數組

它將數據排開來放的，

添加元素的時候只能從棧的一端添加元素，

取出元素的時候也只能棧的一端取出元素，

這一端叫做棧頂，當這樣的限定了數組，

從而形成了棧這種數據結構之后，

它可以在計算機世界中對于

組建邏輯產生非常非常重要的作用。

棧的操作

從棧頂添加元素，把元素一個一個的放入到棧中，

如添加值的時候為 1、2、3，

你取值的時候順序則為 3、2、1，

因為你添加元素是只能從一端放入，

取出元素時也只能從一端取出，

而這一段就是棧頂，

棧的出口和入口都是同一個位置，

所以你只能按照先進后出、后進先出的順序

添加數據或者取出數據，不存在插入和索引。

棧是一種后進先出的數據結構

也就是 Last In First Out(LIFO)，

這樣的一種數據結構，在計算機的世界里，

它擁有著不可思議的作用，

無論是經典的算法還是算法設計都接觸到

棧這種看似很簡單但其實應用非常廣泛的數據結構，

無處不在的 Undo 操作（撤銷）

編輯器的撤銷操作的原理就是靠一個棧來進行維護的，

如 將 每次輸入的內容依次放入棧中 我 喜歡 你，

如果 你 字寫錯，你撤銷一下，變成 我 喜歡，

再撤銷一下 變成 我。

程序調用的系統棧

程序調用時經常會出現在一個邏輯中間

先終止然后跳到另外一個邏輯去執行，

所謂的子函數的調用就是這個過程，

在這個過程中計算機就需要使用一個

稱為系統棧的一個數據結構來記錄程序的調用過程。

例如有三個函數 A、B、C，

當 A 執行到一半的時候調用 B，

當 B 執行到一半的時候調用 C，

C 函數可以執行運行完，

C 函數運行完了之后繼續運行未完成的 B 函數，

B 函數運行完了就運行未完成 A 函數，

A 函數運行完了就結束了。

   function A () {
      1 ...;
      2 B();
      3 ...;
   }

   function B () {
    1 ...;
    2 C();
    3 ...;
   }

   function C () {
    1 ...;
    2 ...;
    3 ...;
   }

系統棧記錄的過程是：

A 函數執行，在第二行中斷了，因為要去執行函數 B 了，

這時候函數信息A2會被放入系統棧中，系統棧中顯示：[A2]，

然后 B 函數執行，在第二行也中斷了，因為要去執行函數 C 了，

這時候函數信息 B2 會被放入系統棧中，系統棧中顯示：[A2, B2]，

然后 C 函數執行，C 函數沒有子函數可執行，那么執行到底，函數 C 執行完畢，

從系統棧中取出函數 B 的信息，系統棧中顯示：[A2]，

根據從系統棧中取出的函數 B 的信息，從函數 B 原來中斷的位置繼續開始執行，

B 函數執行完畢了，這時候會再從系統棧中取出函數 A 的，系統棧中顯示：[]，

根據從系統棧中取出的函數 A 的信息，從函數 A 原來中斷的位置繼續開始執行，

A 函數執行完了，系統棧中已經沒有函數信息了，好的，程序結束。

存入系統棧中的是函數執行時的一些信息，

所以取出來后，可以根據這些信息來繼續完成

原來函數未執行完畢的那部分代碼。

2 和 3 中解釋的原理 就是系統棧最神奇的地方

在編程的時候進行子過程調用的時候，

當一個子過程執行完成之后，

可以自動的回到上層調用中斷的位置，

并且繼續執行下去。

都是靠一個系統棧來記錄每一次調用過程中

中斷的那個調用的點來實現的。

棧雖然是一個非常簡單的數據結構

但是它能夠解決計算機領域非常復雜的一個問題，

這個問題就是這種子過程子邏輯的調用，

在編譯器內部它運行實現的原理是什么，

深入理解這個過程，

甚至能夠幫助你理解一些更復雜的邏輯過程，

比如遞歸這樣的一個過程，你會有更加深刻的理解。

棧這種數據結構非常有用

但其實是非常簡單的。

MyStack

void push(e)：入棧

E pop()：出棧

E peek()：查看位于棧頂位置的元素

int getSize()：獲取棧中實際元素的個數

boolean isEmpty()：棧是否為空

從用戶的角度看

只要支持這些操作就好了，

用戶不管你要怎樣 resize，

他只要知道你這個數組是一個動態的，

他可以不停的往里面添加元素，

并且不會出現問題就 ok，

其實對于棧也是這樣的，

對于具體的底層實現，用戶不關心，

實際底層也有多種實現方式，

所以用戶就更加不關心了。

為了讓代碼更加的清晰，

同時也是為了支持面向對象的一些特性，

比如說支持多態性，

那么就會這樣的去設計，

定義一個接口叫做 IMyStack，

接口中有棧默認的所有方法，

然后再定義一個類叫做 MyStack，

讓它去實現 IMyStack，

這樣就可以在 MyStack 中完成對應的邏輯，

這個 MyStack 就是自定義的棧。

會復用到之前自定義數組對象。

MyStack

void push(e)：O(1) 均攤

E pop()：O(1) 均攤

E peek()：O(1)

int getSize()：O(1)

boolean isEmpty()：O(1)

(interface: IMyStack, class: MyArray, class: MyStack, class: Main)

IMyStack

   public interface IMyStack {
         /**

         */
        void push(E e);

        /**
         * @return 出棧
         */
        E pop();

        /**
         * @return 查看棧頂的元素
         */
        E peek();

        /**
         * @return 獲取棧中實際元素的個數
         */
        int getSize();

        /**
         * @return 判斷棧是否為空
         */
        boolean isEmpty();
  }

3. MyArray

  public class MyArray {
        private E [] data;
        private int size;

        // 構造函數，傳入數組的容量capacity構造Array
        public MyArray (int capacity) {
              data = (E[])new Object[capacity];
              size = 0;
        }

        // 無參數的構造函數，默認數組的容量capacity=10
        public MyArray () {
  //        this( capacity: 10);
              this(10);
        }

        // 獲取數組中的元素實際個數
        public int getSize () {
              return size;
        }

        // 獲取數組的總容量
        public int getCapacity () {
              return data.length;
        }

        // 返回數組是否為空
        public boolean isEmpty () {
              return size == 0;
        }

        // 重新給數組擴容
        private void resize (int newCapacity) {

              E[] newData = (E[])new Object[newCapacity];

              int index = size - 1;
              while (index > -1) {
                    newData[index] = get(index);
                    index --;
              }

              data = newData;
        }

        // 給數組添加一個新元素
        public void add (E e) {

              if (size == data.length) {
  //            throw new IllegalArgumentException("add error. Array is full.");
                    resize(2 * data.length);
              }

              data[size] = e;
              size++;
        }

        // 向所有元素后添加一個新元素 （與 add方法功能一樣） push
        public void addLast (E e) {

              // 復用插入元素的方法
              insert(size, e);
        }

        // 在所有元素前添加一個新元素 unshift
        public void addFirst (E e) {

              insert(0, e);
        }

        // 在index索引的位置插入一個新元素e
        public void insert (int index, E e) {

              if (index < 0 || index > size) {
                    throw new IllegalArgumentException("insert error. require index < 0 or index > size");
              }

              if (size == data.length) {
  //            throw new IllegalArgumentException("add error. Array is full.");
                    resize(2 * data.length);
              }

              for (int i = size - 1; i >= index; i--) {
                    data[i + 1] = data[i];
              }

              data[index] = e;
              size++;
        }

        // 獲取index索引位置的元素
        public E get (int index) {

              if (index < 0 || index >= size) {
                    throw new IllegalArgumentException("get error. index < 0 or index >= size ");
              }
              return data[index];
        }

        // 獲取數組中第一個元素（純查看）
        public E getFirst () {
              return get(0);
        }

        // 獲取數組中最后一個元素（純查看）
        public E getLast () {
              return get(size - 1);
        }

        // 修改index索引位置的元素為e
        public void  set (int index, E e) {

              if (index < 0 || index >= size) {
                    throw new IllegalArgumentException("get error. index < 0 or index >= size ");
              }
              data[index] = e;
        }

        // 查找數組中是否有元素e
        public boolean contain (E e) {

              for (int i = 0; i < size; i++) {
  //            if (data[i] == e) { // 值比較 用 ==
                    if (data[i].equals(e)) { // 引用比較 用 equals()

                                return true;
                    }
              }
              return false;
        }

        // 查找數組中元素e所在的索引，如果不存在元素e，則返回-1
        public int find (E e) {

              for (int i = 0; i < size; i++) {
                    if (data[i].equals(e)) {
                          return i;
                    }
              }
              return -1;
        }

        // 查找數組中所有元素e所在的索引，最后返回存放 所有索引值的 自定義數組
        public MyArray findAll (E e) {

              MyArray ma = new MyArray(20);

              for (int i = 0; i < size; i++) {
                    if (data[i].equals(e)) {
                          ma.add(i);
                    }
              }

              return  ma;

  //        int[] result = new int[ma.getSize()];
  //        for (int i = 0; i < ma.getSize(); i++) {
  //            result[i] = ma.get(i);
  //        }
  //
  //        return  result;
        }

        // 從數組中刪除第一個元素, 返回刪除的元素
        public E removeFirst () {
              return remove(0);
        }

        // 從數組中刪除最后一個元素, 返回刪除的元素
        public E removeLast () {
              return remove(size - 1);
        }

        // 從數組中刪除第一個元素e
        public void removeElement (E e) {
              int index = find(e);
              if (index != -1) {
                    remove(index);
              }
  //        if (contain(e)) {
  //            int index = find(e);
  //            remove(index);
  //        }
        }

        // 從數組中刪除所有元素e
        public void removeAllElement (E e) {

              int index = find(e);
              while (index != -1) {
                    remove(index);
                    index = find(e);
              }
  //        while (contain(e)) {
  //            removeElement(e);
  //        }
        }

        // 從數組中刪除index位置的元素, 返回刪除的元素
        public E remove (int index) {

              if (index < 0 || index >= size) {
                    throw new IllegalArgumentException("get error. index < 0 or index >= size ");
              }

              E temp = data[index];

              for (int i = index; i < size - 1; i++) {
                    data[i] = data[i + 1];
              }

  //        for (int i = index + 1; i < size; i++) {
  //            data[i - 1] = data[i];
  //        }
              size --;
  //        data[size] = 0;
              data[size] = null;

              // 防止復雜度震蕩 防止容量為4，size為1時，data.length / 2 為 0
              if(size == data.length / 4 && data.length / 2 != 0) {
                    resize(data.length / 2);
              }

              return temp;
        }

        @Override
        // @Override: 方法名 日期-開發人員
        public String toString () {

              StringBuilder sb = new StringBuilder();
              String arrInfo = "Array: size = %d，capacity = %d
";
              sb.append(String.format(arrInfo, size, data.length));
              sb.append("[");
              for (int i = 0; i < size - 1; i ++) {
                    sb.append(data[i]);
                    sb.append(",");
              }
              if(!isEmpty()) {
                    sb.append(data[size - 1]);
              }
              sb.append("]");

              return sb.toString();
        }
  }

4. MyStack

  public class MyStack implements IMyStack {
        // 借用自定義個動態數組
        private MyArray ma;

        public MyStack () {
            ma = new MyArray();
        }

        public MyStack (int capacity) {
              ma = new MyArray(capacity);
        }

        /**
         * @param e
         * @return 入棧
         */
        @Override
        public void push(E e) {
              ma.addLast(e);
        }

        /**
         * @return 出棧
         */
        @Override
        public E pop() {
              return ma.removeLast();
        }

        /**
         * @return 查看棧頂的元素
         */
        @Override
        public E peek() {
              return ma.getLast();
        }

        /**
         * @return 獲取棧中實際元素的個數
         */
        @Override
        public int getSize() {
              return ma.getSize();
        }

        /**
         * @return 判斷棧是否為空
         */
        @Override
        public boolean isEmpty() {
              return ma.isEmpty();
        }

        // 返回棧的容量
        public int getCapacity () {
              return ma.getCapacity();
        }

        @Override
        // @Override: 方法名 日期-開發人員
        public String toString () {
              int size = ma.getSize();
  //        int capacity = ma.getCapacity();

              StringBuilder sb = new StringBuilder();
  //        String arrInfo = "Stack: size = %d，capacity = %d
";
  //        sb.append(String.format(arrInfo, size, capacity));
              sb.append("Stack: [");
              for (int i = 0; i < size - 1; i ++) {
                    sb.append(ma.get(i));
                    sb.append(",");
              }
              if (!ma.isEmpty()) {
                    sb.append(ma.getLast());
              }
              sb.append("] right is stack top !");

              return sb.toString();
        }
  }

5. Main

  public class Main {

        public static void main(String[] args) {

              MyStack ms = new MyStack(10);
              for (int i = 1; i <= 10 ; i++) {
                    ms.push(i);
                    System.out.println(ms);
              }

              System.out.println(ms.peek());

  //        System.out.println(ms.isEmpty());
  //        System.out.println(ms.getSize());
  //        System.out.println(ms.getCapacity());

              while (!ms.isEmpty()) {
                    ms.pop();
                    System.out.println(ms);
              }
        }
  }

## 棧的應用

1. undo 操作-編輯器
2. 系統調用棧-操作系統
3. 括號匹配-編譯器

### 以編程的方式體現棧的應用

1. 括號匹配-編譯器
1. 無論是寫表達式，這個表達式中有小括號、中括號、大括號，
2. 自然會出現括號套括號的情況發生，
3. 在這種情況下就一定會產生一個括號匹配的問題，
4. 如果括號匹配是不成功的，那么編譯器會進行報錯。
2. 編譯器是如何檢查括號匹配的問題？
1. 原理是使用了一個棧。
3. 可以通過解答 Leetcode 中的一個問題，
1. 同時來看棧在括號匹配這個問題中的應用。
2. Leetcode 是總部在美國硅谷一家
3. 非常有年頭又同時有信譽度的面向 IT 公司
4. 面試這樣一個在線的平臺，
5. 只需要注冊一個 Leetcode 用戶后，
6. 就可以看到 Leetcode 上有非常多的問題，
7. 對于每一個問題會規定輸入和輸出之后，
8. 然后就可以編寫屬于自己的邏輯，
9. 更重要的是可以直接把你編寫的這個程序
10.   提交給這個網站，
11.   這個網站會自動的判斷你的邏輯書寫的是否正確，
12.   英文網址：`leetcode.com`，
13.   2017 中文網址：`leetcode-cn.com`
4. `leetcode.com`與`leetcode-cn.com`的區別
1. `leetcode-cn.com`支持中文，
2. `leetcode-cn.com`的題目數量沒有英文版的多。
3. `leetcode-cn.com`的探索欄目的內容沒有英文版的多。
4. `leetcode-cn.com`中的題目沒有社區討論功能，但英文版的有。
5. leetcode 中第二十號題目：有效的括號

1. 如：`{ [ ( ) ] }`，
2. 從左往右，先將左側的括號入棧，
3. 然后遇到右側的括號時就查看棧頂的左側括號進行匹配，
4. 如果可以匹配表示括號有效，否則括號無效，
5. 括號有效那么就將棧頂的左側括號取出，
6. 然后繼續從左往右，左側括號就入棧，右側括號就匹配，
7. 匹配成功就讓左側括號出棧，匹配失敗就是無效括號。
8. 其實棧頂元素反映了在嵌套的層級關系中，
9. 最新的需要匹配的元素。
10.   這個算法非常的簡單，但是也非常的實用。
11.   很多工具中都有這樣的邏輯來檢查括號的匹配。

  import java.util.Stack;

  public class Solution {

        public boolean isValid(String s) {
              Stack stack = new Stack();
              for (int i = 0; i < s.length(); i++) {

                    char c = s.charAt(i);
                    switch (c) {
                          case "{":
                          case "[":
                          case "(":
                                stack.push(c);
                                break;
                          default: break;
                    }

                    switch (c) {
                          case "}":
                                if(stack.isEmpty() || stack.pop() != "{" ) {
                                      System.out.println("valid error. not parentheses. in");
                                      return false;
                                }
                                break;
                          case "]":
                                if(stack.isEmpty() || stack.pop() != "[") {
                                      System.out.println("valid error. not parentheses. in");
                                      return false;
                                }
                                break;
                          case ")":
                                if(stack.isEmpty() || stack.pop() != "(") {
                                      System.out.println("valid error. not parentheses. in");
                                      return false;
                                }
                                break;
                          default: break;
                    }
              }

              if (stack.isEmpty()) {
                    System.out.println("valid success. parentheses.");
                    return true;
              } else {
                    System.out.println("valid error. not parentheses. out.");
                    return false;
              }
        }

        public static void main(String[] args) {
           Solution s = new Solution();
           s.isValid("{ [ ( ) ] }");
           s.isValid(" [ ( ] ) ");
        }
  }

  // 7ms的
  import java.util.Stack;

  public class Solution {

        public boolean isValid(String s) {
              Stack stack = new Stack();
              int cur = 0;
              for (int i = 0; i < s.length(); i++) {

                    char c = s.charAt(i);
                    switch (c) {
                          case "{":
                          case "[":
                          case "(":
                                cur ++;
                                stack.push(c);
                                break;
                          default: break;
                    }

                    switch (c) {
                          case "}":
                                if(cur-- == 0 || stack.pop() != "{" ) {
                                      return false;
                                }
                                break;
                          case "]":
                                if(cur-- == 0 || stack.pop() != "[") {
                                      return false;
                                }
                                break;
                          case ")":
                                if(cur-- == 0 || stack.pop() != "(") {
                                      return false;
                                }
                                break;
                          default: break;
                    }
              }
              return cur == 0;
        }
  }

6. leetcode 是一個非常好的準備面試的一個平臺
1. 同時它也是算法競賽的一個入門的地方。
2. 你可以通過題庫來進行訓練，
3. 題庫的右邊有關于這些題目的標簽，
4. 你可以選擇性的去練習，
5. 而且可以根據難度來進行排序這些題目，
6. 你不一定要全部答對，
7. 因為這些題目不僅僅只有一個標簽。
7. 如果你想使用你自己寫的類，
1. 那么你可以你自己寫的自定義棧作為內部類來進行使用，
2. 例如 把自定義棧的代碼放到 Solution 類中，
3. 那樣也是可以使用，
4. 還樣就順便測試了你自己數據結構實現的邏輯是否正確。

### 學習方法討論

1. 不要完美主義。掌握好“度”。
1. 太過于追求完美會把自己逼的太緊，
2. 會產生各種焦慮的心態，. 最后甚至會懷疑自己，
3. 溫故而知新，不要停止不前，
4. 掌握好這個度，不存在你把那些你認為完全掌握了，
5. 然后就成了某一個領域的專家，
6. 相反一旦你產生很濃厚的厭惡感，
7. 那么就意味著你即將會放棄或者已經選擇了放棄，
8. 雖然你之前想把它做到 100 分，
9. 但是由于你的放棄讓它變為 0 分。
2. 學習本著自己的目標去。
1. 不要在學的過程中偏離了自己的目標。
2. 要分清主次。
3. 難的東西，你可以慢慢的回頭看一看。
1. 那樣才會更加的柳暗花明，
2. 更能提升自己的收獲。

## 隊列 Queue

1. 隊列也是一種線性的數據結構
1. 依然就是將數據排成一排。
2. 相比數組，隊列對應的操作是數組的子集。
1. 與棧只能在同一端添加元素和取出元素有所不同，
2. 在隊列中只能從一端(隊尾)添加元素，
3. 只能從另一端(隊首)取出元素。
3. 例如你去銀行取錢
1. 你需要排隊，入隊的人不允許插隊，
2. 所以他要從隊尾開始排隊，
3. 而前面取完錢的會從隊首離開，
4. 然后后面的人再往前移動一位，
5. 最后重復這個過程，
6. 直到沒人再排隊取錢了。
4. 隊列是一種先進先出的數據結構（先到先得）
1. First In First Out(FIFO) 先進先出

### 隊列的實現

1. `Queue`
1. `void enqueue(E)`：入隊
2. `E dequeue()`：出隊
3. `E getFront()`：查看隊首的元素
4. `int getSize()`：獲取隊列中的實際元素大小
5. `boolean isEmpty()`：獲取隊列是否為空的 bool 值
2. 寫一個接口叫做 IMyQueue
1. 讓 MyQueue 實現這個接口
2. 這樣就符合了面向對象的特性。

### 代碼示例

1. `(interface: IMyQueue, class: MyArray, class: MyQueue, class: Main)`
2. IMyQueue

  public interface IMyQueue {
        /**
         * @param e
         *  入隊
         */
        void enqueue (E e);

        /**
         * @return e
         *  出隊
         */
        E dequeue ();

        /**
         * @return e
         *  查看隊首的元素
         */
        E getFront ();

        /**
         * @return number
         *  獲取隊列中的實際元素個數
         */
        int getSize ();

        /**
         * @return bool
         *   獲取隊列是否為空的bool值
         */
        boolean isEmpty ();
  }

3. MyArray

  public class MyArray {
        private E [] data;
        private int size;

        // 構造函數，傳入數組的容量capacity構造Array
        public MyArray (int capacity) {
              data = (E[])new Object[capacity];
              size = 0;
        }

        // 無參數的構造函數，默認數組的容量capacity=10
        public MyArray () {
  //        this( capacity: 10);
              this(10);
        }

        // 獲取數組中的元素實際個數
        public int getSize () {
              return size;
        }

        // 獲取數組的總容量
        public int getCapacity () {
              return data.length;
        }

        // 返回數組是否為空
        public boolean isEmpty () {
              return size == 0;
        }

        // 重新給數組擴容
        private void resize (int newCapacity) {

              E[] newData = (E[])new Object[newCapacity];

              int index = size - 1;
              while (index > -1) {
                    newData[index] = get(index);
                    index --;
              }

              data = newData;
        }

        // 給數組添加一個新元素
        public void add (E e) {

              if (size == data.length) {
  //            throw new IllegalArgumentException("add error. Array is full.");
                    resize(2 * data.length);
              }

              data[size] = e;
              size++;
        }

        // 向所有元素后添加一個新元素 （與 add方法功能一樣） push
        public void addLast (E e) {

              // 復用插入元素的方法
              insert(size, e);
        }

        // 在所有元素前添加一個新元素 unshift
        public void addFirst (E e) {

              insert(0, e);
        }

        // 在index索引的位置插入一個新元素e
        public void insert (int index, E e) {

              if (index < 0 || index > size) {
                    throw new IllegalArgumentException("insert error. require index < 0 or index > size");
              }

              if (size == data.length) {
  //            throw new IllegalArgumentException("add error. Array is full.");
                    resize(2 * data.length);
              }

              for (int i = size - 1; i >= index; i--) {
                    data[i + 1] = data[i];
              }

              data[index] = e;
              size++;
        }

        // 獲取index索引位置的元素
        public E get (int index) {

              if (index < 0 || index >= size) {
                    throw new IllegalArgumentException("get error. index < 0 or index >= size ");
              }
              return data[index];
        }

        // 獲取數組中第一個元素（純查看）
        public E getFirst () {
              return get(0);
        }

        // 獲取數組中最后一個元素（純查看）
        public E getLast () {
              return get(size - 1);
        }

        // 修改index索引位置的元素為e
        public void  set (int index, E e) {

              if (index < 0 || index >= size) {
                    throw new IllegalArgumentException("get error. index < 0 or index >= size ");
              }
              data[index] = e;
        }

        // 查找數組中是否有元素e
        public boolean contain (E e) {

              for (int i = 0; i < size; i++) {
  //            if (data[i] == e) { // 值比較 用 ==
                    if (data[i].equals(e)) { // 引用比較 用 equals()

                                return true;
                    }
              }
              return false;
        }

        // 查找數組中元素e所在的索引，如果不存在元素e，則返回-1
        public int find (E e) {

              for (int i = 0; i < size; i++) {
                    if (data[i].equals(e)) {
                          return i;
                    }
              }
              return -1;
        }

        // 查找數組中所有元素e所在的索引，最后返回存放 所有索引值的 自定義數組
        public MyArray findAll (E e) {

              MyArray ma = new MyArray(20);

              for (int i = 0; i < size; i++) {
                    if (data[i].equals(e)) {
                          ma.add(i);
                    }
              }

              return  ma;

  //        int[] result = new int[ma.getSize()];
  //        for (int i = 0; i < ma.getSize(); i++) {
  //            result[i] = ma.get(i);
  //        }
  //
  //        return  result;
        }

        // 從數組中刪除第一個元素, 返回刪除的元素
        public E removeFirst () {
              return remove(0);
        }

        // 從數組中刪除最后一個元素, 返回刪除的元素
        public E removeLast () {
              return remove(size - 1);
        }

        // 從數組中刪除第一個元素e
        public void removeElement (E e) {
              int index = find(e);
              if (index != -1) {
                    remove(index);
              }
  //        if (contain(e)) {
  //            int index = find(e);
  //            remove(index);
  //        }
        }

        // 從數組中刪除所有元素e
        public void removeAllElement (E e) {

              int index = find(e);
              while (index != -1) {
                    remove(index);
                    index = find(e);
              }
  //        while (contain(e)) {
  //            removeElement(e);
  //        }
        }

        // 從數組中刪除index位置的元素, 返回刪除的元素
        public E remove (int index) {

              if (index < 0 || index >= size) {
                    throw new IllegalArgumentException("get error. index < 0 or index >= size ");
              }

              E temp = data[index];

              for (int i = index; i < size - 1; i++) {
                    data[i] = data[i + 1];
              }

  //        for (int i = index + 1; i < size; i++) {
  //            data[i - 1] = data[i];
  //        }
              size --;
  //        data[size] = 0;
              data[size] = null;

              // 防止復雜度震蕩 防止容量為4，size為1時，data.length / 2 為 0
              if(size == data.length / 4 && data.length / 2 != 0) {
                    resize(data.length / 2);
              }

              return temp;
        }

        @Override
        // @Override: 方法名 日期-開發人員
        public String toString () {

              StringBuilder sb = new StringBuilder();
              String arrInfo = "Array: size = %d，capacity = %d
";
              sb.append(String.format(arrInfo, size, data.length));
              sb.append("[");
              for (int i = 0; i < size - 1; i ++) {
                    sb.append(data[i]);
                    sb.append(",");
              }
              sb.append(data[size - 1]);
              sb.append("]");

              return sb.toString();
        }
  }

4. MyQueue

  public class MyQueue implements IMyQueue {
        private MyArray ma;

        public MyQueue () {
              ma = new MyArray();
        }

        public MyQueue (int capacity) {
              ma = new MyArray(capacity);
        }

        /**
         * @param e
         *  入隊
         */
        @Override
        public void enqueue (E e) {
              ma.addLast(e);
        }

        /**
         * @return e
         *  出隊
         */
        @Override
        public E dequeue () {
              return ma.removeFirst();
        }

        /**
         * @return e
         *  查看隊首的元素
         */
        @Override
        public E getFront () {
              return ma.getFirst();
        }

        /**
         * @return number
         *  獲取隊列中的實際元素個數
         */
        @Override
        public int getSize () {
              return ma.getSize();
        }

        /**
         * @return bool
         *  獲取隊列是否為空的bool值
         */
        @Override
        public boolean isEmpty () {
              return ma.isEmpty();
        }

        // 獲取隊列容量
        public int getCapacity () {
              return ma.getCapacity();
        }

        @Override
        public String toString () {
              int size = ma.getSize ();
              StringBuilder sb = new StringBuilder();
              sb.append("Queue: head [");
              for (int i = 0; i < size - 1; i ++) {
                    sb.append(ma.get(i));
                    sb.append(",");
              }
              if(!isEmpty()) {
                    sb.append(ma.getLast());
              }
              sb.append("] foot. left is queue top!");

              return sb.toString();
        }
  }

5. Main

  public class Main {

        public static void main(String[] args) {

              MyQueue mq = new MyQueue(10);
              for (int i = 1; i <= 10 ; i++) {
                    mq.enqueue(i);
                    System.out.println(mq);
              }

              System.out.println(mq.getFront());

              while (!mq.isEmpty()) {
                    System.out.println(mq);
                    mq.dequeue();
              }
        }
  }

### 隊列的復雜度分析

1. `MyQueue`
1. `void enqueue(E)`： `O(1)` 均攤
2. `E dequeue()`：`O(n)` 出隊的性能消耗太大了
3. `E getFront()`：`O(1)`
4. `int getSize()`：`O(1)`
5. `boolean isEmpty()`：`O(1)`
2. 出隊的性能消耗太大了
1. 如果有一百萬條數據，每次都要操作一百萬次，
2. 那么需要優化它，要讓他出隊的時候時間復雜度為`O(1)`，
3. 并且還要讓他入隊的時候時間復雜度依然是`O(1)`。
4. 可以使用循環隊列的方式來解決這個問題。

## 循環隊列

1. 自定義隊列的性能是有局限性的
1. 出隊操作時的時間復雜度為`O(n)`，
2. 要把他變為`O(1)`。
2. 當取出隊列的第一個元素后，
1. 第一個元素后面所有的元素位置不動，
2. 這樣一來時間復雜度就為`O(1)`了，
3. 下一次再取元素的時候從第二個開始，
4. 取完第二個元素之后，
5. 第二個元素后面所有的元素位置也不動，
6. 入隊的話直接往隊尾添加元素即可。
3. 循環隊列的使用
1. 你可以先用一個數字變量 front 指向隊首，
2. 然后再用一個數字變量 tail 指向隊尾，
3. front 指向的是隊列中的第一個元素，
4. tail 指向的是隊列中最后一個元素的后一個位置，
5. 當隊列整體為空的時候，它們才會指向同一個位置，
6. 所以`front == tail`時隊列就為空，
7. 如果有一個元素入隊了，
8. front 會指向這個元素，
9. 而 tail 會指向這個元素后一個位置（也就是 tail++），
10.   然后再有一個元素入隊了，
11.   front 還是指向第一個元素的位置，
12.   而 tail 會指向第二個元素的后一個位置（還是 tail++），
13.   然后再來四個元素入隊了，
14.   front 還是指向第一個元素的位置，
15.   而 tail 會指向第六個元素的后一個位置（tail++四次），
16.   之后 要出隊兩個元素，
17.   front 會指向第三個元素的位置（也就是 front++兩次），
18.   front 從指向第一個元素變成指向第三個元素的位置，
19.   因為前兩個已經出隊了，
20.   這時候再入隊一個元素，
21.   tail 會指向第七個元素的后一個位置（還是 tail++），
22.   這時隊列的容量已經滿了，可能需要擴容，
23.   但是由于隊列中有兩個元素已經出隊了，
24.   那這兩個位置空出來了，這時就需要利用這兩個位置的空間了，
25.   這就是循環隊列了，以循環的方式重復利用空間，
26.   自定義隊列使用自定義數組實現的，
27.   其實就是把數組看成一個環，數組中一共可以容納 8 個元素，
28.   索引是 0-7，那么 7 之后的索引應該是 0，tail 應該指向 0，
29.   而不是認為整個數組的空間已經滿了，
30.   應該使用 tail 對數組的容量進行求余計算，
31.   tail 為 8，容量也為 8，求余之后為 0，所以 tail 應該指向 0，
32.   這時再入隊一個元素，tail 指向這個元素的后一個位置，即 1，
33.   這時候如果再入隊一個元素，那么此時 tail 和 front 相等，
34.   但是那并不能證明隊列為空，反而是隊列滿了，
35.   所以需要在隊列滿之前進行判斷，`tail+1==front`，
36.   就表示隊列已滿，當數組中只剩最后一個空間了，
37.   隊列就算是滿的，因為再入隊就會讓 tail 與 front 相等，
38.   而那個條件是隊列已空才成立的，雖然對于整個數組空間來說，
39.   是有意識地浪費了一個空間，但是減少了很大的時間消耗，
40.   所以當`(tail+1)%c==front`時就可以擴容了，
41.   將`tail+1==front`變成`(tail+1)%c==front`是因為
42.   tail 從數組的末端跑到前端是有一個求余的過程，
43.   例如 front 指向的是第一個元素，而 tail 指向的第六個元素之后的位置，
44.   那么此時 front 為 0，tail 為 7，容量為 8，還有一個浪費掉的空間，
45.   這時候`(tail+1)%c==front`，所以隊列滿了，
46.   這就是循環隊列所有的具體實現必須遵守的規則，
47.   所有的 front 和 tail 向后移動的過程都要是這種循環的移動，
48.   例如鐘表，11 點鐘的下一個鐘頭為 12 點鐘，也可以管它叫做 0 點，
49.   之后又會變成 1 點、2 點、3 點、4 點依次類推，
50.   所以整個循環隊列的索引也是像鐘表一樣形成了一個環，
51.   只不過不一定有 12 刻度，而刻度的數量是由數組的容量(空間總數)決定的，
52.   這就是循環隊列的原理。
4. 使用循環隊列之后，
1. 出隊操作不再是整體往前移動一位了
2. 而是通過改變 front 的指向，
3. 入隊操作則是改變 tail 的指向，
4. 整個操作循環往復，
5. 這樣一來出隊入隊的時間復雜度都為`O(1)`了。

### 循環隊列的簡單實現解析

1. 循環隊列 MyLoopQueue
1. 他的實現與 MyQueue 有很大的不同，
2. 所以就不使用 MyArray 自定義動態數組了。
2. 循環隊列要從底層重新開始寫起
1. data：一個數組。
2. front： 指向隊頭有效元素的索引。
3. tail： 指向隊尾有效元素的后一個位置的索引。
4. size： 通過 front 和 tail 也可以做到循環。
5. 但是使用 size 能夠讓邏輯更加的清晰明了。
3. 循環隊列實現完畢之后，
1. 你可以不使用 size 來進行循環隊列的維護，
2. 而完完全全的使用 front 和 tail，
3. 這樣難度會稍微的難一點，
4. 因為具體邏輯需要特別的小心，
5. 會有一些小陷阱。
6. 可以試著添加 resize 數組擴容縮容功能到極致，
7. 可以鍛煉邏輯能力、程序編寫調試能力等等。

## 循環隊列的實現

1. 入隊前先判斷隊列是否已經滿了
1. 判斷方式 `(tail + 1) % data.length == front`
2. 判斷分析 (隊尾指向的索引 + 1)余以數組的容量是否為隊首指向的索引，
2. 從用戶的角度上來看
1. 隊列里就是有這么多元素，
2. 一側是隊首一側是隊尾，
3. 其它的內容包括實際的數組的大小是用戶指定的容量大小+1，
4. 這些實現細節，用戶是全部不知道的，給用戶屏蔽掉了，
5. 這就是封裝自定義數據結構的目的所在，
6. 用戶在具體使用這些自定義數據結構的時候，
7. 只需要了解接口中所涉及到的這些方法即可，
8. 至于它的內部細節用戶完全可以不用關心。

### 代碼示例 `(class: MyLoopQueue, class: Main)`

1. MyLoopQueue

  public class MyLoopQueue implements IMyQueue {
        private E[] data;
        private int front, tail;
        private int size;

        public MyLoopQueue (int capacity) {
              // 這個數組的容量為 傳進來的指定容量+1，
              // 因為會有意識的浪費一個空間，只有+1后，
              // 才能裝下用戶期望傳進來的所有數據
              data = (E[])new Object[capacity + 1];

              front = tail = size = 0;
        }

        public MyLoopQueue () {
              this(10);
        }

        public int getCapacity () {
              return data.length - 1;
        }

        private void resize (int newCapacity) {

              E[] newData = (E[]) new Object[newCapacity + 1];
              for (int i = 0; i < size; i++) {
  //            索引可能會越界，于是就要取余一下，
  //            如果越界了，就從隊首開始
                    newData[i] = data[(front + i) % data.length];
              }
              data = newData;
              front = 0;
              tail = size;
        }

        /**
         * @param e 入隊
         */
        @Override
        public void enqueue(E e) {

              if ((tail + 1) % data.length == front) {
                    resize(getCapacity() * 2);
              }

              data[tail] = e;
  //        tail在隊列中循環
              tail = (tail + 1) % data.length;
              size ++;
        }

        /**
         * @return e
         * 出隊
         */
        @Override
        public E dequeue() {

              if(isEmpty()) {
                    throw new IllegalArgumentException("can"t dequeue from an empty queue.");
              }

              E e = data[front];
              data[front] = null;
              front = (front + 1) % data.length;
              size -- ;

              if (getCapacity() / 4 == size && getCapacity() / 2 != 0) {
                    resize(getCapacity() / 2);
              }

              return e;
        }

        /**
         * @return e
         * 查看隊首的元素
         */
        @Override
        public E getFront() {
              if (isEmpty()) {
                    throw new IllegalArgumentException("queue is empty.");
              }
              return data[front];
        }

        /**
         * @return number
         * 獲取隊列中的實際元素個數
         */
        @Override
        public int getSize() {
              return size;
        }

        /**
         * @return bool
         * 獲取隊列是否為空的bool值
         */
        @Override
        public boolean isEmpty() {
              return front == tail;
        }

        @Override
        public String toString () {
              StringBuilder sb = new StringBuilder();
              sb.append(String.format("Queue: size = %d，capacity = %d 
", size, getCapacity()));
              sb.append("Queue: head [");
  //        第一種遍歷方式
  //        for (int i = 0; i < size - 1; i ++) {
  //            sb.append(data[(front + i) % data.length]);
  //            sb.append(",");
  //        }
  //        if(!isEmpty()) {
  //            sb.append(data[(front + size - 1) % data.length]);
  //        }

              // 第二種遍歷方式
              for (int i = front; i != tail ; i = (i + 1) % data.length) {
                    sb.append(data[i]);

                    if ((i + 1) % data.length != tail) {
                          sb.append(",");
                    }
              }

              sb.append("] foot. left is queue top!");
              sb.append("
");

              return sb.toString();
        }

  }

2. Main

  public class Main {

        public static void main(String[] args) {

  //        MyQueue mq = new MyQueue(10);
              MyLoopQueue mq = new MyLoopQueue(10);

              for (int i = 1; i <= 11 ; i++) {
                    mq.enqueue(i);
                    System.out.println(mq);
              }

              System.out.println(mq.getFront());

              while (!mq.isEmpty()) {
                    System.out.println(mq);
                    mq.dequeue();
              }
        }
  }

## 自定義隊列兩種方式的對比

1. 原來自定隊列的出隊時，時間復雜度為`O(n)`，
1. 使用循環隊列的方式后，
2. 出隊時時間復雜度為`O(1)`，
3. 復雜度的分析只是一個抽象上的理論結果，
4. 具體這個變化在性能上意味著會有一個質的飛躍，
5. 隊列中元素越多，性能就更能夠體現出來。

### 自定義隊列的時間復雜度對比

1. `MyQueue`：數組隊列，使用了自定義數組
1. `void enqueue(E)`：`O(1)` 均攤
2. `E dequeue()`：`O(n)` 出隊的性能消耗太大了
3. `E getFront()`：`O(1)`
4. `int getSize()`：`O(1)`
5. `boolean isEmpty()`：`O(1)`
2. `MyLoopQueue`：循環隊列，沒有使用自定義數組
1. `void enqueue(E)`：`O(1)` 均攤
2. `E dequeue()`：`O(1)` 均攤
3. `E getFront()`：`O(1)`
4. `int getSize()`：`O(1)`
5. `boolean isEmpty()`：`O(1)`

### 循環隊列的復雜度分析

1. 通過設置循環隊列底層的機制
1. 雖然稍微比數組隊列要復雜一些，
2. 但是這些復雜的工作是值得的，
3. 因為他使得在數組隊列中，
4. 出隊本該有`O(n)`的復雜度變為了`O(1)`的復雜度，
5. 但是這個`O(1)`為均攤的時間復雜度，
6. 因為出隊還是會涉及到縮容的操作，
7. 在縮容的過程中還是免不了對隊列中所有的元素進行一次遍歷，
8. 但是由于不可能每一次操作都會觸發縮容操作來遍歷所有的元素，
9. 所以應該使用均攤復雜度的分析方式，那樣才更加合理。
2. 循環隊列中所有的操作都是`O(1)`的時間復雜度。
3. `O(n)`的復雜度要比`O(1)`要慢，
1. 但是具體會慢多少可以通過程序來進行測試，
2. 這樣就能夠知道在算法領域和數據結構領域
3. 要費這么大的勁去研究更加優化的操作
4. 這背后實際的意義到底在哪里。
4. 讓這兩個隊列進行入隊和出隊操作，
1. 操作的次數為 100000 次，
2. 通過在同一臺機器上的耗時情況，
3. 就能夠知道性能有什么不同。
5. 數據隊列與循環隊列十萬次入隊出隊操作后的結果是：
1. `MyQueue，time：15.463472711s`，
2. `MyLoopQueue，time：0.009602136s`，
3. 循環隊列就算操作一億次，
4. 時間也才`MyLoopQueue，time：2.663835877s`，
5. 這個差距主要是在出隊的操作中體現出來的，
6. 這個性能差距是上千倍，所以這也是性能優化的意義。
6. 測試性能時，不要只測試一次，你可以測試 100 次
1. 取平均值即可，因為這不光和你的程序相關，
2. 還會和你當前計算機的狀態有關，
3. 特別是在兩個算法的時間復雜度一致時，
4. 測試性能時可能出入會特別大，
5. 因為這有多方面原因、如語法、語言、編譯器、解釋器等等，
6. 這些都會導致你代碼真正運行的邏輯機制
7. 和你理論分析的是不一樣的，
8. 但是當兩個算法的時間復雜度不一致時，
9. 這時候測試性能的結果肯定會有巨大的差異，
10.   如`O(1)`對`O(n)`、`O(n)`對`O(n^2)`、`O(n)`對`O(logn)`。

### 隊列的應用

1. 隊列的概念在生活中隨處可見
1. 所以使用計算機來模擬生活中隊列，
2. 如在業務方面你需要排隊，
3. 或者更加專業的一些領域，
4. 比如 網絡數據包的排隊、
5. 操作系統中執行任務的排隊等，
6. 都可以使用隊列。
2. 隊列本身是一個很復雜的問題
1. 對于排隊來說，隊首到底怎么定義，
2. 是有多樣的定義方式的，也正因為如此，
3. 所以存在廣義隊列這個概念，
4. 這兩種自定義隊列
5. 在組建計算機世界的其它算法邏輯的時候
6. 也是有重要的應用的，最典型的應用是廣度優先遍歷。