摘要：棧的實現(xiàn)棧這種數(shù)據(jù)結(jié)構(gòu)非常有用但其實是非常簡單的。其實棧頂元素反映了在嵌套的層級關(guān)系中，最新的需要匹配的元素。

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

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

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

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

棧也是一種線性結(jié)構(gòu)

相比數(shù)組來說相應(yīng)的操作更少，

棧對應(yīng)的操作是數(shù)組的子集，

因為它的本質(zhì)就是一個數(shù)組，

并且它有比數(shù)組更多的限制。

棧的本質(zhì)就是一個數(shù)組

它將數(shù)據(jù)排開來放的，

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

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

這一端叫做棧頂，當(dāng)這樣的限定了數(shù)組，

從而形成了棧這種數(shù)據(jù)結(jié)構(gòu)之后，

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

組建邏輯產(chǎn)生非常非常重要的作用。

棧的操作

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

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

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

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

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

而這一段就是棧頂，

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

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

添加數(shù)據(jù)或者取出數(shù)據(jù)，不存在插入和索引。

棧是一種后進先出的數(shù)據(jù)結(jié)構(gòu)

也就是 Last In First Out(LIFO)，

這樣的一種數(shù)據(jù)結(jié)構(gòu)，在計算機的世界里，

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

無論是經(jīng)典的算法還是算法設(shè)計都接觸到

棧這種看似很簡單但其實應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu)，

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

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

如 將 每次輸入的內(nèi)容依次放入棧中 我 喜歡 你，

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

再撤銷一下 變成 我。

程序調(diào)用的系統(tǒng)棧

程序調(diào)用時經(jīng)常會出現(xiàn)在一個邏輯中間

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

所謂的子函數(shù)的調(diào)用就是這個過程，

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

稱為系統(tǒng)棧的一個數(shù)據(jù)結(jié)構(gòu)來記錄程序的調(diào)用過程。

例如有三個函數(shù) A、B、C，

當(dāng) A 執(zhí)行到一半的時候調(diào)用 B，

當(dāng) B 執(zhí)行到一半的時候調(diào)用 C，

C 函數(shù)可以執(zhí)行運行完，

C 函數(shù)運行完了之后繼續(xù)運行未完成的 B 函數(shù)，

B 函數(shù)運行完了就運行未完成 A 函數(shù)，

A 函數(shù)運行完了就結(jié)束了。

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

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

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

系統(tǒng)棧記錄的過程是：

A 函數(shù)執(zhí)行，在第二行中斷了，因為要去執(zhí)行函數(shù) B 了，

這時候函數(shù)信息A2會被放入系統(tǒng)棧中，系統(tǒng)棧中顯示：[A2]，

然后 B 函數(shù)執(zhí)行，在第二行也中斷了，因為要去執(zhí)行函數(shù) C 了，

這時候函數(shù)信息 B2 會被放入系統(tǒng)棧中，系統(tǒng)棧中顯示：[A2, B2]，

然后 C 函數(shù)執(zhí)行，C 函數(shù)沒有子函數(shù)可執(zhí)行，那么執(zhí)行到底，函數(shù) C 執(zhí)行完畢，

從系統(tǒng)棧中取出函數(shù) B 的信息，系統(tǒng)棧中顯示：[A2]，

根據(jù)從系統(tǒng)棧中取出的函數(shù) B 的信息，從函數(shù) B 原來中斷的位置繼續(xù)開始執(zhí)行，

B 函數(shù)執(zhí)行完畢了，這時候會再從系統(tǒng)棧中取出函數(shù) A 的，系統(tǒng)棧中顯示：[]，

根據(jù)從系統(tǒng)棧中取出的函數(shù) A 的信息，從函數(shù) A 原來中斷的位置繼續(xù)開始執(zhí)行，

A 函數(shù)執(zhí)行完了，系統(tǒng)棧中已經(jīng)沒有函數(shù)信息了，好的，程序結(jié)束。

存入系統(tǒng)棧中的是函數(shù)執(zhí)行時的一些信息，

所以取出來后，可以根據(jù)這些信息來繼續(xù)完成

原來函數(shù)未執(zhí)行完畢的那部分代碼。

2 和 3 中解釋的原理 就是系統(tǒng)棧最神奇的地方

在編程的時候進行子過程調(diào)用的時候，

當(dāng)一個子過程執(zhí)行完成之后，

可以自動的回到上層調(diào)用中斷的位置，

并且繼續(xù)執(zhí)行下去。

都是靠一個系統(tǒng)棧來記錄每一次調(diào)用過程中

中斷的那個調(diào)用的點來實現(xiàn)的。

棧雖然是一個非常簡單的數(shù)據(jù)結(jié)構(gòu)

但是它能夠解決計算機領(lǐng)域非常復(fù)雜的一個問題，

這個問題就是這種子過程子邏輯的調(diào)用，

在編譯器內(nèi)部它運行實現(xiàn)的原理是什么，

深入理解這個過程，

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

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

棧這種數(shù)據(jù)結(jié)構(gòu)非常有用

但其實是非常簡單的。

MyStack

void push(e)：入棧

E pop()：出棧

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

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

boolean isEmpty()：棧是否為空

從用戶的角度看

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

用戶不管你要怎樣 resize，

他只要知道你這個數(shù)組是一個動態(tài)的，

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

并且不會出現(xiàn)問題就 ok，

其實對于棧也是這樣的，

對于具體的底層實現(xiàn)，用戶不關(guān)心，

實際底層也有多種實現(xiàn)方式，

所以用戶就更加不關(guān)心了。

為了讓代碼更加的清晰，

同時也是為了支持面向?qū)ο蟮囊恍┨匦裕?/p>

比如說支持多態(tài)性，

那么就會這樣的去設(shè)計，

定義一個接口叫做 IMyStack，

接口中有棧默認(rèn)的所有方法，

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

讓它去實現(xiàn) IMyStack，

這樣就可以在 MyStack 中完成對應(yīng)的邏輯，

這個 MyStack 就是自定義的棧。

會復(fù)用到之前自定義數(shù)組對象。

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 查看棧頂?shù)脑?         */
        E peek();

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

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

3. MyArray

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

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

        // 無參數(shù)的構(gòu)造函數(shù)，默認(rèn)數(shù)組的容量capacity=10
        public MyArray () {
  //        this( capacity: 10);
              this(10);
        }

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

        // 獲取數(shù)組的總?cè)萘?        public int getCapacity () {
              return data.length;
        }

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

        // 重新給數(shù)組擴容
        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;
        }

        // 給數(shù)組添加一個新元素
        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) {

              // 復(fù)用插入元素的方法
              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];
        }

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

        // 獲取數(shù)組中最后一個元素（純查看）
        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;
        }

        // 查找數(shù)組中是否有元素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;
        }

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

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

        // 查找數(shù)組中所有元素e所在的索引，最后返回存放 所有索引值的 自定義數(shù)組
        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;
        }

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

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

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

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

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

        // 從數(shù)組中刪除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;

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

              return temp;
        }

        @Override
        // @Override: 方法名 日期-開發(fā)人員
        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 {
        // 借用自定義個動態(tài)數(shù)組
        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 查看棧頂?shù)脑?         */
        @Override
        public E peek() {
              return ma.getLast();
        }

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

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

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

        @Override
        // @Override: 方法名 日期-開發(fā)人員
        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);
              }
        }
  }

## 棧的應(yīng)用

1. undo 操作-編輯器
2. 系統(tǒng)調(diào)用棧-操作系統(tǒng)
3. 括號匹配-編譯器

### 以編程的方式體現(xiàn)棧的應(yīng)用

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

1. 如：`{ [ ( ) ] }`，
2. 從左往右，先將左側(cè)的括號入棧，
3. 然后遇到右側(cè)的括號時就查看棧頂?shù)淖髠?cè)括號進行匹配，
4. 如果可以匹配表示括號有效，否則括號無效，
5. 括號有效那么就將棧頂?shù)淖髠?cè)括號取出，
6. 然后繼續(xù)從左往右，左側(cè)括號就入棧，右側(cè)括號就匹配，
7. 匹配成功就讓左側(cè)括號出棧，匹配失敗就是無效括號。
8. 其實棧頂元素反映了在嵌套的層級關(guān)系中，
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 是一個非常好的準(zhǔn)備面試的一個平臺
1. 同時它也是算法競賽的一個入門的地方。
2. 你可以通過題庫來進行訓(xùn)練，
3. 題庫的右邊有關(guān)于這些題目的標(biāo)簽，
4. 你可以選擇性的去練習(xí)，
5. 而且可以根據(jù)難度來進行排序這些題目，
6. 你不一定要全部答對，
7. 因為這些題目不僅僅只有一個標(biāo)簽。
7. 如果你想使用你自己寫的類，
1. 那么你可以你自己寫的自定義棧作為內(nèi)部類來進行使用，
2. 例如 把自定義棧的代碼放到 Solution 類中，
3. 那樣也是可以使用，
4. 還樣就順便測試了你自己數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的邏輯是否正確。

### 學(xué)習(xí)方法討論

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

## 隊列 Queue

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

### 隊列的實現(xiàn)

1. `Queue`
1. `void enqueue(E)`：入隊
2. `E dequeue()`：出隊
3. `E getFront()`：查看隊首的元素
4. `int getSize()`：獲取隊列中的實際元素大小
5. `boolean isEmpty()`：獲取隊列是否為空的 bool 值
2. 寫一個接口叫做 IMyQueue
1. 讓 MyQueue 實現(xiàn)這個接口
2. 這樣就符合了面向?qū)ο蟮奶匦浴?
### 代碼示例

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
         *  獲取隊列中的實際元素個數(shù)
         */
        int getSize ();

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

3. MyArray

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

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

        // 無參數(shù)的構(gòu)造函數(shù)，默認(rèn)數(shù)組的容量capacity=10
        public MyArray () {
  //        this( capacity: 10);
              this(10);
        }

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

        // 獲取數(shù)組的總?cè)萘?        public int getCapacity () {
              return data.length;
        }

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

        // 重新給數(shù)組擴容
        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;
        }

        // 給數(shù)組添加一個新元素
        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) {

              // 復(fù)用插入元素的方法
              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];
        }

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

        // 獲取數(shù)組中最后一個元素（純查看）
        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;
        }

        // 查找數(shù)組中是否有元素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;
        }

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

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

        // 查找數(shù)組中所有元素e所在的索引，最后返回存放 所有索引值的 自定義數(shù)組
        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;
        }

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

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

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

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

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

        // 從數(shù)組中刪除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;

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

              return temp;
        }

        @Override
        // @Override: 方法名 日期-開發(fā)人員
        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
         *  獲取隊列中的實際元素個數(shù)
         */
        @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();
              }
        }
  }

### 隊列的復(fù)雜度分析

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. 如果有一百萬條數(shù)據(jù)，每次都要操作一百萬次，
2. 那么需要優(yōu)化它，要讓他出隊的時候時間復(fù)雜度為`O(1)`，
3. 并且還要讓他入隊的時候時間復(fù)雜度依然是`O(1)`。
4. 可以使用循環(huán)隊列的方式來解決這個問題。

## 循環(huán)隊列

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

### 循環(huán)隊列的簡單實現(xiàn)解析

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

## 循環(huán)隊列的實現(xiàn)

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

### 代碼示例 `(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) {
              // 這個數(shù)組的容量為 傳進來的指定容量+1，
              // 因為會有意識的浪費一個空間，只有+1后，
              // 才能裝下用戶期望傳進來的所有數(shù)據(jù)
              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在隊列中循環(huán)
              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
         * 獲取隊列中的實際元素個數(shù)
         */
        @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. 原來自定隊列的出隊時，時間復(fù)雜度為`O(n)`，
1. 使用循環(huán)隊列的方式后，
2. 出隊時時間復(fù)雜度為`O(1)`，
3. 復(fù)雜度的分析只是一個抽象上的理論結(jié)果，
4. 具體這個變化在性能上意味著會有一個質(zhì)的飛躍，
5. 隊列中元素越多，性能就更能夠體現(xiàn)出來。

### 自定義隊列的時間復(fù)雜度對比

1. `MyQueue`：數(shù)組隊列，使用了自定義數(shù)組
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`：循環(huán)隊列，沒有使用自定義數(shù)組
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)`

### 循環(huán)隊列的復(fù)雜度分析

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

### 隊列的應(yīng)用

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