一. 棧

1. 棧的概念

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

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

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

2. 棧的實(shí)現(xiàn)

在實(shí)現(xiàn)上，棧既可以用數(shù)組來(lái)實(shí)現(xiàn)，也可以用鏈表來(lái)實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)的棧叫順序棧或靜態(tài)棧，用鏈表實(shí)現(xiàn)的棧叫做鏈?zhǔn)綏；騽?dòng)態(tài)棧，這兩種實(shí)現(xiàn)方式分別如下圖所示：

3. 棧的操作

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

3.1 入棧

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

對(duì)于入棧操作的時(shí)間復(fù)雜度，因?yàn)橹簧婕暗揭粋€(gè)元素的操作，因此非常簡(jiǎn)單為O(1)。

3.2 出棧

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

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

4. 棧的特點(diǎn)

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

5. 棧的應(yīng)用

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

5.1 子程序調(diào)用

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

5.2 瀏覽器前進(jìn)和后退

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

5.3 表達(dá)式求值

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

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

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

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

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

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

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

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

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

(4). 向右掃描，遇到號(hào)運(yùn)算符，彈出棧頂元素5和次棧頂元素7，并計(jì)算75=35，將結(jié)果35壓入棧中。(此時(shí)，棧中只有1個(gè)元素：35)

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

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

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

二. 隊(duì)列

1. 隊(duì)列的概念

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

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

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

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

2. 隊(duì)列的特點(diǎn)

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

3. 隊(duì)列的操作

同棧類似，隊(duì)列也是一種操作受限，隊(duì)列有入隊(duì)和出隊(duì)兩種操作。接下來(lái)，我們?cè)敿?xì)介紹：

3.1 入隊(duì)

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

3.2 出隊(duì)

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

4. 時(shí)間復(fù)雜度

無(wú)論是順序隊(duì)列還是鏈?zhǔn)疥?duì)列，入隊(duì)和出隊(duì)操作都只涉及1個(gè)元素的操作，因此隊(duì)列操作的時(shí)間復(fù)雜度都是O(1)。隊(duì)列的主要應(yīng)用于資源池、消息隊(duì)列、命令隊(duì)列等。

三. 串

1. 概念

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

串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串稱為主串。通常我們把字符在序列中的序號(hào)為該字符在串中的位置，子串在主串中的位置則以子串的第一個(gè)字符在主串中的位置來(lái)表示。當(dāng)兩個(gè)串的長(zhǎng)度相等，并且各個(gè)對(duì)應(yīng)的字符都相等時(shí)，稱兩個(gè)串相等。由一個(gè)或多個(gè)空格組成的串稱為空格串。空格穿并非空串，它有長(zhǎng)度，它的長(zhǎng)度為串中空格符號(hào)的個(gè)數(shù)。

2. 串的特性

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

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

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

四. 結(jié)語(yǔ)

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

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

最新評(píng)論