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

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

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

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

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

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

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

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

因?yàn)樗谋举|(zhì)就是一個(gè)數(shù)組，

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

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

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

添加元素的時(shí)候只能從棧的一端添加元素，

取出元素的時(shí)候也只能棧的一端取出元素，

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

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

它可以在計(jì)算機(jī)世界中對(duì)于

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

棧的操作

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

如添加值的時(shí)候?yàn)?1、2、3，

你取值的時(shí)候順序則為 3、2、1，

因?yàn)槟闾砑釉厥侵荒軓囊欢朔湃耄?/p>

取出元素時(shí)也只能從一端取出，

而這一段就是棧頂，

棧的出口和入口都是同一個(gè)位置，

所以你只能按照先進(jìn)后出、后進(jìn)先出的順序

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

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

也就是 Last In First Out(LIFO)，

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

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

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

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

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

編輯器的撤銷操作的原理就是靠一個(gè)棧來進(jìn)行維護(hù)的，

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

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

再撤銷一下 變成 我。

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

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

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

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

在這個(gè)過程中計(jì)算機(jī)就需要使用一個(gè)

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

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

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

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

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

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

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

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

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

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

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

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

A 函數(shù)執(zhí)行，在第二行中斷了，因?yàn)橐?zhí)行函數(shù) B 了，

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

然后 B 函數(shù)執(zhí)行，在第二行也中斷了，因?yàn)橐?zhí)行函數(shù) C 了，

這時(shí)候函數(shù)信息 B2 會(huì)被放入系統(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í)行完畢了，這時(shí)候會(huì)再從系統(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í)行時(shí)的一些信息，

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

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

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

在編程的時(shí)候進(jìn)行子過程調(diào)用的時(shí)候，

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

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

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

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

中斷的那個(gè)調(diào)用的點(diǎn)來實(shí)現(xiàn)的。

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

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

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

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

深入理解這個(gè)過程，

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

比如遞歸這樣的一個(gè)過程，你會(huì)有更加深刻的理解。

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

但其實(shí)是非常簡(jiǎn)單的。

MyStack

void push(e)：入棧

E pop()：出棧

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

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

boolean isEmpty()：棧是否為空

從用戶的角度看

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

用戶不管你要怎樣 resize，

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

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

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

其實(shí)對(duì)于棧也是這樣的，

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

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

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

為了讓代碼更加的清晰，

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

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

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

定義一個(gè)接口叫做 IMyStack，

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

然后再定義一個(gè)類叫做 MyStack，

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

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

這個(gè) MyStack 就是自定義的棧。

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

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í)際元素的個(gè)數(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í)際個(gè)數(shù)
        public int getSize () {
              return size;
        }

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

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

        // 重新給數(shù)組擴(kuò)容
        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ù)組添加一個(gè)新元素
        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++;
        }

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

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

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

              insert(0, e);
        }

        // 在index索引的位置插入一個(gè)新元素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ù)組中第一個(gè)元素（純查看）
        public E getFirst () {
              return get(0);
        }

        // 獲取數(shù)組中最后一個(gè)元素（純查看）
        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ù)組中刪除第一個(gè)元素, 返回刪除的元素
        public E removeFirst () {
              return remove(0);
        }

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

        // 從數(shù)組中刪除第一個(gè)元素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時(shí)，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 {
        // 借用自定義個(gè)動(dòng)態(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í)際元素的個(gè)數(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. 括號(hào)匹配-編譯器

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

1. 括號(hào)匹配-編譯器
1. 無論是寫表達(dá)式，這個(gè)表達(dá)式中有小括號(hào)、中括號(hào)、大括號(hào)，
2. 自然會(huì)出現(xiàn)括號(hào)套括號(hào)的情況發(fā)生，
3. 在這種情況下就一定會(huì)產(chǎn)生一個(gè)括號(hào)匹配的問題，
4. 如果括號(hào)匹配是不成功的，那么編譯器會(huì)進(jìn)行報(bào)錯(cuò)。
2. 編譯器是如何檢查括號(hào)匹配的問題？
1. 原理是使用了一個(gè)棧。
3. 可以通過解答 Leetcode 中的一個(gè)問題，
1. 同時(shí)來看棧在括號(hào)匹配這個(gè)問題中的應(yīng)用。
2. Leetcode 是總部在美國(guó)硅谷一家
3. 非常有年頭又同時(shí)有信譽(yù)度的面向 IT 公司
4. 面試這樣一個(gè)在線的平臺(tái)，
5. 只需要注冊(cè)一個(gè) Leetcode 用戶后，
6. 就可以看到 Leetcode 上有非常多的問題，
7. 對(duì)于每一個(gè)問題會(huì)規(guī)定輸入和輸出之后，
8. 然后就可以編寫屬于自己的邏輯，
9. 更重要的是可以直接把你編寫的這個(gè)程序
10.   提交給這個(gè)網(wǎng)站，
11.   這個(gè)網(wǎng)站會(huì)自動(dò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 中第二十號(hào)題目：有效的括號(hào)

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

  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 是一個(gè)非常好的準(zhǔn)備面試的一個(gè)平臺(tái)
1. 同時(shí)它也是算法競(jìng)賽的一個(gè)入門的地方。
2. 你可以通過題庫來進(jìn)行訓(xùn)練，
3. 題庫的右邊有關(guān)于這些題目的標(biāo)簽，
4. 你可以選擇性的去練習(xí)，
5. 而且可以根據(jù)難度來進(jìn)行排序這些題目，
6. 你不一定要全部答對(duì)，
7. 因?yàn)檫@些題目不僅僅只有一個(gè)標(biāo)簽。
7. 如果你想使用你自己寫的類，
1. 那么你可以你自己寫的自定義棧作為內(nèi)部類來進(jìn)行使用，
2. 例如 把自定義棧的代碼放到 Solution 類中，
3. 那樣也是可以使用，
4. 還樣就順便測(cè)試了你自己數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的邏輯是否正確。

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

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

## 隊(duì)列 Queue

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

### 隊(duì)列的實(shí)現(xiàn)

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

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

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

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

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

        /**
         * @return number
         *  獲取隊(duì)列中的實(shí)際元素個(gè)數(shù)
         */
        int getSize ();

        /**
         * @return bool
         *   獲取隊(duì)列是否為空的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í)際個(gè)數(shù)
        public int getSize () {
              return size;
        }

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

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

        // 重新給數(shù)組擴(kuò)容
        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ù)組添加一個(gè)新元素
        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++;
        }

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

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

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

              insert(0, e);
        }

        // 在index索引的位置插入一個(gè)新元素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ù)組中第一個(gè)元素（純查看）
        public E getFirst () {
              return get(0);
        }

        // 獲取數(shù)組中最后一個(gè)元素（純查看）
        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ù)組中刪除第一個(gè)元素, 返回刪除的元素
        public E removeFirst () {
              return remove(0);
        }

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

        // 從數(shù)組中刪除第一個(gè)元素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時(shí)，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
         *  入隊(duì)
         */
        @Override
        public void enqueue (E e) {
              ma.addLast(e);
        }

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

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

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

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

        // 獲取隊(duì)列容量
        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();
              }
        }
  }

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

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

## 循環(huán)隊(duì)列

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

### 循環(huán)隊(duì)列的簡(jiǎn)單實(shí)現(xiàn)解析

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

## 循環(huán)隊(duì)列的實(shí)現(xiàn)

1. 入隊(duì)前先判斷隊(duì)列是否已經(jīng)滿了
1. 判斷方式 `(tail + 1) % data.length == front`
2. 判斷分析 (隊(duì)尾指向的索引 + 1)余以數(shù)組的容量是否為隊(duì)首指向的索引，
2. 從用戶的角度上來看
1. 隊(duì)列里就是有這么多元素，
2. 一側(cè)是隊(duì)首一側(cè)是隊(duì)尾，
3. 其它的內(nèi)容包括實(shí)際的數(shù)組的大小是用戶指定的容量大小+1，
4. 這些實(shí)現(xiàn)細(xì)節(jié)，用戶是全部不知道的，給用戶屏蔽掉了，
5. 這就是封裝自定義數(shù)據(jù)結(jié)構(gòu)的目的所在，
6. 用戶在具體使用這些自定義數(shù)據(jù)結(jié)構(gòu)的時(shí)候，
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) {
              // 這個(gè)數(shù)組的容量為 傳進(jìn)來的指定容量+1，
              // 因?yàn)闀?huì)有意識(shí)的浪費(fèi)一個(gè)空間，只有+1后，
              // 才能裝下用戶期望傳進(jìn)來的所有數(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++) {
  //            索引可能會(huì)越界，于是就要取余一下，
  //            如果越界了，就從隊(duì)首開始
                    newData[i] = data[(front + i) % data.length];
              }
              data = newData;
              front = 0;
              tail = size;
        }

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

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

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

        /**
         * @return e
         * 出隊(duì)
         */
        @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
         * 查看隊(duì)首的元素
         */
        @Override
        public E getFront() {
              if (isEmpty()) {
                    throw new IllegalArgumentException("queue is empty.");
              }
              return data[front];
        }

        /**
         * @return number
         * 獲取隊(duì)列中的實(shí)際元素個(gè)數(shù)
         */
        @Override
        public int getSize() {
              return size;
        }

        /**
         * @return bool
         * 獲取隊(duì)列是否為空的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();
              }
        }
  }

## 自定義隊(duì)列兩種方式的對(duì)比

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

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

1. `MyQueue`：數(shù)組隊(duì)列，使用了自定義數(shù)組
1. `void enqueue(E)`：`O(1)` 均攤
2. `E dequeue()`：`O(n)` 出隊(duì)的性能消耗太大了
3. `E getFront()`：`O(1)`
4. `int getSize()`：`O(1)`
5. `boolean isEmpty()`：`O(1)`
2. `MyLoopQueue`：循環(huán)隊(duì)列，沒有使用自定義數(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)隊(duì)列的復(fù)雜度分析

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

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

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