前言
在前兩篇文章中，給大家介紹了線性資料結構中的連結清單。除了連結清單這種結構之外，實際上還有棧、隊列、串等結構，那麼這些結構又有哪些特點呢？大家快來看看今天的内容吧。
全文大約【3900】字，不說廢話，隻講可以讓你學到技術、明白原理的純幹貨！本文帶有豐富的案例及配圖視訊，讓你更好地了解和運用文中的技術概念，并可以給你帶來具有足夠啟迪的思考......
一. 棧
1. 棧的概念
棧(stack)是一種操作受限的線性表，棧的操作被限定線上性表的尾部進行，棧結構有兩個特殊概念：
- 棧頂：棧的尾部被稱為棧頂(Top)；
- 棧底：另一端固定不動，被稱為棧底(Bottom)。
棧中的元素隻能先入後出。 最早進入棧的元素所在的位置是棧底，最後進入棧的元素所在的位置是棧頂。資料進入棧的過程叫入棧或壓棧，資料從棧中出去的過程叫出棧或彈棧。如下圖所示：
2. 棧的實作
在實作上，棧既可以用數組來實作，也可以用連結清單來實作。用數組實作的棧叫順序棧或靜态棧，用連結清單實作的棧叫做鍊式棧或動态棧，這兩種實作方式分别如下圖所示：
3. 棧的操作
剛剛給大家介紹了棧頂和棧底的概念，棧的操作就和這兩個概念有關。棧一般隻有兩個操作：入棧和出棧。
3.1 入棧
入棧操作就是把元素(資料)放入到棧中，入棧操作又稱壓棧，有時也稱之為push操作，均表示入棧操作含義。需要注意的是，根據棧結構的特點，入棧隻允許從棧頂放入元素，進入棧的新元素會在最上方，成為棧頂。
對于入棧操作的時間複雜度，因為隻涉及到一個元素的操作，是以非常簡單為O(1)。
3.2 出棧
出棧操作就是把元素（資料）從棧中取出，出棧操作又稱彈棧，有時也稱之為pop操作，均表示出棧操作含義。同樣需要注意，根據棧結構的特點，出棧隻需要從棧頂取出元素，元素出棧後，原次頂元素會成為新的棧頂元素。
出棧操作的時間複雜度與入棧操作的時間複雜度相同，均是操作棧頂一個元素，是以出棧操作時間複雜度為O(1)。
4. 棧的特點
如上圖所示，清晰的展示了棧的入棧操作和出棧操作。可以看到，無論入棧操作，還是出棧操作，都是操作的棧頂元素。由此，給大家總結棧結構的特點：後進先出，即後進入的元素會先出棧。在計算機術語中，後進先出描述為Last In First Out，簡稱LIFO；另外也有人表述為先進後出(Frist In Last Out，簡稱FILO)，這兩者含義其實是相同的。
5. 棧的應用
在實際的應用實踐中，我們可以利用棧結構的特殊性和其特點，解決某些特定的問題，此處給大家介紹常見的幾個。
5.1 子程式調用
程式在執行過程中，不免會涉及到調用。利用棧結構，可以在跳往子程式前，先将下個指令的位址存到堆棧中，直到子程式執行完後再将位址取出，以便回到原來的程式中。
5.2 浏覽器前進和後退
我們使用兩個棧X和Y，把首次浏覽的頁面依次壓入棧X，當單擊後退按鈕時，再依次從棧X中出棧，并将出棧的資料依次放入棧Y。當單擊前進按鈕時，我們依次從棧Y中取出資料， 放入棧X中。當棧X中沒有資料時，說明沒有頁面可以繼續後退浏覽了。當棧Y中沒有資料，那就說明沒有頁面可以單擊前進按鈕浏覽了。
5.3 表達式求值
首先大家要知道什麼是表達式，以及有哪些表達式，才能進一步學習如何進行表達式求值。根據百科的定義：表達式是由數字、算符、數字分組符号(括号)、自由變量和限制變量等以能求得數值的有意義排列方法所得的組合。聽起來非常的抽閑和不好了解，我們可以簡單地說：由一個或多個操作數通過操作符組合而成的式子就是表達式。比如：3+5、a-b、c==d等這些都是表達式，在這三個表達式中，均包含兩個操作數和一個操作符。程式設計中常見和使用的表達式有：算術表達式、邏輯表達式、字元串表達式等。
表達式按照操作數和操作符順序的不同，又可以分為三種為：中綴表達式、字首表達式、字尾表達式。
- 中綴表達式：中綴表達式是一個通用的算術或邏輯公式表示方法，我們從國小就接觸的算術表達式就是中綴表達式的寫法。比如a + b 就預設是中綴表達式。中綴表達式對大家來說很熟悉，但是對計算機來說比較難計算。因為要比較運算符的優先級，是以一般将中綴表達式轉化為字尾表達式再進行表達式的運算。
- 字首表達式：字首表達式是一種沒有括号的算術表達式，與中綴表達式不同的是，其将運算符寫在前面，操作數寫在後面。為紀念其發明者波蘭數學家盧卡西維茨(Jan Lukasiewicz)，字首表達式也稱為“波蘭表達式”。例如，- 1 + 2 3，它等價于1-(2+3)。
- 字尾表達式：字尾表達式将運算符寫在操作數之後。也叫做逆波蘭表達式(Reverse Polish notation，RPN，或逆波蘭記法)。
在本文中，我們以字尾表達式求值為例，向大家介紹如何利用棧結構計算表達式的值。
首先，我們需要學習字尾表達式運算求值的規則，其運算思路是：從左至右掃描字尾表達式，遇到數字時，将數字壓入棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做出相應的計算，并将結果入棧。重複上述過程，直到表達式的最右端。最後運算得出的值即為表達式的計算結果。
文字描述太過抽象，通過具體例子進行說明。例如：求字尾表達式3 4 + 5 * 6 -的值，步驟如下：
(1). 從左向右掃描表達式，首先遇到數字，将數字3和數字4壓棧。(此時棧中有2個元素為：3、4)
(2). 繼續向右掃描，遇到+運算符。彈出4和3(4為棧頂元素，3為次頂元素)，計算4+3=7，将結果7壓入棧中。(此時，棧中隻有1個元素：7)
(3). 向右繼續掃描，遇到數字5，将數字5壓入棧中。(此時，棧中包含2個元素：7、5)
(4). 向右掃描，遇到*号運算符，彈出棧頂元素5和次棧頂元素7，并計算7*5=35，将結果35壓入棧中。(此時，棧中隻有1個元素：35)
(5). 向右掃描，遇到數字6，将數字6壓入棧中。(此時，棧中包含2個元素：35，6)
(6). 向右掃描，遇到-運算符，彈出棧頂元素6和次棧頂元素35，并計算35-6=29，将數字29壓入棧中。(此時，棧中隻有1個元素：29)
(7). 整個表達式掃描結束，取出棧中的元素29，就是最後表達式的結果。
二. 隊列
1. 隊列的概念
隊列(Queue)也是一種操作受限的線性表，是先進先出的線性表。隊列的出口端叫作隊頭(front)，隊列的入口端叫作隊尾(rear)。隊列隻允許在隊尾進行添加操作，在隊頭進行删除操作。隊列的操作方式和棧類似，唯一的差別在于隊列隻允許新資料在隊尾進行添加，如下圖所示：
隊列是Java中常用的資料結構，隊列的存儲結構有兩種：一種是基于數組實作的；另一種是基于單連結清單實作的。
用數組實作隊列時，為了入隊操作的友善，把隊尾位置規定為最後入隊元素的下一個位置。 用數組實作的隊列叫作順序隊列。數組實作的隊列在建立的時候就已經确定了數組的長度，是以隊列的長度是固定的，但是可以循環使用數組，是以這種隊列也稱之為循環隊列。
用連結清單實作的隊列叫作鍊式隊列。連結清單實作的隊列内部通過指針指向形成一個隊列，這種隊列是單向的且長度不固定，是以也稱之為非循環隊列。
2. 隊列的特點
如上圖所示，所有的元素都是從隊尾進入隊列，若需要出隊，則從另外一端對頭取出元素。我們會發現，元素從隊列中出隊的順序剛好是元素進入隊列的順序。我們把這種進入和出來的順序相同的隊列的特點，稱之為先進先出(First In First Out，簡稱為FIFO)。
3. 隊列的操作
同棧類似，隊列也是一種操作受限，隊列有入隊和出隊兩種操作。接下來，我們詳細介紹：
3.1 入隊
入隊又稱enqueue，入隊就是把新元素放入隊列中，隻允許在隊尾的位置放入元素，新元素的下一個位置将會成為新的隊尾。添加資料時，首先判斷隊列的長度是否超出了數組的長度，如果超出則就添加失敗(也可以設定成等待，等隊列裡的資料出隊，然後再添加進去)。元素入隊完成後，隊列長度加一，rear指針也會相應自增一。如下圖所示：
3.2 出隊
出隊又稱dequeue，出隊就是把元素移出隊列，隻允許在隊頭一側移出元素，出隊元素的後一個元素将會成為新的隊頭。元素出隊後，隊列的長度減一，front指針自增一。如下圖所示：
4. 時間複雜度
無論是順序隊列還是鍊式隊列，入隊和出隊操作都隻涉及1個元素的操作，是以隊列操作的時間複雜度都是O(1)。隊列的主要應用于資源池、消息隊列、指令隊列等。
三. 串
1. 概念
我們通常将字元串簡稱為串，其是由零個或多個字元組成的有限序列。串可以是字母、數字或其他字元。串中的字元數目稱為串的長度，零個字元的串稱為空串，它的長度為0。
串中任意個連續字元組成的子序列稱為該串的子串，包含子串的串稱為主串。通常我們把字元在序列中的序号為該字元在串中的位置，子串在主串中的位置則以子串的第一個字元在主串中的位置來表示。當兩個串的長度相等，并且各個對應的字元都相等時，稱兩個串相等。由一個或多個空格組成的串稱為空格串。空格穿并非空串，它有長度，它的長度為串中空格符号的個數。
2. 串的特性
由此，我們可以得知串的幾個結論：
- 串是由零個或多個字元組成的有限序列；
- 串可以由字母、數字或其他字元組成；
- 串中的字元數目稱為串的長度；
- 零個字元的串稱為空串，它的長度為0；
- 串中任意個連續的字元組成的子序列，稱為該串的子串；
- 由一個或多個空格組成的串稱為空格串；
- 空格穿并非空串，它有長度，它的長度為串中空格符号的個數。
以上這些簡潔的結論，在面試題中可能會遇到，大家需要注意一下。關于串的其他操作，我們在後面學習算法時，會單獨組織一篇内容進行介紹，此處不再贅述。
四. 結語
本篇文章中，向大家介紹了棧、隊列和串三種新的線性資料結構。這三種資料結構相對數組和連結清單而言，操作比較簡單，也比較容易了解，各位在學習時需要記住這幾個不同資料結構特有的特點。在時間複雜度分析這個名額上，棧和隊列的操作均為O(1)。
更多技術類幹貨/IT程式員資訊，關注@千鋒教育