[[379190]]

本質(zhì)棧是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它特殊在它的結(jié)構(gòu)，與數(shù)組、鏈表不同的是，它的數(shù)據(jù)出入規(guī)則是：先進(jìn)后出，后進(jìn)先出。

由于它這種特殊的特性，它一般用于指定的場景之下，例如：瀏覽器的前進(jìn)與回退效果。

瀏覽器的特性是：我們可以向前訪問我們之前訪問的網(wǎng)站，也可以向后訪問后面的網(wǎng)站。

瀏覽器的這種特性，完美匹配了棧的結(jié)構(gòu)。

我們只需使用兩個棧，分別代表瀏覽器的向前訪問與向后訪問。

當(dāng)某個數(shù)據(jù)集合只涉及在一端插入和刪除數(shù)據(jù)，并且滿足先進(jìn)后出，后進(jìn)先出的特性，這時我們應(yīng)該首先想到的是棧，看它是否能夠更好的實現(xiàn)我們所需的場景。

實現(xiàn)方式棧的實現(xiàn)方式有兩種，一種是基于數(shù)組的實現(xiàn)方式，稱為順序棧;另一種是基于鏈表的實現(xiàn)方式，稱為鏈?zhǔn)綏！?/p>

這兩種實現(xiàn)方式區(qū)別不是很多，實現(xiàn)之后棧的出入時間復(fù)雜度都是O(1)。

不同的是基于數(shù)組實現(xiàn)的棧消耗的內(nèi)存更少，因為它不需要額外保存指向的指針。

但基于數(shù)組的另外一額外需要做的是，如果需要實現(xiàn)不定大小的棧，它需要實現(xiàn)動態(tài)擴(kuò)容，這是所有基于數(shù)組實現(xiàn)的一個必修課。

下面我們來實現(xiàn)一個基于數(shù)組的順序棧，為了減少復(fù)雜度，不考慮擴(kuò)容的情況。

// 基于數(shù)組實現(xiàn)的順序棧class ArrayStack(private val n: Int) { private val items = arrayOfNulls(n) // 棧數(shù)組 private var count = 0 // 棧的當(dāng)前大小 // 入棧 fun push(item: String): Boolean { // 數(shù)組空間不夠了，直接返回false，入棧失敗 if (count == n) return false // 將item放到下標(biāo)為count的位置，并且count加一 items[count] = item ++count return true } // 出棧 fun pop(): String? { // 棧為空，則直接返回null if (count == 0) return null // 返回下標(biāo)為count-1的數(shù)組元素，并且棧中元素個數(shù)count減一 val tmp = items[count - 1] --count return tmp }}

基于上面的實現(xiàn)，我們能夠很容易得出棧的出入時間復(fù)雜度為O(1)。

另一方面，由于沒有額外的空間申請，所以棧的空間復(fù)雜度為O(1)。

擴(kuò)容上面我們實現(xiàn)的是一個固定的順序棧，也就是說初始化的時候已經(jīng)指定了棧的大小，當(dāng)棧滿了的時候，無法進(jìn)行向棧中添加數(shù)據(jù)。當(dāng)然基于鏈表的鏈?zhǔn)綏]有這種限制。

為了解決順序棧的這種限制，我們需要對數(shù)據(jù)進(jìn)行擴(kuò)容操作，這在數(shù)組那一節(jié)也有提及過。

所以，如果要實現(xiàn)一個支持?jǐn)U容的棧，我們只需底層依賴一個基于擴(kuò)容的數(shù)組即可。

具體的擴(kuò)容示意圖如下：

具體代碼實現(xiàn)可以查看數(shù)據(jù)的擴(kuò)容。

下面我們再來分析一下基于數(shù)組擴(kuò)容的棧的時間復(fù)雜度。

首先未達(dá)到棧的大小時，這一階段與固定的順序棧一樣，出入的時間復(fù)雜度都為O(1)。

當(dāng)數(shù)據(jù)為K時且達(dá)到擴(kuò)容的臨界點時，需要將數(shù)組的大小擴(kuò)大到原來的兩倍，并將之前的數(shù)據(jù)拷貝的新的數(shù)組中;這一階段消耗的時間復(fù)雜度為O(K)。

當(dāng)擴(kuò)容結(jié)束之后繼續(xù)出入棧，此時的時間復(fù)雜度又為O(1)。

當(dāng)再一次達(dá)到2k時又需要再次擴(kuò)容，拷貝數(shù)據(jù)到新數(shù)組中，此時消耗的時間復(fù)雜度為O(2k)。

反復(fù)重復(fù)以上步驟。

這就是支持?jǐn)U容的順序棧的時間復(fù)雜度的變化。也就是說最好情況的時間復(fù)雜度為O(1);最壞的時間復(fù)雜度為O(n)。那么平均時間復(fù)雜度呢?

還記得在算法之旅:復(fù)雜度分析中提到的均攤時間復(fù)雜度嗎?

下面我們就利用均攤時間復(fù)雜度來分析它的平均時間復(fù)雜度。其實看一張圖就能夠明白均攤時間復(fù)雜度的算法。

每次我們都將擴(kuò)容的所消耗的時間都分?jǐn)偟街蟮娜霔Ｖ?。在分?jǐn)傊叭霔Ｐ枰粋€push的時間;分?jǐn)傊笕霔Ｔ趐ush的時間上再加上一個數(shù)據(jù)move的時間。push與move的時間復(fù)雜度都為O(1)。

所以均攤之后棧的整個時間復(fù)雜度就是O(1)，即棧的平均復(fù)雜度為O(1)。

棧的應(yīng)用現(xiàn)在我們已經(jīng)對棧有了一個全面的了解，為了完全鞏固棧這種數(shù)據(jù)結(jié)構(gòu)，我們剩下的就是練習(xí)以達(dá)到熟悉程度。

例如：實現(xiàn)一個基本的計算器來計算一個簡單的字符串表達(dá)式的值, 字符串表達(dá)式可以包含左括號(，右括號)，加號+，減號-，非負(fù)整數(shù)和空格。

基于表達(dá)式的運(yùn)算，非常符合棧這種結(jié)構(gòu)，我們可以使用棧來實現(xiàn)的。實現(xiàn)思路如下：

通過設(shè)定一個符號位將所有的運(yùn)算轉(zhuǎn)化成加法

遇到數(shù)字都帶上之前的符號位，再與之前的結(jié)果做加法運(yùn)算

遇到'('將之前的符號位與結(jié)果保留到棧中，然后再重復(fù)1 2步驟計算括號里面的值

遇到')'取出之前保留的符號位與結(jié)果，與當(dāng)前結(jié)果做加法運(yùn)算

/** * O(n) */fun calculate(s: String): Int { val numberStack = Stack() var sign = 1 // 符號位 var result = 0 var index = 0 while (index < s.length) { when (s[index]) { '+' -> { sign = 1 } '-' -> { sign = -1 } '(' -> { // 將當(dāng)前結(jié)果加入棧中 numberStack.push(result) result = 0 // 將當(dāng)前符號位加入棧中 numberStack.push(sign) sign = 1 } ')' -> { // 取出之前保留的符號位與結(jié)果，與當(dāng)前結(jié)果做加法運(yùn)算 result = numberStack.pop() * result + numberStack.pop() } ' ' -> { } else -> { // 計算出當(dāng)前的數(shù)值，可以能為多位數(shù) var cur = s[index] - '0' while (index + 1 < s.length && s[index + 1].isDigit()) { cur = cur * 10 + (s[++index] - '0') } // 遇到數(shù)字帶上之前的符號位，再與之前的結(jié)果做加法運(yùn)算 result += cur * sign } } index++ } return result}

還有一些關(guān)于棧的經(jīng)典練習(xí)，如果能夠掌握這些，那么有關(guān)棧的算法就基本沒什么問題了

比較含退格的字符串

棒球比賽

下一個更大元素

有效的括號

我將源碼放在Github上了，如有需要的可以自行查看。

本文轉(zhuǎn)載自微信公眾號「 Android補(bǔ)給站」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系 Android補(bǔ)給站公眾號。