什么是棧，棧存儲結(jié)構(gòu)詳情

同順序表和鏈表一樣，棧也是用來存儲邏輯關(guān)系為一對一數(shù)據(jù)的線性存儲結(jié)構(gòu)，如圖所示:

從圖1我們看到，棧存儲結(jié)構(gòu)與之前學(xué)的線性存儲有所差異，這源于棧對數(shù)存和取的過程有特殊的要求:

棧只能從表的一端存取數(shù)據(jù)，另一端是封閉的

在棧中，無論是存儲數(shù)據(jù)還是取數(shù)據(jù)，都必須遵循先進(jìn)先出的原則，即最先進(jìn)棧的元素最后出棧。從圖1棧來說，從圖中數(shù)據(jù)的存儲狀態(tài)可判斷出，元素1是最先進(jìn)的棧。因此，當(dāng)需要從棧中取出元素1的時(shí)候，根據(jù)先進(jìn)后出原則，需提前將元素3和元素2從棧中取出，然后才能成功取出元素1.

因此我們可以給棧下一個定義，即 棧是一種只能從表的一端取數(shù)據(jù)且遵循先進(jìn)先出原則的線性存儲結(jié)構(gòu)。

通常，棧的開口端被稱為棧頂；相應(yīng)的，封口段被稱為棧低。

進(jìn)棧和出棧

基于棧結(jié)構(gòu)的特點(diǎn)，在實(shí)際應(yīng)用中，通常只會對棧執(zhí)行一下兩種操作:

• 向棧中添加元素，此過程被稱為進(jìn)棧(入棧或壓棧)
• 從棧中提取指定元素，此過程被稱為出棧(或彈棧)

棧的具體實(shí)現(xiàn)

棧是一種特殊的線性存儲結(jié)構(gòu)，因此棧的具體實(shí)現(xiàn)有以下兩種方式:

順序棧: 采用順序存儲結(jié)構(gòu)可以模擬棧存儲數(shù)據(jù)的特點(diǎn)，從而實(shí)現(xiàn)棧存儲結(jié)構(gòu)

鏈棧: 采用鏈表存儲結(jié)構(gòu)實(shí)現(xiàn)棧結(jié)構(gòu)

兩種實(shí)現(xiàn)方式的區(qū)別，僅限于數(shù)據(jù)元素在實(shí)際物理空間上存放的相對位置，順序棧底層采用的是數(shù)組，鏈棧底層采用的是鏈表。

棧的應(yīng)用

基于棧結(jié)構(gòu)對數(shù)據(jù)存取采用 “先進(jìn)后出” 原則的特點(diǎn)，它可以用于實(shí)現(xiàn)很多功能。

例如，我們經(jīng)常使用瀏覽器在各種網(wǎng)站上查找信息。假設(shè)先瀏覽的頁面 A，然后關(guān)閉了頁面 A 跳轉(zhuǎn)到頁面 B，隨后又關(guān)閉頁面 B 跳轉(zhuǎn)到了頁面 C。而此時(shí)，我們?nèi)绻胫匦禄氐巾撁?A，有兩個選擇：
重新搜索找到頁面 A；
使用瀏覽器的"回退"功能。瀏覽器會先回退到頁面 B，而后再回退到頁面 A。

瀏覽器 “回退” 功能的實(shí)現(xiàn)，底層使用的就是棧存儲結(jié)構(gòu)。當(dāng)你關(guān)閉頁面 A 時(shí)，瀏覽器會將頁面 A 入棧；同樣，當(dāng)你關(guān)閉頁面 B 時(shí)，瀏覽器也會將 B入棧。因此，當(dāng)你執(zhí)行回退操作時(shí)，才會首先看到的是頁面 B，然后是頁面 A，這是棧中數(shù)據(jù)依次出棧的效果。

不僅如此，棧存儲結(jié)構(gòu)還可以幫我們檢測代碼中的括號匹配問題。多數(shù)編程語言都會用到括號（小括號、中括號和大括號），括號的錯誤使用（通常是丟右括號）會導(dǎo)致程序編譯錯誤，而很多開發(fā)工具中都有檢測代碼是否有編輯錯誤的功能，其中就包含檢測代碼中的括號匹配問題，此功能的底層實(shí)現(xiàn)使用的就是棧結(jié)構(gòu)。

同時(shí)，棧結(jié)構(gòu)還可以實(shí)現(xiàn)數(shù)值的進(jìn)制轉(zhuǎn)換功能。例如，編寫程序?qū)崿F(xiàn)從十進(jìn)制數(shù)自動轉(zhuǎn)換成二進(jìn)制數(shù)，就可以使用棧存儲結(jié)構(gòu)來實(shí)現(xiàn)。

以上也僅是棧應(yīng)用領(lǐng)域的冰山一角。

總結(jié)

以上是生活随笔為你收集整理的什么是栈，栈存储结构详情的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。