棧的應(yīng)用場景解析報告棧的應(yīng)用場景解析報告

一、引言

棧是一種重要的數(shù)據(jù)結(jié)構(gòu)，具有后進(jìn)先出（LIFO）的特性。它廣泛應(yīng)用于各種計(jì)算場景，從簡單的編程任務(wù)到復(fù)雜的系統(tǒng)設(shè)計(jì)。本報告將解析棧的主要應(yīng)用場景，并說明其優(yōu)勢及適用條件。通過具體案例，展示棧如何在不同領(lǐng)域發(fā)揮作用。

---

二、棧的基本特性與優(yōu)勢

（一）棧的定義與核心特性

1.后進(jìn)先出（LIFO）：棧中最后被添加的元素將是第一個被移除的元素。

2.操作受限：主要支持兩種操作——入棧（push）和出棧（pop）。

3.固定或動態(tài)大?。簵？梢允枪潭ù笮〉模ㄈ鐢?shù)組實(shí)現(xiàn)）或動態(tài)擴(kuò)展的（如鏈表實(shí)現(xiàn)）。

（二）棧的主要優(yōu)勢

1.高效性：入棧和出棧操作的時間復(fù)雜度為O(1)。

2.簡單性：實(shí)現(xiàn)邏輯清晰，易于理解和應(yīng)用。

3.靈活性：適用于多種需要逆序處理數(shù)據(jù)的場景。

---

三、棧的典型應(yīng)用場景

（一）表達(dá)式求值

1.中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式（逆波蘭表示法）

步驟：

(1)初始化一個空棧和輸出隊(duì)列。

(2)逐個讀取表達(dá)式中的符號：

-若為操作數(shù)，直接加入輸出隊(duì)列。

-若為運(yùn)算符，根據(jù)優(yōu)先級與棧頂元素比較：

-優(yōu)先級高或棧為空，入棧。

-優(yōu)先級低或相等，將棧頂元素彈出至輸出隊(duì)列，再入棧當(dāng)前符號。

(3)處理完所有符號后，將棧中剩余元素依次彈出至輸出隊(duì)列。

2.后綴表達(dá)式求值

步驟：

(1)初始化一個空棧。

(2)逐個讀取后綴表達(dá)式中的符號：

-若為操作數(shù)，入棧。

-若為運(yùn)算符，彈出棧頂兩個操作數(shù)進(jìn)行計(jì)算，將結(jié)果入棧。

(3)最終棧頂元素即為表達(dá)式結(jié)果。

---

（二）函數(shù)調(diào)用棧

1.調(diào)用棧的作用

-管理函數(shù)調(diào)用過程中的局部變量和返回地址。

-每次函數(shù)調(diào)用時，創(chuàng)建新的棧幀存儲信息。

-函數(shù)返回時，棧幀被彈出，恢復(fù)之前的調(diào)用狀態(tài)。

2.示例場景

-遞歸函數(shù)：如階乘計(jì)算、斐波那契數(shù)列。

-異常處理：記錄錯誤發(fā)生時的調(diào)用路徑。

---

（三）路徑回溯

1.游戲與搜索算法

-迷宮求解：使用棧記錄移動路徑，遇到死路時回溯。

-深度優(yōu)先搜索（DFS）：在圖遍歷中，棧用于存儲待訪問的節(jié)點(diǎn)。

步驟：

(1)將起始節(jié)點(diǎn)入棧。

(2)循環(huán)：

-若棧為空，結(jié)束。

-彈出棧頂節(jié)點(diǎn)，標(biāo)記為已訪問。

-將其未訪問的鄰接節(jié)點(diǎn)按順序入棧。

2.編輯器撤銷功能

-記錄用戶的操作歷史，撤銷時依次彈出棧頂操作。

---

（四）瀏覽器歷史記錄

1.前進(jìn)/后退功能實(shí)現(xiàn)

-使用兩個棧：

-歷史棧：記錄從首頁到當(dāng)前頁的路徑。

-未來?xiàng)＃河涗洀漠?dāng)前頁到已訪問過的頁面路徑。

操作邏輯：

(1)切換頁面時，將當(dāng)前頁面從歷史棧推入未來?xiàng)?，更新歷史棧頂。

(2)點(diǎn)擊“后退”時，彈出歷史棧頂至未來?xiàng)！?/p>

(3)點(diǎn)擊“前進(jìn)”時，彈出未來?xiàng)ｍ斨翚v史棧。

---

四、棧的實(shí)現(xiàn)方式

（一）基于數(shù)組的實(shí)現(xiàn)

優(yōu)點(diǎn)：

-訪問速度快（O(1)）。

-內(nèi)存連續(xù)，緩存友好。

缺點(diǎn)：

-固定大小限制（需預(yù)留空間）。

-擴(kuò)容時可能需要數(shù)組復(fù)制。

示例：

棧底-->[空,空,3,1,5]<--棧頂

top=2

（二）基于鏈表的實(shí)現(xiàn)

優(yōu)點(diǎn)：

-動態(tài)擴(kuò)展，按需分配。

-無需預(yù)分配空間。

缺點(diǎn)：

-鏈接指針增加內(nèi)存開銷。

-訪問速度受鏈表長度影響。

示例：

Node{value:5,next:Node{value:1,next:Node{value:3,next:None}}}

---

五、結(jié)論

棧作為一種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，在多個領(lǐng)域展現(xiàn)出重要價值。其簡潔高效的特性使其成為表達(dá)式求值、函數(shù)調(diào)用管理、路徑回溯等場景的理想選擇。根據(jù)實(shí)際需求，可以選擇合適的實(shí)現(xiàn)方式（數(shù)組或鏈表）以平衡性能與資源消耗。掌握棧的應(yīng)用原理，有助于提升算法設(shè)計(jì)和問題解決能力。

棧的應(yīng)用場景解析報告

一、引言

棧是一種重要的數(shù)據(jù)結(jié)構(gòu)，具有后進(jìn)先出（LIFO）的特性。它廣泛應(yīng)用于各種計(jì)算場景，從簡單的編程任務(wù)到復(fù)雜的系統(tǒng)設(shè)計(jì)。本報告將解析棧的主要應(yīng)用場景，并說明其優(yōu)勢及適用條件。通過具體案例，展示棧如何在不同領(lǐng)域發(fā)揮作用。

---

二、棧的基本特性與優(yōu)勢

（一）棧的定義與核心特性

1.后進(jìn)先出（LIFO）：棧中最后被添加的元素將是第一個被移除的元素。這一特性使得棧在處理需要逆序訪問或撤銷操作的數(shù)據(jù)時具有天然優(yōu)勢。例如，在瀏覽器歷史記錄中，最后訪問的頁面應(yīng)該是第一個可以“后退”的頁面。

2.操作受限：棧主要支持兩種基本操作：

入棧（Push）：將一個新元素添加到棧頂。如果棧已滿（在固定大小棧中），操作可能失敗或觸發(fā)溢出。

出棧（Pop）：移除并返回棧頂元素。如果棧為空，操作可能失敗或觸發(fā)下溢（Underflow）。

除了這兩種基本操作，有時也會提供：

查看棧頂（Peek或Top）：返回棧頂元素的值，但不移除它。

檢查?？眨↖sEmpty）：判斷棧是否為空。

檢查棧滿（IsFull）：判斷棧是否已達(dá)到容量上限（僅限固定大小棧）。

3.固定或動態(tài)大小：棧的實(shí)現(xiàn)可以基于固定大小的數(shù)組，也可以基于鏈表。固定大小棧在內(nèi)存使用上更簡單，但可能需要預(yù)留空間或限制棧的最大容量；動態(tài)大小棧（如鏈?zhǔn)綏＃┛梢愿鶕?jù)需要擴(kuò)展，更靈活，但通常需要額外的內(nèi)存開銷（如指針）。

（二）棧的主要優(yōu)勢

1.高效性：入棧和出棧操作的時間復(fù)雜度均為O(1)，即常數(shù)時間。這是因?yàn)闊o論是基于數(shù)組的順序棧還是基于鏈表的鏈?zhǔn)綏?，訪問棧頂元素的操作都非常直接和快速。這使得棧非常適合需要頻繁進(jìn)行元素添加和移除的場景。

2.簡單性：棧的操作接口簡單，只有幾個核心方法。其邏輯清晰，易于理解和實(shí)現(xiàn)，降低了編程復(fù)雜度。對于初學(xué)者來說，棧是一個很好的數(shù)據(jù)結(jié)構(gòu)入門概念。

3.靈活性：棧的LIFO特性使其能夠適應(yīng)多種需要逆序處理或依賴最近操作的場景。它可以作為一種“臨時存儲”或“狀態(tài)管理”的工具，在算法和系統(tǒng)中扮演輔助角色。

---

三、棧的典型應(yīng)用場景

（一）表達(dá)式求值

1.中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式（逆波蘭表示法）

中綴表達(dá)式（如`3+42/(1-5)`）的運(yùn)算符位于操作數(shù)之間，而計(jì)算機(jī)底層（如堆棧處理器）通常更適合處理后綴表達(dá)式（如`34215-/`）。轉(zhuǎn)換過程利用棧來暫存運(yùn)算符，并根據(jù)優(yōu)先級規(guī)則進(jìn)行排列。

轉(zhuǎn)換步驟（艾茲恩公式-ShuntingYardAlgorithm）：

(1)初始化：創(chuàng)建一個空棧用于存儲運(yùn)算符（稱為`operator_stack`），創(chuàng)建一個空列表或隊(duì)列用于存儲輸出（稱為`output_queue`）。

(2)逐個掃描中綴表達(dá)式的符號（從左到右）：

遇到操作數(shù)：

-直接將操作數(shù)添加到`output_queue`的末尾。

遇到運(yùn)算符（如+,-,,/,^）：

-若`operator_stack`為空：將當(dāng)前運(yùn)算符直接入棧。

-若`operator_stack`不為空：

-比較當(dāng)前運(yùn)算符與棧頂運(yùn)算符的優(yōu)先級：

當(dāng)前運(yùn)算符優(yōu)先級>棧頂運(yùn)算符優(yōu)先級：將當(dāng)前運(yùn)算符入棧。

當(dāng)前運(yùn)算符優(yōu)先級<=棧頂運(yùn)算符優(yōu)先級：

-將棧頂運(yùn)算符彈出，并添加到`output_queue`。

-重復(fù)此步驟，直到棧為空或棧頂運(yùn)算符的優(yōu)先級低于當(dāng)前運(yùn)算符。

-將當(dāng)前運(yùn)算符入棧。

遇到左括號'('：

-將左括號入棧。它將作為后續(xù)運(yùn)算符的臨時分隔符。

遇到右括號')'：

-彈出`operator_stack`中的運(yùn)算符，并添加到`output_queue`，直到遇到左括號'('。

-彈出左括號，丟棄它。（注意：左括號不加入輸出隊(duì)列）

(3)處理剩余運(yùn)算符：

-當(dāng)掃描完所有符號后，如果`operator_stack`中還有運(yùn)算符，則依次彈出并添加到`output_queue`，直到棧為空。

(4)結(jié)果：`output_queue`中存儲的序列即為后綴表達(dá)式。

優(yōu)先級示例：

`^`(冪運(yùn)算)>``,`/`(乘除)>`+`,`-`(加減)

同級運(yùn)算符從左到右結(jié)合。

示例：轉(zhuǎn)換`A+BC`

-A:output_queue=[A]

-+:operator_stack=[+](棧為空)

-B:output_queue=[A,B]

-:operator_stack=[+,](棧頂+優(yōu)先級>=，彈出+)

output_queue=[A,B,+]

operator_stack=[]

:operator_stack=[](棧為空)

-C:output_queue=[A,B,+,C]

-結(jié)束：彈出,output_queue=[A,B,+,C,]

最終后綴表達(dá)式為：`AB+C`

2.后綴表達(dá)式求值

后綴表達(dá)式（或稱逆波蘭表示法）的求值過程同樣利用棧，步驟更直接。

求值步驟：

(1)初始化：創(chuàng)建一個空棧。

(2)逐個掃描后綴表達(dá)式的符號（從左到右）：

遇到操作數(shù)：

-將操作數(shù)轉(zhuǎn)換為數(shù)值類型，并壓入棧中。

遇到運(yùn)算符（如+,-,,/）：

-從棧中彈出兩個操作數(shù)（注意：先彈出的是右操作數(shù)，后彈出的是左操作數(shù)，因?yàn)闂Ｊ荓IFO）。

-對這兩個操作數(shù)執(zhí)行當(dāng)前運(yùn)算符指定的運(yùn)算。

-將運(yùn)算結(jié)果壓入棧中。

(3)結(jié)果：當(dāng)掃描完所有符號后，棧中剩下的唯一元素就是整個表達(dá)式的求值結(jié)果。

示例：求值`34+5`

-3:stack=[3]

-4:stack=[3,4]

-+:彈出4,彈出3,計(jì)算3+4=7,壓入7。stack=[7]

-5:stack=[7,5]

-:彈出5,彈出7,計(jì)算75=35,壓入35。stack=[35]

-結(jié)束：最終結(jié)果為35。

---

（二）函數(shù)調(diào)用棧

函數(shù)調(diào)用棧是程序運(yùn)行時管理函數(shù)調(diào)用的一種機(jī)制，其核心就是棧。每次函數(shù)被調(diào)用時，都會創(chuàng)建一個新的“棧幀”（StackFrame），用于存儲該函數(shù)的局部變量、參數(shù)、返回地址等信息。當(dāng)函數(shù)執(zhí)行完畢或發(fā)生異常返回時，其棧幀會被彈出，程序控制權(quán)返回到之前的調(diào)用點(diǎn)。

1.調(diào)用棧的作用

存儲局部變量和參數(shù)：每個函數(shù)調(diào)用都有自己的獨(dú)立作用域，棧幀用于隔離不同函數(shù)的變量空間。

保存返回地址：函數(shù)執(zhí)行完畢后，需要知道從哪里繼續(xù)執(zhí)行（即調(diào)用它的函數(shù)）。返回地址通常存儲在棧幀中，并且在函數(shù)返回時被使用。

支持遞歸調(diào)用：遞歸函數(shù)通過調(diào)用棧實(shí)現(xiàn)每一層調(diào)用的上下文保存。每一層遞歸都有自己的棧幀，互不干擾。如果沒有調(diào)用棧，遞歸將無法保存中間狀態(tài)。

異常處理：當(dāng)程序發(fā)生異常時，異常處理機(jī)制需要沿著調(diào)用棧向上查找合適的異常處理代碼塊，棧幀記錄了函數(shù)的調(diào)用鏈，是實(shí)現(xiàn)這一功能的基礎(chǔ)。

中斷處理：操作系統(tǒng)中的中斷（如I/O完成）也會使用棧來保存當(dāng)前任務(wù)的狀態(tài)，以便處理完中斷后能正確返回。

2.示例場景

遞歸函數(shù)：

階乘計(jì)算：`factorial(n)`調(diào)用`factorial(n-1)`。每次調(diào)用`factorial(n-1)`時，都會為它分配一個新的棧幀存儲變量`n-1`的值和返回地址。當(dāng)最內(nèi)層的調(diào)用（如`factorial(1)`)返回時，其棧幀被彈出，然后`factorial(2)`繼續(xù)執(zhí)行。

```偽代碼

factorial(n):

ifn==0:

return1

else:

result=nfactorial(n-1)//調(diào)用棧幀內(nèi)會保存n,result,以及返回到調(diào)用點(diǎn)的地址

returnresult

```

斐波那契數(shù)列：計(jì)算`fib(n)`需要遞歸計(jì)算`fib(n-1)`和`fib(n-2)`。每次遞歸調(diào)用都會在調(diào)用棧上添加新的棧幀。

```偽代碼

fib(n):

ifn<=1:

returnn

else:

fib_n_minus_1=fib(n-1)//棧幀內(nèi)保存n,fib_n_minus_1,fib_n_minus_2,返回地址

fib_n_minus_2=fib(n-2)

returnfib_n_minus_1+fib_n_minus_2

```

注意：遞歸深度過大會導(dǎo)致棧溢出。

異常處理：當(dāng)代碼拋出異常時，程序會檢查當(dāng)前棧幀及后續(xù)棧幀，尋找?guī)в邢鄳?yīng)異常處理代碼的`try`塊。找到后，程序會跳轉(zhuǎn)到該處理代碼執(zhí)行。棧幀記錄了調(diào)用鏈，是定位錯誤和恢復(fù)程序狀態(tài)的關(guān)鍵。

---

（三）路徑回溯

棧在需要探索可能路徑并能在死路盡頭回退的場景中非常有用。其LIFO特性天然適合模擬“走一步，看一步，如果走不通就退回上一步”的邏輯。

1.游戲與搜索算法

迷宮求解：

玩家或算法從迷宮入口開始移動，每次選擇一個未探索的相鄰方向前進(jìn)。將已探索的路徑或當(dāng)前位置標(biāo)記為“已訪問”。如果前進(jìn)后到達(dá)死胡同（即所有相鄰方向都已探索或被阻擋），則需要回退到上一個位置，嘗試其他未探索的方向。這個過程非常適合用棧來實(shí)現(xiàn)：

步驟：

(1)初始化一個空棧，將起點(diǎn)位置（如坐標(biāo)(0,0)）及其狀態(tài)（如“未訪問”）入棧。

(2)循環(huán)執(zhí)行直到棧為空：

如果棧為空，表示所有路徑都已探索完畢或迷宮無解（根據(jù)情況判斷）。

彈出棧頂元素，記為當(dāng)前位置(x,y)和其狀態(tài)。

如果該位置是迷宮出口，則找到解。

如果該位置是死胡同（所有相鄰方向均不可行或已訪問），則忽略或標(biāo)記為“死路”。

否則，將該位置的未訪問相鄰位置（假設(shè)為(nx,ny)）及其狀態(tài)（“未訪問”）入棧。

（可選）為了記錄完整路徑，可以在入棧時將父節(jié)點(diǎn)信息也存儲起來。

棧頂始終代表當(dāng)前正在探索或回溯的“前一步”。

深度優(yōu)先搜索（DFS）：

DFS是一種圖遍歷算法，它沿著一條路徑盡可能深入，直到無法繼續(xù)前進(jìn)，然后回溯到上一個節(jié)點(diǎn)，繼續(xù)探索其他路徑。這正是棧的用武之地：

步驟：

(1)選擇一個起始節(jié)點(diǎn)，將其入棧。

(2)循環(huán)執(zhí)行直到棧為空：

如果棧為空，表示所有可達(dá)節(jié)點(diǎn)都已訪問或圖不連通（根據(jù)情況判斷）。

彈出棧頂節(jié)點(diǎn)`u`，標(biāo)記為已訪問。

遍歷節(jié)點(diǎn)`u`的所有鄰接節(jié)點(diǎn)`v`：

如果節(jié)點(diǎn)`v`未被訪問，則將節(jié)點(diǎn)`v`及其狀態(tài)（“未訪問”）入棧。

（可選）為了記錄訪問順序或路徑，可以在入棧時記錄節(jié)點(diǎn)`u`作為`v`的父節(jié)點(diǎn)。

棧頂節(jié)點(diǎn)始終是當(dāng)前正在訪問或準(zhǔn)備訪問的節(jié)點(diǎn)。

2.編輯器撤銷功能

計(jì)算機(jī)的文本編輯器、繪圖軟件等常常提供“撤銷”（Undo）功能，允許用戶取消最近的操作。棧是實(shí)現(xiàn)這一功能的有效方式：

概念：用戶的每一步操作（如插入文本、刪除文本、修改格式）都可以被視為一個“命令”或“動作”。

實(shí)現(xiàn)：

維護(hù)一個“操作歷史棧”。每執(zhí)行一次操作，就將這個操作的描述（以及可能需要的數(shù)據(jù)，如被刪除的文本內(nèi)容、修改前的格式）作為一個新元素壓入棧頂。

當(dāng)用戶點(diǎn)擊“撤銷”按鈕時，從棧頂彈出最后一個操作記錄。

根據(jù)彈出的記錄，執(zhí)行相應(yīng)的“反向操作”（如恢復(fù)被刪除的文本、恢復(fù)原始格式）。

（可選）為了支持“重做”（Redo），可以維護(hù)一個獨(dú)立的“操作重做?！薄３蜂N操作后，可以將撤銷的命令記錄壓入重做棧。點(diǎn)擊“重做”時，則從重做棧彈出并執(zhí)行。

優(yōu)點(diǎn)：棧結(jié)構(gòu)簡單，能夠按操作發(fā)生的順序（后執(zhí)行的后撤銷）進(jìn)行管理。

---

（四）瀏覽器歷史記錄

現(xiàn)代網(wǎng)頁瀏覽器都提供了強(qiáng)大的歷史記錄功能，允許用戶瀏覽之前訪問過的網(wǎng)頁，并可以“后退”或“前進(jìn)”。

1.前進(jìn)/后退功能實(shí)現(xiàn)

瀏覽器通常使用兩個棧來管理用戶的瀏覽狀態(tài)：

歷史棧（BackStack）：存儲用戶從當(dāng)前頁面“后退”可以訪問的頁面記錄。當(dāng)用戶訪問一個新頁面時，當(dāng)前頁面記錄（通常是URL和頁面標(biāo)題）被推入歷史棧。

未來?xiàng)＃‵orwardStack）：存儲用戶從當(dāng)前頁面“前進(jìn)”可以訪問的頁面記錄。當(dāng)用戶執(zhí)行“后退”操作后，被彈出的頁面記錄會同時被推入未來?xiàng)?。?dāng)用戶執(zhí)行“前進(jìn)”操作時，頁面記錄會從未來?xiàng)棾?，并再次進(jìn)入歷史棧（成為棧頂）。

操作邏輯：

(1)訪問新頁面：

將當(dāng)前歷史棧的棧頂元素（如果存在，即用戶點(diǎn)擊了“后退”后處于瀏覽的那個頁面）依次彈出到未來?xiàng)＃ㄒ驗(yàn)橛脩艨赡芤扒斑M(jìn)”回去）。

將代表新訪問頁面的記錄（URL,標(biāo)題等）壓入歷史棧。

清空未來?xiàng)＃驗(yàn)橛脩粢呀?jīng)向前移動到了新的位置。

更新當(dāng)前活動頁面。

(2)點(diǎn)擊“后退”按鈕：

如果歷史棧不為空：

彈出歷史棧的棧頂元素（即當(dāng)前頁面記錄）。

將這個元素壓入未來?xiàng)！?/p>

從歷史棧彈出的下一個元素（即前一個頁面記錄）成為新的當(dāng)前活動頁面。

如果歷史棧為空（通常表示用戶在歷史記錄的第一頁），則可能顯示“沒有更多歷史記錄”或停留在當(dāng)前頁面。

(3)點(diǎn)擊“前進(jìn)”按鈕：

如果未來?xiàng)２粸榭眨?/p>

彈出未來?xiàng)５臈ｍ斣亍?/p>

將這個元素壓入歷史棧。

從未來?xiàng)棾龅南乱粋€元素（即下一個要訪問的頁面記錄）成為新的當(dāng)前活動頁面。

如果未來?xiàng)榭眨从脩粢呀?jīng)到達(dá)歷史記錄的末尾），則可能顯示“沒有更多歷史記錄”或停留在當(dāng)前頁面。

這種雙棧結(jié)構(gòu)確保了“后退”總是回到上一個有效的瀏覽狀態(tài)，而“前進(jìn)”則是在已訪問過的狀態(tài)之間導(dǎo)航。

---

四、棧的實(shí)現(xiàn)方式

棧可以通過兩種主要方式實(shí)現(xiàn)：基于數(shù)組的實(shí)現(xiàn)和基于鏈表的實(shí)現(xiàn)。

（一）基于數(shù)組的實(shí)現(xiàn)（順序棧）

使用一個固定大小的數(shù)組來存儲棧元素，并使用一個整數(shù)索引（通常稱為`top`或`head`）來指示棧頂?shù)奈恢谩?/p>

優(yōu)點(diǎn)：

內(nèi)存空間連續(xù)：棧元素存儲在連續(xù)的內(nèi)存地址上，這有利于CPU緩存（Cache）的利用，從而可能提高訪問速度。

訪問速度快：由于內(nèi)存連續(xù)，棧頂元素的位置是已知的（`top`索引處），因此`push`和`pop`操作的時間復(fù)雜度都是O(1)。

實(shí)現(xiàn)簡單：邏輯清晰，只需要數(shù)組和少數(shù)幾個變量（如`top`,`max_size`）。

缺點(diǎn)：

大小固定：在創(chuàng)建棧時需要指定最大容量，一旦達(dá)到這個容量，棧就無法再添加新元素，會發(fā)生“棧溢出”（StackOverflow）。如果預(yù)先無法確定棧的最大大小，則可能需要選擇過大的數(shù)組，造成內(nèi)存浪費(fèi)。

擴(kuò)展困難：如果棧滿了需要增加容量，通常需要創(chuàng)建一個更大的數(shù)組，并將所有現(xiàn)有元素復(fù)制到新數(shù)組中，這是一個O(n)的操作，且可能涉及內(nèi)存分配開銷。

示例：假設(shè)棧的最大容量為5，存儲在數(shù)組`stack=[None,None,None,None,None]`中，`top=0`（棧為空）。

`push(10)`：`stack[1]=10`,`top=1`

`push(20)`：`stack[2]=20`,`top=2`

`pop()`：返回20,`stack[2]=None`,`top=1`

`push(30)`：`stack[3]=30`,`top=3`

...以此類推

`push(50)`：`stack[5]=50`,`top=5`（棧滿）

`push(60)`：失敗，棧溢出。

空間復(fù)雜度：O(n)，其中n是棧的最大容量。

時間復(fù)雜度：`push`/`pop`為O(1)；`isFull`為O(1)；`IsEmpty`為O(1)。

（二）基于鏈表的實(shí)現(xiàn)（鏈?zhǔn)綏＃?/p>

使用鏈表節(jié)點(diǎn)來存儲棧元素，每個節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個節(jié)點(diǎn)的指針。鏈表的頭部（頭節(jié)點(diǎn)）通常用作棧頂。

優(yōu)點(diǎn)：

動態(tài)大小：棧的大小只受限于可用內(nèi)存，可以根據(jù)需要動態(tài)增長或縮小，不會發(fā)生棧溢出（除非內(nèi)存耗盡）。

按需分配：只有在添加新元素時才分配內(nèi)存，可以更有效地利用內(nèi)存空間，避免預(yù)分配帶來的浪費(fèi)。

擴(kuò)展方便：添加新元素只需要分配一個節(jié)點(diǎn)大小的內(nèi)存，并將指針修改即可，時間復(fù)雜度為O(1)。

缺點(diǎn)：

內(nèi)存空間不連續(xù)：節(jié)點(diǎn)可能分散在內(nèi)存的任意位置，需要通過指針連接。

指針開銷：每個節(jié)點(diǎn)都需要額外的空間來存儲指針（通常是8字節(jié)或4字節(jié)，取決于系統(tǒng)架構(gòu)），相比順序棧有一定內(nèi)存開銷。

訪問速度可能稍慢：雖然`push`和`pop`本身是O(1)，但由于可能需要遍歷鏈表（盡管鏈?zhǔn)綏ＭǔＶ魂P(guān)心頭部和尾部，頭部即棧頂），且現(xiàn)代CPU對內(nèi)存連續(xù)訪問更友好，實(shí)際性能可能略低于理想情況下的順序棧。但在只訪問棧頂?shù)那闆r下，性能仍然是O(1)。

示例：棧由鏈表`Node{value:30,next:Node{value:20,next:Node{value:10,next:None}}}`表示，棧頂是`value=30`的節(jié)點(diǎn)。

`push(40)`：創(chuàng)建新節(jié)點(diǎn)`Node{value:40,next:None}`，修改頭部指針`head.next=new_node`,`head=new_node`。棧頂變?yōu)閌value=40`。

`pop()`：`temp=head`,`head=head.next`,返回`temp.value`（40）。釋放`temp`節(jié)點(diǎn)。棧頂變?yōu)閌value=30`。

空間復(fù)雜度：O(n)，其中n是棧中元素的數(shù)量。

時間復(fù)雜度：`push`/`pop`為O(1)；`isFull`不適用；`IsEmpty`為O(1)。

---

五、結(jié)論

棧作為一種基礎(chǔ)且強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，憑借其后進(jìn)先出（LIFO）的特性，在眾多領(lǐng)域扮演著不可或缺的角色。從計(jì)算機(jī)科學(xué)的核心概念——函數(shù)調(diào)用棧，到我們?nèi)粘Ｊ褂玫能浖δ堋磉_(dá)式求值、瀏覽器歷史記錄和編輯器撤銷，棧都發(fā)揮著重要作用。無論是簡單高效的基于數(shù)組實(shí)現(xiàn)，還是靈活動態(tài)的基于鏈表實(shí)現(xiàn)，都有其適用的場景和優(yōu)缺點(diǎn)。

理解棧的工作原理和應(yīng)用方式，不僅有助于解決具體的編程問題，更能加深對程序運(yùn)行機(jī)制和數(shù)據(jù)管理方式的理解。在設(shè)計(jì)和實(shí)現(xiàn)算法或系統(tǒng)時，根據(jù)具體需求選擇合適的棧實(shí)現(xiàn)方式，并巧妙利用其特性，能夠有效提升程序的效率和可維護(hù)性。掌握棧是成為優(yōu)秀程序員的基礎(chǔ)技能之一。

棧的應(yīng)用場景解析報告

一、引言

棧是一種重要的數(shù)據(jù)結(jié)構(gòu)，具有后進(jìn)先出（LIFO）的特性。它廣泛應(yīng)用于各種計(jì)算場景，從簡單的編程任務(wù)到復(fù)雜的系統(tǒng)設(shè)計(jì)。本報告將解析棧的主要應(yīng)用場景，并說明其優(yōu)勢及適用條件。通過具體案例，展示棧如何在不同領(lǐng)域發(fā)揮作用。

---

二、棧的基本特性與優(yōu)勢

（一）棧的定義與核心特性

1.后進(jìn)先出（LIFO）：棧中最后被添加的元素將是第一個被移除的元素。

2.操作受限：主要支持兩種操作——入棧（push）和出棧（pop）。

3.固定或動態(tài)大?。簵？梢允枪潭ù笮〉模ㄈ鐢?shù)組實(shí)現(xiàn)）或動態(tài)擴(kuò)展的（如鏈表實(shí)現(xiàn)）。

（二）棧的主要優(yōu)勢

1.高效性：入棧和出棧操作的時間復(fù)雜度為O(1)。

2.簡單性：實(shí)現(xiàn)邏輯清晰，易于理解和應(yīng)用。

3.靈活性：適用于多種需要逆序處理數(shù)據(jù)的場景。

---

三、棧的典型應(yīng)用場景

（一）表達(dá)式求值

1.中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式（逆波蘭表示法）

步驟：

(1)初始化一個空棧和輸出隊(duì)列。

(2)逐個讀取表達(dá)式中的符號：

-若為操作數(shù)，直接加入輸出隊(duì)列。

-若為運(yùn)算符，根據(jù)優(yōu)先級與棧頂元素比較：

-優(yōu)先級高或棧為空，入棧。

-優(yōu)先級低或相等，將棧頂元素彈出至輸出隊(duì)列，再入棧當(dāng)前符號。

(3)處理完所有符號后，將棧中剩余元素依次彈出至輸出隊(duì)列。

2.后綴表達(dá)式求值

步驟：

(1)初始化一個空棧。

(2)逐個讀取后綴表達(dá)式中的符號：

-若為操作數(shù)，入棧。

-若為運(yùn)算符，彈出棧頂兩個操作數(shù)進(jìn)行計(jì)算，將結(jié)果入棧。

(3)最終棧頂元素即為表達(dá)式結(jié)果。

---

（二）函數(shù)調(diào)用棧

1.調(diào)用棧的作用

-管理函數(shù)調(diào)用過程中的局部變量和返回地址。

-每次函數(shù)調(diào)用時，創(chuàng)建新的棧幀存儲信息。

-函數(shù)返回時，棧幀被彈出，恢復(fù)之前的調(diào)用狀態(tài)。

2.示例場景

-遞歸函數(shù)：如階乘計(jì)算、斐波那契數(shù)列。

-異常處理：記錄錯誤發(fā)生時的調(diào)用路徑。

---

（三）路徑回溯

1.游戲與搜索算法

-迷宮求解：使用棧記錄移動路徑，遇到死路時回溯。

-深度優(yōu)先搜索（DFS）：在圖遍歷中，棧用于存儲待訪問的節(jié)點(diǎn)。

步驟：

(1)將起始節(jié)點(diǎn)入棧。

(2)循環(huán)：

-若棧為空，結(jié)束。

-彈出棧頂節(jié)點(diǎn)，標(biāo)記為已訪問。

-將其未訪問的鄰接節(jié)點(diǎn)按順序入棧。

2.編輯器撤銷功能

-記錄用戶的操作歷史，撤銷時依次彈出棧頂操作。

---

（四）瀏覽器歷史記錄

1.前進(jìn)/后退功能實(shí)現(xiàn)

-使用兩個棧：

-歷史棧：記錄從首頁到當(dāng)前頁的路徑。

-未來?xiàng)＃河涗洀漠?dāng)前頁到已訪問過的頁面路徑。

操作邏輯：

(1)切換頁面時，將當(dāng)前頁面從歷史棧推入未來?xiàng)?，更新歷史棧頂。

(2)點(diǎn)擊“后退”時，彈出歷史棧頂至未來?xiàng)！?/p>

(3)點(diǎn)擊“前進(jìn)”時，彈出未來?xiàng)ｍ斨翚v史棧。

---

四、棧的實(shí)現(xiàn)方式

（一）基于數(shù)組的實(shí)現(xiàn)

優(yōu)點(diǎn)：

-訪問速度快（O(1)）。

-內(nèi)存連續(xù)，緩存友好。

缺點(diǎn)：

-固定大小限制（需預(yù)留空間）。

-擴(kuò)容時可能需要數(shù)組復(fù)制。

示例：

棧底-->[空,空,3,1,5]<--棧頂

top=2

（二）基于鏈表的實(shí)現(xiàn)

優(yōu)點(diǎn)：

-動態(tài)擴(kuò)展，按需分配。

-無需預(yù)分配空間。

缺點(diǎn)：

-鏈接指針增加內(nèi)存開銷。

-訪問速度受鏈表長度影響。

示例：

Node{value:5,next:Node{value:1,next:Node{value:3,next:None}}}

---

五、結(jié)論

棧作為一種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，在多個領(lǐng)域展現(xiàn)出重要價值。其簡潔高效的特性使其成為表達(dá)式求值、函數(shù)調(diào)用管理、路徑回溯等場景的理想選擇。根據(jù)實(shí)際需求，可以選擇合適的實(shí)現(xiàn)方式（數(shù)組或鏈表）以平衡性能與資源消耗。掌握棧的應(yīng)用原理，有助于提升算法設(shè)計(jì)和問題解決能力。

棧的應(yīng)用場景解析報告

一、引言

棧是一種重要的數(shù)據(jù)結(jié)構(gòu)，具有后進(jìn)先出（LIFO）的特性。它廣泛應(yīng)用于各種計(jì)算場景，從簡單的編程任務(wù)到復(fù)雜的系統(tǒng)設(shè)計(jì)。本報告將解析棧的主要應(yīng)用場景，并說明其優(yōu)勢及適用條件。通過具體案例，展示棧如何在不同領(lǐng)域發(fā)揮作用。

---

二、棧的基本特性與優(yōu)勢

（一）棧的定義與核心特性

1.后進(jìn)先出（LIFO）：棧中最后被添加的元素將是第一個被移除的元素。這一特性使得棧在處理需要逆序訪問或撤銷操作的數(shù)據(jù)時具有天然優(yōu)勢。例如，在瀏覽器歷史記錄中，最后訪問的頁面應(yīng)該是第一個可以“后退”的頁面。

2.操作受限：棧主要支持兩種基本操作：

入棧（Push）：將一個新元素添加到棧頂。如果棧已滿（在固定大小棧中），操作可能失敗或觸發(fā)溢出。

出棧（Pop）：移除并返回棧頂元素。如果棧為空，操作可能失敗或觸發(fā)下溢（Underflow）。

除了這兩種基本操作，有時也會提供：

查看棧頂（Peek或Top）：返回棧頂元素的值，但不移除它。

檢查?？眨↖sEmpty）：判斷棧是否為空。

檢查棧滿（IsFull）：判斷棧是否已達(dá)到容量上限（僅限固定大小棧）。

3.固定或動態(tài)大?。簵５膶?shí)現(xiàn)可以基于固定大小的數(shù)組，也可以基于鏈表。固定大小棧在內(nèi)存使用上更簡單，但可能需要預(yù)留空間或限制棧的最大容量；動態(tài)大小棧（如鏈?zhǔn)綏＃┛梢愿鶕?jù)需要擴(kuò)展，更靈活，但通常需要額外的內(nèi)存開銷（如指針）。

（二）棧的主要優(yōu)勢

1.高效性：入棧和出棧操作的時間復(fù)雜度均為O(1)，即常數(shù)時間。這是因?yàn)闊o論是基于數(shù)組的順序棧還是基于鏈表的鏈?zhǔn)綏＃L問棧頂元素的操作都非常直接和快速。這使得棧非常適合需要頻繁進(jìn)行元素添加和移除的場景。

2.簡單性：棧的操作接口簡單，只有幾個核心方法。其邏輯清晰，易于理解和實(shí)現(xiàn)，降低了編程復(fù)雜度。對于初學(xué)者來說，棧是一個很好的數(shù)據(jù)結(jié)構(gòu)入門概念。

3.靈活性：棧的LIFO特性使其能夠適應(yīng)多種需要逆序處理或依賴最近操作的場景。它可以作為一種“臨時存儲”或“狀態(tài)管理”的工具，在算法和系統(tǒng)中扮演輔助角色。

---

三、棧的典型應(yīng)用場景

（一）表達(dá)式求值

1.中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式（逆波蘭表示法）

中綴表達(dá)式（如`3+42/(1-5)`）的運(yùn)算符位于操作數(shù)之間，而計(jì)算機(jī)底層（如堆棧處理器）通常更適合處理后綴表達(dá)式（如`34215-/`）。轉(zhuǎn)換過程利用棧來暫存運(yùn)算符，并根據(jù)優(yōu)先級規(guī)則進(jìn)行排列。

轉(zhuǎn)換步驟（艾茲恩公式-ShuntingYardAlgorithm）：

(1)初始化：創(chuàng)建一個空棧用于存儲運(yùn)算符（稱為`operator_stack`），創(chuàng)建一個空列表或隊(duì)列用于存儲輸出（稱為`output_queue`）。

(2)逐個掃描中綴表達(dá)式的符號（從左到右）：

遇到操作數(shù)：

-直接將操作數(shù)添加到`output_queue`的末尾。

遇到運(yùn)算符（如+,-,,/,^）：

-若`operator_stack`為空：將當(dāng)前運(yùn)算符直接入棧。

-若`operator_stack`不為空：

-比較當(dāng)前運(yùn)算符與棧頂運(yùn)算符的優(yōu)先級：

當(dāng)前運(yùn)算符優(yōu)先級>棧頂運(yùn)算符優(yōu)先級：將當(dāng)前運(yùn)算符入棧。

當(dāng)前運(yùn)算符優(yōu)先級<=棧頂運(yùn)算符優(yōu)先級：

-將棧頂運(yùn)算符彈出，并添加到`output_queue`。

-重復(fù)此步驟，直到棧為空或棧頂運(yùn)算符的優(yōu)先級低于當(dāng)前運(yùn)算符。

-將當(dāng)前運(yùn)算符入棧。

遇到左括號'('：

-將左括號入棧。它將作為后續(xù)運(yùn)算符的臨時分隔符。

遇到右括號')'：

-彈出`operator_stack`中的運(yùn)算符，并添加到`output_queue`，直到遇到左括號'('。

-彈出左括號，丟棄它。（注意：左括號不加入輸出隊(duì)列）

(3)處理剩余運(yùn)算符：

-當(dāng)掃描完所有符號后，如果`operator_stack`中還有運(yùn)算符，則依次彈出并添加到`output_queue`，直到棧為空。

(4)結(jié)果：`output_queue`中存儲的序列即為后綴表達(dá)式。

優(yōu)先級示例：

`^`(冪運(yùn)算)>``,`/`(乘除)>`+`,`-`(加減)

同級運(yùn)算符從左到右結(jié)合。

示例：轉(zhuǎn)換`A+BC`

-A:output_queue=[A]

-+:operator_stack=[+](棧為空)

-B:output_queue=[A,B]

-:operator_stack=[+,](棧頂+優(yōu)先級>=，彈出+)

output_queue=[A,B,+]

operator_stack=[]

:operator_stack=[](棧為空)

-C:output_queue=[A,B,+,C]

-結(jié)束：彈出,output_queue=[A,B,+,C,]

最終后綴表達(dá)式為：`AB+C`

2.后綴表達(dá)式求值

后綴表達(dá)式（或稱逆波蘭表示法）的求值過程同樣利用棧，步驟更直接。

求值步驟：

(1)初始化：創(chuàng)建一個空棧。

(2)逐個掃描后綴表達(dá)式的符號（從左到右）：

遇到操作數(shù)：

-將操作數(shù)轉(zhuǎn)換為數(shù)值類型，并壓入棧中。

遇到運(yùn)算符（如+,-,,/）：

-從棧中彈出兩個操作數(shù)（注意：先彈出的是右操作數(shù)，后彈出的是左操作數(shù)，因?yàn)闂Ｊ荓IFO）。

-對這兩個操作數(shù)執(zhí)行當(dāng)前運(yùn)算符指定的運(yùn)算。

-將運(yùn)算結(jié)果壓入棧中。

(3)結(jié)果：當(dāng)掃描完所有符號后，棧中剩下的唯一元素就是整個表達(dá)式的求值結(jié)果。

示例：求值`34+5`

-3:stack=[3]

-4:stack=[3,4]

-+:彈出4,彈出3,計(jì)算3+4=7,壓入7。stack=[7]

-5:stack=[7,5]

-:彈出5,彈出7,計(jì)算75=35,壓入35。stack=[35]

-結(jié)束：最終結(jié)果為35。

---

（二）函數(shù)調(diào)用棧

函數(shù)調(diào)用棧是程序運(yùn)行時管理函數(shù)調(diào)用的一種機(jī)制，其核心就是棧。每次函數(shù)被調(diào)用時，都會創(chuàng)建一個新的“棧幀”（StackFrame），用于存儲該函數(shù)的局部變量、參數(shù)、返回地址等信息。當(dāng)函數(shù)執(zhí)行完畢或發(fā)生異常返回時，其棧幀會被彈出，程序控制權(quán)返回到之前的調(diào)用點(diǎn)。

1.調(diào)用棧的作用

存儲局部變量和參數(shù)：每個函數(shù)調(diào)用都有自己的獨(dú)立作用域，棧幀用于隔離不同函數(shù)的變量空間。

保存返回地址：函數(shù)執(zhí)行完畢后，需要知道從哪里繼續(xù)執(zhí)行（即調(diào)用它的函數(shù)）。返回地址通常存儲在棧幀中，并且在函數(shù)返回時被使用。

支持遞歸調(diào)用：遞歸函數(shù)通過調(diào)用棧實(shí)現(xiàn)每一層調(diào)用的上下文保存。每一層遞歸都有自己的棧幀，互不干擾。如果沒有調(diào)用棧，遞歸將無法保存中間狀態(tài)。

異常處理：當(dāng)程序發(fā)生異常時，異常處理機(jī)制需要沿著調(diào)用棧向上查找合適的異常處理代碼塊，棧幀記錄了函數(shù)的調(diào)用鏈，是實(shí)現(xiàn)這一功能的基礎(chǔ)。

中斷處理：操作系統(tǒng)中的中斷（如I/O完成）也會使用棧來保存當(dāng)前任務(wù)的狀態(tài)，以便處理完中斷后能正確返回。

2.示例場景

遞歸函數(shù)：

階乘計(jì)算：`factorial(n)`調(diào)用`factorial(n-1)`。每次調(diào)用`factorial(n-1)`時，都會為它分配一個新的棧幀存儲變量`n-1`的值和返回地址。當(dāng)最內(nèi)層的調(diào)用（如`factorial(1)`)返回時，其棧幀被彈出，然后`factorial(2)`繼續(xù)執(zhí)行。

```偽代碼

factorial(n):

ifn==0:

return1

else:

result=nfactorial(n-1)//調(diào)用棧幀內(nèi)會保存n,result,以及返回到調(diào)用點(diǎn)的地址

returnresult

```

斐波那契數(shù)列：計(jì)算`fib(n)`需要遞歸計(jì)算`fib(n-1)`和`fib(n-2)`。每次遞歸調(diào)用都會在調(diào)用棧上添加新的棧幀。

```偽代碼

fib(n):

ifn<=1:

returnn

else:

fib_n_minus_1=fib(n-1)//棧幀內(nèi)保存n,fib_n_minus_1,fib_n_minus_2,返回地址

fib_n_minus_2=fib(n-2)

returnfib_n_minus_1+fib_n_minus_2

```

注意：遞歸深度過大會導(dǎo)致棧溢出。

異常處理：當(dāng)代碼拋出異常時，程序會檢查當(dāng)前棧幀及后續(xù)棧幀，尋找?guī)в邢鄳?yīng)異常處理代碼的`try`塊。找到后，程序會跳轉(zhuǎn)到該處理代碼執(zhí)行。棧幀記錄了調(diào)用鏈，是定位錯誤和恢復(fù)程序狀態(tài)的關(guān)鍵。

---

（三）路徑回溯

棧在需要探索可能路徑并能在死路盡頭回退的場景中非常有用。其LIFO特性天然適合模擬“走一步，看一步，如果走不通就退回上一步”的邏輯。

1.游戲與搜索算法

迷宮求解：

玩家或算法從迷宮入口開始移動，每次選擇一個未探索的相鄰方向前進(jìn)。將已探索的路徑或當(dāng)前位置標(biāo)記為“已訪問”。如果前進(jìn)后到達(dá)死胡同（即所有相鄰方向都已探索或被阻擋），則需要回退到上一個位置，嘗試其他未探索的方向。這個過程非常適合用棧來實(shí)現(xiàn)：

步驟：

(1)初始化一個空棧，將起點(diǎn)位置（如坐標(biāo)(0,0)）及其狀態(tài)（如“未訪問”）入棧。

(2)循環(huán)執(zhí)行直到棧為空：

如果棧為空，表示所有路徑都已探索完畢或迷宮無解（根據(jù)情況判斷）。

彈出棧頂元素，記為當(dāng)前位置(x,y)和其狀態(tài)。

如果該位置是迷宮出口，則找到解。

如果該位置是死胡同（所有相鄰方向均不可行或已訪問），則忽略或標(biāo)記為“死路”。

否則，將該位置的未訪問相鄰位置（假設(shè)為(nx,ny)）及其狀態(tài)（“未訪問”）入棧。

（可選）為了記錄完整路徑，可以在入棧時將父節(jié)點(diǎn)信息也存儲起來。

棧頂始終代表當(dāng)前正在探索或回溯的“前一步”。

深度優(yōu)先搜索（DFS）：

DFS是一種圖遍歷算法，它沿著一條路徑盡可能深入，直到無法繼續(xù)前進(jìn)，然后回溯到上一個節(jié)點(diǎn)，繼續(xù)探索其他路徑。這正是棧的用武之地：

步驟：

(1)選擇一個起始節(jié)點(diǎn)，將其入棧。

(2)循環(huán)執(zhí)行直到棧為空：

如果棧為空，表示所有可達(dá)節(jié)點(diǎn)都已訪問或圖不連通（根據(jù)情況判斷）。

彈出棧頂節(jié)點(diǎn)`u`，標(biāo)記為已訪問。

遍歷節(jié)點(diǎn)`u`的所有鄰接節(jié)點(diǎn)`v`：

如果節(jié)點(diǎn)`v`未被訪問，則將節(jié)點(diǎn)`v`及其狀態(tài)（“未訪問”）入棧。

（可選）為了記錄訪問順序或路徑，可以在入棧時記錄節(jié)點(diǎn)`u`作為`v`的父節(jié)點(diǎn)。

棧頂節(jié)點(diǎn)始終是當(dāng)前正在訪問或準(zhǔn)備訪問的節(jié)點(diǎn)。

2.編輯器撤銷功能

計(jì)算機(jī)的文本編輯器、繪圖軟件等常常提供“撤銷”（Undo）功能，允許用戶取消最近的操作。棧是實(shí)現(xiàn)這一功能的有效方式：

概念：用戶的每一步操作（如插入文本、刪除文本、修改格式）都可以被視為一個“命令”或“動作”。

實(shí)現(xiàn)：

維護(hù)一個“操作歷史棧”。每執(zhí)行一次操作，就將這個操作的描述（以及可能需要的數(shù)據(jù)，如被刪除的文本內(nèi)容、修改前的格式）作為一個新元素壓入棧頂。

當(dāng)用戶點(diǎn)擊“撤銷”按鈕時，從棧頂彈出最后一個操作記錄。

根據(jù)彈出的記錄，執(zhí)行相應(yīng)的“反向操作”（如恢復(fù)被刪除的文本、恢復(fù)原始格式）。

（可選）為了支持“重做”（Redo），可以維護(hù)一個獨(dú)立的“操作重做棧”。撤銷操作后，可以將撤銷的命令記錄壓入重做棧。點(diǎn)擊“重做”時，則從重做棧彈出并執(zhí)行。

優(yōu)點(diǎn)：棧結(jié)構(gòu)簡單，能夠按操作發(fā)生的順序（后執(zhí)行的后撤銷）進(jìn)行管理。

---

（四）瀏覽器歷史記錄

現(xiàn)代網(wǎng)頁瀏覽器都提供了強(qiáng)大的歷史記錄功能，允許用戶瀏覽之前訪問過的網(wǎng)頁，并可以“后退”或“前進(jìn)”。

1.前進(jìn)/后退功能實(shí)現(xiàn)

瀏覽器通常使用兩個棧來管理用戶的瀏覽狀態(tài)：

歷史棧（BackStack）：存儲用戶從當(dāng)前頁面“后退”可以訪問的頁面記錄。當(dāng)用戶訪問一個新頁面時，當(dāng)前頁面記錄（通常是URL和頁面標(biāo)題）被推入歷史棧。

未來?xiàng)＃‵orwardStack）：存儲用戶從當(dāng)前頁面“前進(jìn)”可以訪問的頁面記錄。當(dāng)用戶執(zhí)行“后退”操作后，被彈出的頁面記錄會同時被推入未來?xiàng)！．?dāng)用戶執(zhí)行“前進(jìn)”操作時，頁面記錄會從未來?xiàng)棾觯⒃俅芜M(jìn)入歷史棧（成為棧頂）。

操作邏輯：

(1)訪問新頁面：

將當(dāng)前歷史棧的棧頂元素（如果存在，即用戶點(diǎn)擊了“后退”后處于瀏覽的那個頁面）依次彈出到未來?xiàng)＃ㄒ驗(yàn)橛脩艨赡芤扒斑M(jìn)”回去）。

將代表新訪問頁面的記錄（URL,標(biāo)題等）壓入歷史棧。

清空未來?xiàng)?，因?yàn)橛脩粢呀?jīng)向前移動到了新的位置。

更新當(dāng)前活動頁面。

(2)點(diǎn)擊“后退”按鈕：

如果歷史棧不為空：

彈出歷史棧的棧頂元素（即當(dāng)前頁面記錄）。

將這個元素壓入未來?xiàng)！?/p>

從歷史棧彈出的下一個元素（即前一個頁面記錄）成為新的當(dāng)前活動頁面。

如果歷史棧為空（通常表示用戶在歷史記錄的第一頁），則可能顯示“沒有更多歷史記錄”或停留在當(dāng)前頁面。

(3)點(diǎn)擊“前進(jìn)”按鈕：

如果未來?xiàng)２粸榭眨?/p>

彈出未來?xiàng)５臈ｍ斣亍?/p>

將這個元素壓入歷史棧。

從未來?xiàng)棾龅南乱粋€元素（即下一個要訪問的頁面記錄）成為新的當(dāng)前活動頁面。

如果未來?xiàng)榭眨从脩粢呀?jīng)到達(dá)歷史記錄的末尾），則可能顯示“沒有更多歷史記錄”或停留在當(dāng)前頁面。

這種雙棧結(jié)構(gòu)確保了“后退”總是回到上一個有效的瀏覽狀態(tài)，而“前進(jìn)”則是在已訪問過的狀態(tài)之間導(dǎo)航。

---

四、棧的實(shí)現(xiàn)方式

?？梢酝ㄟ^兩種主要方式實(shí)現(xiàn)：基于數(shù)組的實(shí)現(xiàn)和基于鏈表的實(shí)現(xiàn)。

（一）基于數(shù)組的實(shí)現(xiàn)（順序棧）

使用一個固定大小的數(shù)組來存儲棧元素，并使用一個整數(shù)索引（通常稱為`top`或`head`）來指