一. 棧

1. 棧的概念

棧 (stack) 是一種操作受限的線性表，棧的操作被限定在線性表的尾部進行，棧結(jié)構(gòu)有兩個特殊概念：

• 棧頂：棧的尾部被稱為棧頂(Top)；
• 棧底：另一端固定不動，被稱為棧底(Bottom)。

棧中的元素只能先入后出。 最早進入棧的元素所在的位置是棧底，最后進入棧的元素所在的位置是棧頂。數(shù)據(jù)進入棧的過程叫入棧或壓棧，數(shù)據(jù)從棧中出去的過程叫出棧或彈棧。 如下圖所示：

2. 棧的實現(xiàn)

在實現(xiàn)上，棧既可以用數(shù)組來實現(xiàn)，也可以用鏈表來實現(xiàn)。用數(shù)組實現(xiàn)的棧叫順序?；蜢o態(tài)棧，用鏈表實現(xiàn)的棧叫做鏈式棧或動態(tài)棧，這兩種實現(xiàn)方式分別如下圖所示：

3. 棧的操作

剛剛小編給大家介紹了棧頂和棧底的概念，棧的操作就和這兩個概念有關(guān)。棧一般只有兩個操作：入棧和出棧。

3.1 入棧

入棧操作就是把元素(數(shù)據(jù))放入到棧中，入棧操作又稱壓棧，有時也稱之為push操作，均表示入棧操作含義。需要注意的是，根據(jù)棧結(jié)構(gòu)的特點，入棧只允許從棧頂放入元素，進入棧的新元素會在最上方，成為棧頂。

對于入棧操作的時間復(fù)雜度，因為只涉及到一個元素的操作，因此非常簡單為O(1)。

3.2 出棧

出棧操作就是把元素（數(shù)據(jù)）從棧中取出，出棧操作又稱彈棧，有時也稱之為pop操作，均表示出棧操作含義。同樣需要注意，根據(jù)棧結(jié)構(gòu)的特點，出棧只需要從棧頂取出元素，元素出棧后，原次頂元素會成為新的棧頂元素。

出棧操作的時間復(fù)雜度與入棧操作的時間復(fù)雜度相同，均是操作棧頂一個元素，因此出棧操作時間復(fù)雜度為O(1)。

4. 棧的特點

如上圖所示，清晰的展示了棧的入棧操作和出棧操作?？梢钥吹?，無論入棧操作，還是出棧操作，都是操作的棧頂元素。由此，給大家總結(jié)棧結(jié)構(gòu)的特點：后進先出，即后進入的元素會先出棧。在計算機術(shù)語中，后進先出描述為Last In First Out，簡稱LIFO；另外也有人表述為先進后出(Frist In Last Out，簡稱FILO) ，這兩者含義其實是相同的。

5. 棧的應(yīng)用

在實際的應(yīng)用實踐中，我們可以利用棧結(jié)構(gòu)的特殊性和其特點，解決某些特定的問題，此處給大家介紹常見的幾個。

5.1 子程序調(diào)用

程序在執(zhí)行過程中，不免會涉及到調(diào)用。利用棧結(jié)構(gòu)，可以在跳往子程序前，先將下個指令的地址存到堆棧中，直到子程序執(zhí)行完后再將地址取出，以便回到原來的程序中。

5.2 瀏覽器前進和后退

我們使用兩個棧X和Y，把首次瀏覽的頁面依次壓入棧X，當(dāng)單擊后退按鈕時，再依次從棧X中出棧，并將出棧的數(shù)據(jù)依次放入棧Y。當(dāng)單擊前進按鈕時，我們依次從棧Y中取出數(shù)據(jù)， 放入棧X中。當(dāng)棧X中沒有數(shù)據(jù)時，說明沒有頁面可以繼續(xù)后退瀏覽了。當(dāng)棧Y中沒有數(shù)據(jù)，那就說明沒有頁面可以單擊前進按鈕瀏覽了。

5.3 表達式求值

首先大家要知道什么是表達式，以及有哪些表達式，才能進一步學(xué)習(xí)如何進行表達式求值。根據(jù)百科的定義：表達式是由數(shù)字、算符、數(shù)字分組符號(括號)、自由變量和約束變量等以能求得數(shù)值的有意義排列方法所得的組合。聽起來非常的抽閑和不好理解，我們可以簡單地說：由一個或多個操作數(shù)通過操作符組合而成的式子就是表達式。比如：3+5、a-b、c==d等這些都是表達式，在這三個表達式中，均包含兩個操作數(shù)和一個操作符。編程中常見和使用的表達式有：算術(shù)表達式、邏輯表達式、字符串表達式等。

表達式按照操作數(shù)和操作符順序的不同，又可以分為三種為：中綴表達式、前綴表達式、后綴表達式。

• 中綴表達式：中綴表達式是一個通用的算術(shù)或邏輯公式表示方法，我們從小學(xué)就接觸的算術(shù)表達式就是中綴表達式的寫法。比如a + b 就默認是中綴表達式。中綴表達式對大家來說很熟悉，但是對計算機來說比較難計算。因為要比較運算符的優(yōu)先級，所以一般將中綴表達式轉(zhuǎn)化為后綴表達式再進行表達式的運算。
• 前綴表達式：前綴表達式是一種沒有括號的算術(shù)表達式，與中綴表達式不同的是，其將運算符寫在前面，操作數(shù)寫在后面。為紀念其發(fā)明者波蘭數(shù)學(xué)家盧卡西維茨(Jan Lukasiewicz)，前綴表達式也稱為“波蘭表達式”。例如，- 1 + 2 3，它等價于1-(2+3)。
• 后綴表達式：后綴表達式將運算符寫在操作數(shù)之后。也叫做逆波蘭表達式(Reverse Polish notation，RPN，或逆波蘭記法)。

在本文中，我們以后綴表達式求值為例，向大家介紹如何利用棧結(jié)構(gòu)計算表達式的值。

首先，我們需要學(xué)習(xí)后綴表達式運算求值的規(guī)則，其運算思路是：從左至右掃描后綴表達式，遇到數(shù)字時，將數(shù)字壓入棧，遇到運算符時，彈出棧頂?shù)膬蓚€數(shù)，用運算符對它們做出相應(yīng)的計算，并將結(jié)果入棧。重復(fù)上述過程，直到表達式的最右端。最后運算得出的值即為表達式的計算結(jié)果。

文字描述太過抽象，通過具體例子進行說明。例如：求后綴表達式3 4 + 5 * 6 -的值，步驟如下：

(1). 從左向右掃描表達式，首先遇到數(shù)字，將數(shù)字3和數(shù)字4壓棧。(此時棧中有2個元素為：3、4)

(2). 繼續(xù)向右掃描，遇到+運算符。彈出4和3(4為棧頂元素，3為次頂元素)，計算4+3=7，將結(jié)果7壓入棧中。(此時，棧中只有1個元素：7)

(3). 向右繼續(xù)掃描，遇到數(shù)字5，將數(shù)字5壓入棧中。(此時，棧中包含2個元素：7、5)

(4). 向右掃描，遇到號運算符，彈出棧頂元素5和次棧頂元素7，并計算75=35，將結(jié)果35壓入棧中。(此時，棧中只有1個元素：35)

(5). 向右掃描，遇到數(shù)字6，將數(shù)字6壓入棧中。(此時，棧中包含2個元素：35，6)

(6). 向右掃描，遇到-運算符，彈出棧頂元素6和次棧頂元素35，并計算35-6=29，將數(shù)字29壓入棧中。(此時，棧中只有1個元素：29)

(7). 整個表達式掃描結(jié)束，取出棧中的元素29，就是最后表達式的結(jié)果。

二. 隊列

1. 隊列的概念

隊列 (Queue) 也是一種操作受限的線性表，是先進先出的線性表。隊列的出口端叫作隊頭(front)，隊列的入口端叫作隊尾(rear)。隊列只允許在隊尾進行添加操作，在隊頭進行刪除操作。隊列的操作方式和棧類似，唯一的區(qū)別在于隊列只允許新數(shù)據(jù)在隊尾進行添加，如下圖所示：

隊列是Java中常用的數(shù)據(jù)結(jié)構(gòu)，隊列的存儲結(jié)構(gòu)有兩種：一種是基于數(shù)組實現(xiàn)的；另一種是基于單鏈表實現(xiàn)的。

用數(shù)組實現(xiàn)隊列時，為了入隊操作的方便，把隊尾位置規(guī)定為最后入隊元素的下一個位置。 用數(shù)組實現(xiàn)的隊列叫作順序隊列。數(shù)組實現(xiàn)的隊列在創(chuàng)建的時候就已經(jīng)確定了數(shù)組的長度，所以隊列的長度是固定的，但是可以循環(huán)使用數(shù)組，所以這種隊列也稱之為循環(huán)隊列。

用鏈表實現(xiàn)的隊列叫作鏈式隊列。鏈表實現(xiàn)的隊列內(nèi)部通過指針指向形成一個隊列，這種隊列是單向的且長度不固定，所以也稱之為非循環(huán)隊列。

2. 隊列的特點

如上圖所示，所有的元素都是從隊尾進入隊列，若需要出隊，則從另外一端對頭取出元素。我們會發(fā)現(xiàn)，元素從隊列中出隊的順序剛好是元素進入隊列的順序。我們把這種進入和出來的順序相同的隊列的特點，稱之為先進先出(First In First Out，簡稱為FIFO) 。

3. 隊列的操作

同棧類似，隊列也是一種操作受限，隊列有入隊和出隊兩種操作。接下來，我們詳細介紹：

3.1 入隊

入隊又稱enqueue，入隊就是把新元素放入隊列中，只允許在隊尾的位置放入元素，新元素的下一個位置將會成為新的隊尾。添加數(shù)據(jù)時，首先判斷隊列的長度是否超出了數(shù)組的長度，如果超出則就添加失敗(也可以設(shè)置成等待，等隊列里的數(shù)據(jù)出隊，然后再添加進去)。元素入隊完成后，隊列長度加一，rear指針也會相應(yīng)自增一。如下圖所示：

3.2 出隊

出隊又稱dequeue，出隊就是把元素移出隊列，只允許在隊頭一側(cè)移出元素，出隊元素的后一個元素將會成為新的隊頭。元素出隊后，隊列的長度減一，front指針自增一。如下圖所示：

4. 時間復(fù)雜度

無論是順序隊列還是鏈式隊列，入隊和出隊操作都只涉及1個元素的操作，因此隊列操作的時間復(fù)雜度都是O(1)。隊列的主要應(yīng)用于資源池、消息隊列、命令隊列等。

三. 串

1. 概念

我們通常將字符串簡稱為串，其是由零個或多個字符組成的有限序列。串可以是字母、數(shù)字或其他字符。串中的字符數(shù)目稱為串的長度，零個字符的串稱為空串，它的長度為0。

串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串稱為主串。通常我們把字符在序列中的序號為該字符在串中的位置，子串在主串中的位置則以子串的第一個字符在主串中的位置來表示。當(dāng)兩個串的長度相等，并且各個對應(yīng)的字符都相等時，稱兩個串相等。由一個或多個空格組成的串稱為空格串?？崭翊┎⒎强沾虚L度，它的長度為串中空格符號的個數(shù)。

2. 串的特性

由此，我們可以得知串的幾個結(jié)論：

• 串是由零個或多個字符組成的有限序列；
• 串可以由字母、數(shù)字或其他字符組成；
• 串中的字符數(shù)目稱為串的長度；
• 零個字符的串稱為空串，它的長度為0；
• 串中任意個連續(xù)的字符組成的子序列，稱為該串的子串；
• 由一個或多個空格組成的串稱為空格串；
• 空格穿并非空串，它有長度，它的長度為串中空格符號的個數(shù)。

以上這些簡潔的結(jié)論，在面試題中可能會遇到，大家需要注意一下。關(guān)于串的其他操作，我們在后面學(xué)習(xí)算法時，會單獨組織一篇內(nèi)容進行介紹，此處不再贅述。

四. 結(jié)語

本篇文章中，向大家介紹了棧、隊列和串三種新的線性數(shù)據(jù)結(jié)構(gòu)。這三種數(shù)據(jù)結(jié)構(gòu)相對數(shù)組和鏈表而言，操作比較簡單，也比較容易理解，各位在學(xué)習(xí)時需要記住這幾個不同數(shù)據(jù)結(jié)構(gòu)特有的特點。在時間復(fù)雜度分析這個指標上，棧和隊列的操作均為O(1)。

以上就是Java線性結(jié)構(gòu)中棧、隊列和串的基本概念和特點詳解的詳細內(nèi)容，更多關(guān)于Java棧、隊列和串的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論