[[379190]]

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

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

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

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

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

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

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

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

不同的是基于數(shù)組實(shí)現(xiàn)的棧消耗的內(nèi)存更少，因?yàn)樗恍枰~外保存指向的指針。

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

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

// 基于數(shù)組實(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ù)組元素，并且棧中元素個(gè)數(shù)count減一 val tmp = items[count - 1] --count return tmp }}

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

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

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

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

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

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

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

下面我們?cè)賮?lái)分析一下基于數(shù)組擴(kuò)容的棧的時(shí)間復(fù)雜度。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

/** * O(n) */fun calculate(s: String): Int { val numberStack = Stack() var sign = 1 // 符號(hào)位 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)前符號(hào)位加入棧中 numberStack.push(sign) sign = 1 } ')' -> { // 取出之前保留的符號(hào)位與結(jié)果，與當(dāng)前結(jié)果做加法運(yùn)算 result = numberStack.pop() * result + numberStack.pop() } ' ' -> { } else -> { // 計(jì)算出當(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ù)字帶上之前的符號(hào)位，再與之前的結(jié)果做加法運(yùn)算 result += cur * sign } } index++ } return result}

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

比較含退格的字符串

棒球比賽

下一個(gè)更大元素

有效的括號(hào)

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

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