棧和隊(duì)列的應(yīng)用報(bào)告一、引言

棧和隊(duì)列是兩種重要的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和軟件工程中。它們具有獨(dú)特的操作特性（LIFO和FIFO），能夠解決多種實(shí)際問(wèn)題。本報(bào)告將詳細(xì)介紹棧和隊(duì)列的基本概念、操作方法及其典型應(yīng)用場(chǎng)景，并通過(guò)實(shí)例說(shuō)明其使用價(jià)值。

二、棧和隊(duì)列的基本概念

棧和隊(duì)列是線性數(shù)據(jù)結(jié)構(gòu)，但操作方式不同。

（一）棧（Stack）

1.定義：棧是一種后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，只允許在棧頂進(jìn)行插入和刪除操作。

2.基本操作：

(1)入棧（push）：將元素添加到棧頂。

(2)出棧（pop）：移除并返回棧頂元素。

(3)查看棧頂（peek/top）：返回棧頂元素但不移除。

(4)判斷空棧（isEmpty）：檢查棧是否為空。

（二）隊(duì)列（Queue）

1.定義：隊(duì)列是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，元素從隊(duì)尾入隊(duì)，從隊(duì)頭出隊(duì)。

2.基本操作：

(1)入隊(duì)（enqueue）：將元素添加到隊(duì)尾。

(2)出隊(duì)（dequeue）：移除并返回隊(duì)頭元素。

(3)查看隊(duì)頭（front）：返回隊(duì)頭元素但不移除。

(4)判斷空隊(duì)（isEmpty）：檢查隊(duì)列是否為空。

三、棧的應(yīng)用場(chǎng)景

棧的LIFO特性使其適用于需要逆序處理或回溯的場(chǎng)景。

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

1.說(shuō)明：程序執(zhí)行時(shí)，每次調(diào)用函數(shù)都會(huì)在棧上創(chuàng)建新的棧幀，函數(shù)返回時(shí)棧幀被移除。

2.應(yīng)用：

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

(2)代碼編譯：管理函數(shù)嵌套和變量作用域。

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

1.說(shuō)明：使用棧處理中綴表達(dá)式、后綴表達(dá)式或前綴表達(dá)式。

2.步驟（以中綴轉(zhuǎn)后綴為例）：

(1)初始化一個(gè)運(yùn)算符棧和一個(gè)輸出隊(duì)列。

(2)遍歷表達(dá)式，遇到數(shù)字直接加入隊(duì)列，遇到運(yùn)算符按優(yōu)先級(jí)壓棧。

(3)處理完整表達(dá)式后，將棧中剩余運(yùn)算符加入隊(duì)列。

（三）瀏覽器歷史記錄

1.說(shuō)明：后退按鈕使用棧記錄訪問(wèn)頁(yè)面，最新訪問(wèn)的頁(yè)面在棧頂。

2.操作：

(1)訪問(wèn)新頁(yè)面：壓棧。

(2)點(diǎn)擊后退：出棧并返回上一頁(yè)。

四、隊(duì)列的應(yīng)用場(chǎng)景

隊(duì)列的FIFO特性使其適用于需要按順序處理元素的場(chǎng)景。

（一）任務(wù)調(diào)度

1.說(shuō)明：操作系統(tǒng)使用隊(duì)列管理任務(wù)執(zhí)行順序。

2.應(yīng)用：

(1)打印隊(duì)列：按提交順序處理打印任務(wù)。

(2)網(wǎng)絡(luò)請(qǐng)求處理：管理待處理的HTTP請(qǐng)求。

（二）廣度優(yōu)先搜索（BFS）

1.說(shuō)明：BFS使用隊(duì)列遍歷圖或樹(shù)的節(jié)點(diǎn)。

2.步驟：

(1)將起點(diǎn)節(jié)點(diǎn)入隊(duì)。

(2)循環(huán)直到隊(duì)列為空：出隊(duì)節(jié)點(diǎn)，訪問(wèn)其鄰居節(jié)點(diǎn)，未訪問(wèn)的鄰居入隊(duì)。

（三）緩沖區(qū)管理

1.說(shuō)明：隊(duì)列用于臨時(shí)存儲(chǔ)數(shù)據(jù)流，如音頻或視頻緩沖。

2.應(yīng)用：

(1)音頻播放：按順序播放緩沖區(qū)中的音頻幀。

(2)數(shù)據(jù)包轉(zhuǎn)發(fā)：路由器按接收順序處理數(shù)據(jù)包。

五、總結(jié)

棧和隊(duì)列是基礎(chǔ)但強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，通過(guò)其LIFO和FIFO特性，可高效解決函數(shù)調(diào)用、表達(dá)式求值、任務(wù)調(diào)度、BFS等實(shí)際問(wèn)題。在實(shí)際應(yīng)用中，應(yīng)根據(jù)需求選擇合適的結(jié)構(gòu)，并合理設(shè)計(jì)操作流程。

一、引言

棧和隊(duì)列是兩種基礎(chǔ)且重要的線性數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)科學(xué)和軟件工程的各個(gè)領(lǐng)域都有廣泛的應(yīng)用。它們的核心特性——棧的后進(jìn)先出（LIFO）和隊(duì)列的先進(jìn)先出（FIFO）——使得它們能夠有效地解決許多實(shí)際問(wèn)題，如表達(dá)式求值、函數(shù)調(diào)用管理、任務(wù)調(diào)度、資源分配和搜索算法等。本報(bào)告將深入探討棧和隊(duì)列的基本概念、關(guān)鍵操作及其典型應(yīng)用場(chǎng)景，并通過(guò)更詳細(xì)的步驟和實(shí)例說(shuō)明其使用價(jià)值和實(shí)現(xiàn)方式。

二、棧和隊(duì)列的基本概念

棧和隊(duì)列是線性數(shù)據(jù)結(jié)構(gòu)，意味著元素具有一對(duì)一的邏輯關(guān)系，但它們的操作受限，分別遵循LIFO和FIFO原則。

（一）棧（Stack）

1.定義：棧是一種僅允許在棧頂進(jìn)行插入（push）和刪除（pop）操作的數(shù)據(jù)結(jié)構(gòu)。它遵循后進(jìn)先出（LIFO,Last-In-First-Out）的原則，即最后被添加的元素將是第一個(gè)被移除的元素。棧是一種“操作受限”的線性表。

2.基本數(shù)據(jù)結(jié)構(gòu)表示：

(1)數(shù)組實(shí)現(xiàn)：使用一個(gè)一維數(shù)組來(lái)存儲(chǔ)棧元素，并維護(hù)一個(gè)指針（通常稱為棧頂指針，top）來(lái)指示棧頂元素的位置。初始時(shí)，top通常設(shè)置為-1，表示棧為空。

(2)鏈表實(shí)現(xiàn)：使用鏈節(jié)點(diǎn)鏈接各個(gè)元素，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。維護(hù)一個(gè)指向棧頂節(jié)點(diǎn)的指針（head或top）。

3.基本操作詳解：

(1)入棧（push）：將一個(gè)新元素添加到棧頂。

數(shù)組實(shí)現(xiàn)步驟：

a.檢查棧是否已滿（通常top==數(shù)組長(zhǎng)度-1）。如果滿，則無(wú)法入棧（發(fā)生棧溢出）。

b.top自增（top++）。

c.將新元素存儲(chǔ)在數(shù)組中索引為top的位置（array[top]=element）。

鏈表實(shí)現(xiàn)步驟：

a.創(chuàng)建一個(gè)新節(jié)點(diǎn)，存儲(chǔ)元素?cái)?shù)據(jù)。

b.將新節(jié)點(diǎn)的next指針指向當(dāng)前棧頂節(jié)點(diǎn)（top節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)）。

c.將棧頂指針（top）更新為新節(jié)點(diǎn)。

(2)出棧（pop）：移除并返回棧頂元素。

數(shù)組實(shí)現(xiàn)步驟：

a.檢查棧是否為空（通常top==-1）。如果空，則無(wú)法出棧（發(fā)生棧下溢）。

b.獲取棧頂元素（element=array[top]）。

c.top自減（top--）。

d.返回獲取的元素。

鏈表實(shí)現(xiàn)步驟：

a.檢查棧是否為空（top==NULL）。如果空，則無(wú)法出棧。

b.獲取棧頂元素（element=top->data）。

c.保存棧頂指針的下一個(gè)節(jié)點(diǎn)（next_node=top->next）。

d.釋放當(dāng)前棧頂節(jié)點(diǎn)內(nèi)存（或使其可被垃圾回收）。

e.將棧頂指針（top）更新為next_node。

f.返回獲取的元素。

(3)查看棧頂（peek或top）：返回棧頂元素的值，但不移除它。

數(shù)組實(shí)現(xiàn)：直接返回array[top]的值（前提是棧非空）。

鏈表實(shí)現(xiàn)：返回top->data的值（前提是棧非空）。

(4)判斷?？眨╥sEmpty）：檢查棧是否不包含任何元素。

數(shù)組實(shí)現(xiàn)：判斷top==-1。

鏈表實(shí)現(xiàn)：判斷top==NULL。

（二）隊(duì)列（Queue）

1.定義：隊(duì)列是一種只允許在隊(duì)頭（front）進(jìn)行刪除（dequeue）操作、在隊(duì)尾（rear）進(jìn)行插入（enqueue）操作的數(shù)據(jù)結(jié)構(gòu)。它遵循先進(jìn)先出（FIFO,First-In-First-Out）的原則，即最早被添加的元素將是第一個(gè)被移除的元素。隊(duì)列也是一種“操作受限”的線性表。

2.基本數(shù)據(jù)結(jié)構(gòu)表示：

(1)數(shù)組實(shí)現(xiàn)：使用一個(gè)一維數(shù)組來(lái)存儲(chǔ)隊(duì)列元素，并維護(hù)兩個(gè)指針：隊(duì)頭指針（front）和隊(duì)尾指針（rear）。初始時(shí)，通常front和rear都設(shè)置為0，表示隊(duì)列為空。

(2)鏈表實(shí)現(xiàn)：使用鏈節(jié)點(diǎn)鏈接各個(gè)元素，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。維護(hù)兩個(gè)指針：隊(duì)頭指針（front）指向隊(duì)列第一個(gè)元素，隊(duì)尾指針（rear）指向隊(duì)列最后一個(gè)元素。

3.基本操作詳解：

(1)入隊(duì)（enqueue）：將一個(gè)新元素添加到隊(duì)尾。

數(shù)組實(shí)現(xiàn)步驟：

a.檢查隊(duì)列是否已滿（通常(rear+1)%array_length==front）。如果滿，則無(wú)法入隊(duì)（發(fā)生隊(duì)列溢出）。

b.將新元素存儲(chǔ)在數(shù)組中索引為rear的位置（array[rear]=element）。

c.rear指針向前移動(dòng)（rear=(rear+1)%array_length）。使用模運(yùn)算實(shí)現(xiàn)循環(huán)隊(duì)列。

鏈表實(shí)現(xiàn)步驟：

a.創(chuàng)建一個(gè)新節(jié)點(diǎn)，存儲(chǔ)元素?cái)?shù)據(jù)。

b.如果隊(duì)列為空（front==NULL），則新節(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾，讓front和rear都指向新節(jié)點(diǎn)。

c.否則，將新節(jié)點(diǎn)的next指針指向當(dāng)前隊(duì)尾節(jié)點(diǎn)（rear->next）。

d.將隊(duì)尾指針（rear）更新為新節(jié)點(diǎn)。

(2)出隊(duì)（dequeue）：移除并返回隊(duì)頭元素。

數(shù)組實(shí)現(xiàn)步驟：

a.檢查隊(duì)列是否為空（通常front==rear）。如果空，則無(wú)法出隊(duì)（發(fā)生隊(duì)列下溢）。

b.獲取隊(duì)頭元素（element=array[front]）。

c.front指針向前移動(dòng)（front=(front+1)%array_length）。使用模運(yùn)算實(shí)現(xiàn)循環(huán)隊(duì)列。

d.返回獲取的元素。

鏈表實(shí)現(xiàn)步驟：

a.檢查隊(duì)列是否為空（front==NULL）。如果空，則無(wú)法出隊(duì)。

b.獲取隊(duì)頭元素（element=front->data）。

c.保存隊(duì)頭指針的下一個(gè)節(jié)點(diǎn)（next_node=front->next）。

d.釋放當(dāng)前隊(duì)頭節(jié)點(diǎn)內(nèi)存（或使其可被垃圾回收）。

e.將隊(duì)頭指針（front）更新為next_node。

f.如果更新后的front指針為NULL（原隊(duì)頭是唯一節(jié)點(diǎn)），則需要同時(shí)將rear指針也設(shè)置為NULL。

g.返回獲取的元素。

(3)查看隊(duì)頭（front或peek）：返回隊(duì)頭元素的值，但不移除它。

數(shù)組實(shí)現(xiàn)：直接返回array[front]的值（前提是隊(duì)列非空）。

鏈表實(shí)現(xiàn)：返回front->data的值（前提是隊(duì)列非空）。

(4)判斷隊(duì)空（isEmpty）：檢查隊(duì)列是否不包含任何元素。

數(shù)組實(shí)現(xiàn)：判斷front==rear。

鏈表實(shí)現(xiàn)：判斷front==NULL。

三、棧的應(yīng)用場(chǎng)景

棧的LIFO特性使其適用于需要逆序處理、回溯或管理嵌套關(guān)系的場(chǎng)景。

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

1.說(shuō)明：在程序執(zhí)行過(guò)程中，每當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，操作系統(tǒng)會(huì)為該函數(shù)創(chuàng)建一個(gè)臨時(shí)的數(shù)據(jù)結(jié)構(gòu)（棧幀或激活記錄），其中包含函數(shù)的局部變量、參數(shù)、返回地址等信息。這個(gè)棧幀被壓入函數(shù)調(diào)用棧中。當(dāng)函數(shù)執(zhí)行完畢并返回時(shí)，對(duì)應(yīng)的棧幀被彈出并銷毀。函數(shù)調(diào)用棧天然地支持遞歸調(diào)用和函數(shù)嵌套。

2.應(yīng)用詳解：

(1)遞歸算法實(shí)現(xiàn)：

步驟：將遞歸問(wèn)題轉(zhuǎn)化為可由棧模擬的迭代問(wèn)題。

例子：計(jì)算階乘n!。

a.遞歸實(shí)現(xiàn)（偽代碼）：

functionfactorial(n):

ifn==0:

return1

else:

returnnfactorial(n-1)

b.棧模擬實(shí)現(xiàn)（偽代碼）：

stack=emptystack

result=1

forifrom1ton:

stack.push(i)

whilenotstack.isEmpty():

value=stack.pop()

result=value

returnresult

優(yōu)勢(shì)：避免遞歸深度過(guò)大導(dǎo)致的遞歸調(diào)用棧溢出，轉(zhuǎn)換為迭代后更可控。

(2)代碼編譯與解釋執(zhí)行：

步驟：編譯器或解釋器在處理程序時(shí)，使用棧來(lái)管理函數(shù)嵌套、流程控制（如if-else,switch-case）和局部變量作用域。

應(yīng)用：在解析表達(dá)式、執(zhí)行語(yǔ)句時(shí)，棧用于暫存中間結(jié)果和操作符。

(3)撤銷/重做（Undo/Redo）功能：

步驟：用戶每執(zhí)行一個(gè)操作，將該操作的相關(guān)狀態(tài)或指令壓入棧中。執(zhí)行撤銷時(shí)，出棧并執(zhí)行相反操作；執(zhí)行重做時(shí)，將撤銷的操作再次壓回棧并執(zhí)行。

應(yīng)用：文本編輯器、繪圖軟件等。

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

1.說(shuō)明：使用?？梢愿咝У赜?jì)算中綴表達(dá)式（如3+42/(1-5)）、后綴表達(dá)式（如34+215-/）或前綴表達(dá)式（波蘭式，如+342-15）。

2.應(yīng)用詳解：

(1)中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式（逆波蘭式）算法（ShuntingYard算法）步驟：

初始化一個(gè)空的操作符棧和一個(gè)空的后綴表達(dá)式隊(duì)列（或列表）。

從左到右掃描中綴表達(dá)式的每個(gè)字符（token）：

a.如果是操作數(shù)（數(shù)字或變量），直接將其加入后綴表達(dá)式隊(duì)列。

b.如果是左括號(hào)'('，將其壓入操作符棧。

c.如果是右括號(hào)')'：

i.彈出并丟棄棧中的操作符，加入后綴表達(dá)式隊(duì)列，直到遇到左括號(hào)'('。彈出左括號(hào)，但不加入隊(duì)列。

ii.如果棧頂是函數(shù)名（如sin,cos），則將其彈出并加入隊(duì)列（如果需要）。

d.如果是操作符（如+,-,,/）：

i.彈出棧中所有優(yōu)先級(jí)高于或等于當(dāng)前操作符的操作符，并加入后綴表達(dá)式隊(duì)列。

ii.如果棧頂是左括號(hào)'('，則將當(dāng)前操作符壓入棧。

iii.將當(dāng)前操作符壓入操作符棧。

掃描結(jié)束后，彈出并加入操作符棧中剩余的所有操作符。

(2)后綴表達(dá)式求值算法步驟：

初始化一個(gè)空棧。

從左到右掃描后綴表達(dá)式的每個(gè)token：

a.如果是操作數(shù)，將其壓入棧。

b.如果是操作符，彈出棧頂?shù)膔equired_number個(gè)操作數(shù)（順序不重要，因?yàn)闂Ｊ荓IFO），執(zhí)行運(yùn)算（操作符+第一個(gè)操作數(shù)+第二個(gè)操作數(shù)），將結(jié)果壓回棧。

掃描結(jié)束后，棧頂元素即為表達(dá)式的值。

(3)前綴表達(dá)式求值（波蘭式）算法步驟：

需要先反轉(zhuǎn)前綴表達(dá)式，使其從右到左成為后綴表達(dá)式形式。

然后應(yīng)用后綴表達(dá)式求值算法步驟進(jìn)行計(jì)算。

（三）瀏覽器歷史記錄與后退功能

1.說(shuō)明：現(xiàn)代瀏覽器通常使用棧來(lái)管理用戶訪問(wèn)的頁(yè)面歷史。用戶訪問(wèn)的每個(gè)頁(yè)面URL或會(huì)話狀態(tài)被壓入一個(gè)棧（稱為“后退?！保｜c(diǎn)擊瀏覽器的后退按鈕相當(dāng)于從棧頂彈出當(dāng)前頁(yè)面，返回到前一個(gè)頁(yè)面。

2.應(yīng)用詳解：

(1)前進(jìn)/后退操作：

訪問(wèn)新頁(yè)面：將新頁(yè)面的標(biāo)識(shí)（如URL或會(huì)話指針）壓入后退棧。

點(diǎn)擊后退：檢查后退棧是否為空。如果不空，彈出棧頂元素，更新瀏覽器顯示的當(dāng)前頁(yè)面，并將后退棧的下一個(gè)元素（如果存在）設(shè)置為可用的“前進(jìn)?！钡臈ｍ?。

點(diǎn)擊前進(jìn)：如果存在“前進(jìn)?！鼻曳强?，彈出棧頂元素，更新瀏覽器顯示，并將該元素移回“后退?！薄?/p>

(2)雙擊后退/前進(jìn)：連續(xù)點(diǎn)擊可能涉及連續(xù)彈出棧頂元素。

（四）括號(hào)匹配

1.說(shuō)明：檢查一個(gè)字符串（如代碼、表達(dá)式）中的括號(hào)（如'(',')','{','}','[',']'）是否正確匹配和配對(duì)。

2.應(yīng)用詳解：

步驟：

a.初始化一個(gè)空棧。

b.從左到右掃描字符串的每個(gè)字符：

i.如果是開(kāi)括號(hào)（'(','{','['），將其壓入棧。

ii.如果是閉括號(hào)（')','}',']'）：

a.檢查棧是否為空。如果為空，則沒(méi)有對(duì)應(yīng)的開(kāi)括號(hào)，匹配失敗。

b.彈出棧頂?shù)拈_(kāi)括號(hào)。

c.檢查彈出的開(kāi)括號(hào)是否與當(dāng)前的閉括號(hào)類型匹配（'('與')'，'{'與'}'，'['與']'）。如果不匹配，匹配失敗。

c.掃描結(jié)束后，檢查棧是否為空。如果棧非空，說(shuō)明有未匹配的開(kāi)括號(hào)，匹配失敗。如果棧為空，則所有括號(hào)匹配成功。

應(yīng)用：編譯器錯(cuò)誤檢查、語(yǔ)法分析、驗(yàn)證代碼或配置文件格式。

四、隊(duì)列的應(yīng)用場(chǎng)景

隊(duì)列的FIFO特性使其適用于需要按順序處理元素、管理等待隊(duì)列或進(jìn)行層次遍歷的場(chǎng)景。

（一）任務(wù)調(diào)度與資源管理

1.說(shuō)明：操作系統(tǒng)和應(yīng)用程序使用隊(duì)列來(lái)管理待處理的任務(wù)或請(qǐng)求，確保它們按照請(qǐng)求的順序被處理。

2.應(yīng)用詳解：

(1)打印隊(duì)列：

步驟：用戶提交打印任務(wù)時(shí)，任務(wù)信息（如文件路徑、打印份數(shù)、紙張?jiān)O(shè)置）被入隊(duì)。

打印機(jī)驅(qū)動(dòng)程序循環(huán)檢查隊(duì)列是否為空。如果不空，出隊(duì)第一個(gè)任務(wù)，發(fā)送打印指令給打印機(jī)，直到隊(duì)列為空或發(fā)生錯(cuò)誤。

優(yōu)點(diǎn)：確保按提交順序打印，公平處理用戶請(qǐng)求。

(2)網(wǎng)絡(luò)請(qǐng)求處理：

步驟：Web服務(wù)器或客戶端應(yīng)用程序接收到的HTTP請(qǐng)求按順序入隊(duì)。

后臺(tái)線程或進(jìn)程循環(huán)出隊(duì)請(qǐng)求，分配資源（如數(shù)據(jù)庫(kù)連接、線程），處理請(qǐng)求，發(fā)送響應(yīng)。

應(yīng)用：管理并發(fā)連接，平滑處理突發(fā)流量。

(3)CPU時(shí)間片調(diào)度（概念性，非具體算法實(shí)現(xiàn)細(xì)節(jié)）：

步驟：多道程序系統(tǒng)中，就緒隊(duì)列存儲(chǔ)等待CPU的進(jìn)程。調(diào)度器按FIFO（或其他策略）從隊(duì)列頭部選擇進(jìn)程分配CPU時(shí)間片。

應(yīng)用：實(shí)現(xiàn)簡(jiǎn)單的輪轉(zhuǎn)調(diào)度（RoundRobin）。

（二）廣度優(yōu)先搜索（Breadth-FirstSearch,BFS）

1.說(shuō)明：BFS是一種用于遍歷或搜索樹(shù)或圖數(shù)據(jù)結(jié)構(gòu)的算法。它從根節(jié)點(diǎn)（或任意起始節(jié)點(diǎn)）開(kāi)始，先訪問(wèn)所有直接鄰居節(jié)點(diǎn)，然后再訪問(wèn)鄰居的鄰居，逐層向外擴(kuò)展。

2.應(yīng)用詳解：

算法步驟（以圖為例）：

a.初始化一個(gè)空隊(duì)列。

b.選擇一個(gè)起始節(jié)點(diǎn)，將其標(biāo)記為已訪問(wèn)，并將其入隊(duì)。

c.當(dāng)隊(duì)列非空時(shí)，執(zhí)行以下操作：

i.出隊(duì)一個(gè)節(jié)點(diǎn)current_node。

ii.處理current_node（例如，輸出、檢查條件）。

iii.遍歷current_node的所有未訪問(wèn)的鄰居節(jié)點(diǎn)neighbor。

iv.對(duì)每個(gè)未訪問(wèn)的neighbor：

a.標(biāo)記neighbor為已訪問(wèn)。

b.將neighbor入隊(duì)。

數(shù)據(jù)結(jié)構(gòu)：隊(duì)列用于存儲(chǔ)待訪問(wèn)的節(jié)點(diǎn)。通常需要一個(gè)集合（如哈希集合或布爾數(shù)組）來(lái)記錄已訪問(wèn)的節(jié)點(diǎn)，以避免重復(fù)訪問(wèn)和無(wú)限循環(huán)。

應(yīng)用：尋找無(wú)權(quán)圖中單源最短路徑、社交網(wǎng)絡(luò)中的好友推薦（基于共同鄰居）、網(wǎng)絡(luò)路由協(xié)議、游戲關(guān)卡設(shè)計(jì)（尋找路徑）。

（三）緩沖區(qū)管理

1.說(shuō)明：隊(duì)列用于在數(shù)據(jù)生產(chǎn)速度和消費(fèi)速度不匹配時(shí)，臨時(shí)存儲(chǔ)數(shù)據(jù)流，起到緩沖和削峰填谷的作用。

2.應(yīng)用詳解：

(1)音頻/視頻流媒體緩沖：

步驟：媒體播放器從服務(wù)器或本地文件讀取數(shù)據(jù)塊（如音頻幀、視頻幀），將其入隊(duì)到緩沖隊(duì)列中。播放器線程從隊(duì)列頭部按順序取出數(shù)據(jù)塊進(jìn)行解碼和播放。

作用：平滑網(wǎng)絡(luò)波動(dòng)或文件讀取速度變化，保證播放的連續(xù)性。隊(duì)列的FIFO特性確保按接收順序播放。

(2)數(shù)據(jù)包轉(zhuǎn)發(fā)（如路由器）：

步驟：路由器接口接收到的數(shù)據(jù)包按順序入隊(duì)到輸入隊(duì)列。路由處理器從隊(duì)列頭部取出數(shù)據(jù)包，查找路由表，決定下一跳，并將數(shù)據(jù)包從輸出隊(duì)列（或另一個(gè)輸入隊(duì)列）發(fā)送出去。

作用：管理高速數(shù)據(jù)流，按序處理和轉(zhuǎn)發(fā)。

（四）隊(duì)列模擬（QueueSimulation）

1.說(shuō)明：使用隊(duì)列數(shù)據(jù)結(jié)構(gòu)模擬現(xiàn)實(shí)生活中的排隊(duì)系統(tǒng)，如銀行取號(hào)、超市結(jié)賬、呼叫中心等，以分析系統(tǒng)性能（如平均等待時(shí)間、隊(duì)列長(zhǎng)度）。

2.應(yīng)用詳解：

步驟（簡(jiǎn)化示例：模擬超市結(jié)賬）：

a.初始化兩個(gè)隊(duì)列：一個(gè)用于顧客排隊(duì)（customer_queue），一個(gè)用于空閑收銀臺(tái)（cashier_queue）。每個(gè)收銀臺(tái)用一個(gè)變量或簡(jiǎn)單結(jié)構(gòu)表示狀態(tài)（空閑或繁忙，以及預(yù)計(jì)完成時(shí)間）。

b.模擬時(shí)間流逝，按一定概率生成新顧客（入隊(duì)到customer_queue）。

c.檢查每個(gè)收銀臺(tái)狀態(tài)：

i.如果收銀臺(tái)空閑，且customer_queue非空，則將隊(duì)首顧客從customer_queue移到該收銀臺(tái)，計(jì)算開(kāi)始服務(wù)時(shí)間。

ii.如果收銀臺(tái)繁忙，更新其預(yù)計(jì)完成時(shí)間。

d.檢查所有收銀臺(tái)，減少繁忙收銀臺(tái)的預(yù)計(jì)完成時(shí)間（模擬時(shí)間流逝）。

e.如果某個(gè)收銀臺(tái)完成服務(wù)，將其標(biāo)記為空閑，并記錄顧客等待時(shí)間等統(tǒng)計(jì)數(shù)據(jù)。

f.重復(fù)步驟b-d，直至模擬結(jié)束時(shí)間。

五、總結(jié)

棧和隊(duì)列作為兩種基礎(chǔ)且強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，憑借其獨(dú)特的LIFO和FIFO操作特性，在計(jì)算機(jī)科學(xué)和軟件工程的眾多領(lǐng)域扮演著不可或缺的角色。棧適用于需要逆序處理、回溯、嵌套管理或函數(shù)調(diào)用棧管理的場(chǎng)景，如遞歸算法模擬、表達(dá)式求值、括號(hào)匹配和瀏覽器歷史記錄。隊(duì)列則適用于需要按順序處理元素、管理等待隊(duì)列、實(shí)現(xiàn)層次遍歷或作為緩沖機(jī)制的場(chǎng)景，如任務(wù)調(diào)度、廣度優(yōu)先搜索、緩沖區(qū)管理和隊(duì)列模擬。深入理解棧和隊(duì)列的操作原理、實(shí)現(xiàn)方式及其應(yīng)用場(chǎng)景，對(duì)于設(shè)計(jì)高效、正確的軟件系統(tǒng)至關(guān)重要。在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問(wèn)題的需求，靈活選擇使用棧、隊(duì)列，甚至結(jié)合使用這兩種結(jié)構(gòu)（例如，使用棧來(lái)存儲(chǔ)臨時(shí)狀態(tài)，再使用隊(duì)列來(lái)按順序處理這些狀態(tài)）。

一、引言

棧和隊(duì)列是兩種重要的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和軟件工程中。它們具有獨(dú)特的操作特性（LIFO和FIFO），能夠解決多種實(shí)際問(wèn)題。本報(bào)告將詳細(xì)介紹棧和隊(duì)列的基本概念、操作方法及其典型應(yīng)用場(chǎng)景，并通過(guò)實(shí)例說(shuō)明其使用價(jià)值。

二、棧和隊(duì)列的基本概念

棧和隊(duì)列是線性數(shù)據(jù)結(jié)構(gòu)，但操作方式不同。

（一）棧（Stack）

1.定義：棧是一種后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，只允許在棧頂進(jìn)行插入和刪除操作。

2.基本操作：

(1)入棧（push）：將元素添加到棧頂。

(2)出棧（pop）：移除并返回棧頂元素。

(3)查看棧頂（peek/top）：返回棧頂元素但不移除。

(4)判斷空棧（isEmpty）：檢查棧是否為空。

（二）隊(duì)列（Queue）

1.定義：隊(duì)列是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，元素從隊(duì)尾入隊(duì)，從隊(duì)頭出隊(duì)。

2.基本操作：

(1)入隊(duì)（enqueue）：將元素添加到隊(duì)尾。

(2)出隊(duì)（dequeue）：移除并返回隊(duì)頭元素。

(3)查看隊(duì)頭（front）：返回隊(duì)頭元素但不移除。

(4)判斷空隊(duì)（isEmpty）：檢查隊(duì)列是否為空。

三、棧的應(yīng)用場(chǎng)景

棧的LIFO特性使其適用于需要逆序處理或回溯的場(chǎng)景。

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

1.說(shuō)明：程序執(zhí)行時(shí)，每次調(diào)用函數(shù)都會(huì)在棧上創(chuàng)建新的棧幀，函數(shù)返回時(shí)棧幀被移除。

2.應(yīng)用：

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

(2)代碼編譯：管理函數(shù)嵌套和變量作用域。

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

1.說(shuō)明：使用棧處理中綴表達(dá)式、后綴表達(dá)式或前綴表達(dá)式。

2.步驟（以中綴轉(zhuǎn)后綴為例）：

(1)初始化一個(gè)運(yùn)算符棧和一個(gè)輸出隊(duì)列。

(2)遍歷表達(dá)式，遇到數(shù)字直接加入隊(duì)列，遇到運(yùn)算符按優(yōu)先級(jí)壓棧。

(3)處理完整表達(dá)式后，將棧中剩余運(yùn)算符加入隊(duì)列。

（三）瀏覽器歷史記錄

1.說(shuō)明：后退按鈕使用棧記錄訪問(wèn)頁(yè)面，最新訪問(wèn)的頁(yè)面在棧頂。

2.操作：

(1)訪問(wèn)新頁(yè)面：壓棧。

(2)點(diǎn)擊后退：出棧并返回上一頁(yè)。

四、隊(duì)列的應(yīng)用場(chǎng)景

隊(duì)列的FIFO特性使其適用于需要按順序處理元素的場(chǎng)景。

（一）任務(wù)調(diào)度

1.說(shuō)明：操作系統(tǒng)使用隊(duì)列管理任務(wù)執(zhí)行順序。

2.應(yīng)用：

(1)打印隊(duì)列：按提交順序處理打印任務(wù)。

(2)網(wǎng)絡(luò)請(qǐng)求處理：管理待處理的HTTP請(qǐng)求。

（二）廣度優(yōu)先搜索（BFS）

1.說(shuō)明：BFS使用隊(duì)列遍歷圖或樹(shù)的節(jié)點(diǎn)。

2.步驟：

(1)將起點(diǎn)節(jié)點(diǎn)入隊(duì)。

(2)循環(huán)直到隊(duì)列為空：出隊(duì)節(jié)點(diǎn)，訪問(wèn)其鄰居節(jié)點(diǎn)，未訪問(wèn)的鄰居入隊(duì)。

（三）緩沖區(qū)管理

1.說(shuō)明：隊(duì)列用于臨時(shí)存儲(chǔ)數(shù)據(jù)流，如音頻或視頻緩沖。

2.應(yīng)用：

(1)音頻播放：按順序播放緩沖區(qū)中的音頻幀。

(2)數(shù)據(jù)包轉(zhuǎn)發(fā)：路由器按接收順序處理數(shù)據(jù)包。

五、總結(jié)

棧和隊(duì)列是基礎(chǔ)但強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，通過(guò)其LIFO和FIFO特性，可高效解決函數(shù)調(diào)用、表達(dá)式求值、任務(wù)調(diào)度、BFS等實(shí)際問(wèn)題。在實(shí)際應(yīng)用中，應(yīng)根據(jù)需求選擇合適的結(jié)構(gòu)，并合理設(shè)計(jì)操作流程。

一、引言

棧和隊(duì)列是兩種基礎(chǔ)且重要的線性數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)科學(xué)和軟件工程的各個(gè)領(lǐng)域都有廣泛的應(yīng)用。它們的核心特性——棧的后進(jìn)先出（LIFO）和隊(duì)列的先進(jìn)先出（FIFO）——使得它們能夠有效地解決許多實(shí)際問(wèn)題，如表達(dá)式求值、函數(shù)調(diào)用管理、任務(wù)調(diào)度、資源分配和搜索算法等。本報(bào)告將深入探討棧和隊(duì)列的基本概念、關(guān)鍵操作及其典型應(yīng)用場(chǎng)景，并通過(guò)更詳細(xì)的步驟和實(shí)例說(shuō)明其使用價(jià)值和實(shí)現(xiàn)方式。

二、棧和隊(duì)列的基本概念

棧和隊(duì)列是線性數(shù)據(jù)結(jié)構(gòu)，意味著元素具有一對(duì)一的邏輯關(guān)系，但它們的操作受限，分別遵循LIFO和FIFO原則。

（一）棧（Stack）

1.定義：棧是一種僅允許在棧頂進(jìn)行插入（push）和刪除（pop）操作的數(shù)據(jù)結(jié)構(gòu)。它遵循后進(jìn)先出（LIFO,Last-In-First-Out）的原則，即最后被添加的元素將是第一個(gè)被移除的元素。棧是一種“操作受限”的線性表。

2.基本數(shù)據(jù)結(jié)構(gòu)表示：

(1)數(shù)組實(shí)現(xiàn)：使用一個(gè)一維數(shù)組來(lái)存儲(chǔ)棧元素，并維護(hù)一個(gè)指針（通常稱為棧頂指針，top）來(lái)指示棧頂元素的位置。初始時(shí)，top通常設(shè)置為-1，表示棧為空。

(2)鏈表實(shí)現(xiàn)：使用鏈節(jié)點(diǎn)鏈接各個(gè)元素，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。維護(hù)一個(gè)指向棧頂節(jié)點(diǎn)的指針（head或top）。

3.基本操作詳解：

(1)入棧（push）：將一個(gè)新元素添加到棧頂。

數(shù)組實(shí)現(xiàn)步驟：

a.檢查棧是否已滿（通常top==數(shù)組長(zhǎng)度-1）。如果滿，則無(wú)法入棧（發(fā)生棧溢出）。

b.top自增（top++）。

c.將新元素存儲(chǔ)在數(shù)組中索引為top的位置（array[top]=element）。

鏈表實(shí)現(xiàn)步驟：

a.創(chuàng)建一個(gè)新節(jié)點(diǎn)，存儲(chǔ)元素?cái)?shù)據(jù)。

b.將新節(jié)點(diǎn)的next指針指向當(dāng)前棧頂節(jié)點(diǎn)（top節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)）。

c.將棧頂指針（top）更新為新節(jié)點(diǎn)。

(2)出棧（pop）：移除并返回棧頂元素。

數(shù)組實(shí)現(xiàn)步驟：

a.檢查棧是否為空（通常top==-1）。如果空，則無(wú)法出棧（發(fā)生棧下溢）。

b.獲取棧頂元素（element=array[top]）。

c.top自減（top--）。

d.返回獲取的元素。

鏈表實(shí)現(xiàn)步驟：

a.檢查棧是否為空（top==NULL）。如果空，則無(wú)法出棧。

b.獲取棧頂元素（element=top->data）。

c.保存棧頂指針的下一個(gè)節(jié)點(diǎn)（next_node=top->next）。

d.釋放當(dāng)前棧頂節(jié)點(diǎn)內(nèi)存（或使其可被垃圾回收）。

e.將棧頂指針（top）更新為next_node。

f.返回獲取的元素。

(3)查看棧頂（peek或top）：返回棧頂元素的值，但不移除它。

數(shù)組實(shí)現(xiàn)：直接返回array[top]的值（前提是棧非空）。

鏈表實(shí)現(xiàn)：返回top->data的值（前提是棧非空）。

(4)判斷?？眨╥sEmpty）：檢查棧是否不包含任何元素。

數(shù)組實(shí)現(xiàn)：判斷top==-1。

鏈表實(shí)現(xiàn)：判斷top==NULL。

（二）隊(duì)列（Queue）

1.定義：隊(duì)列是一種只允許在隊(duì)頭（front）進(jìn)行刪除（dequeue）操作、在隊(duì)尾（rear）進(jìn)行插入（enqueue）操作的數(shù)據(jù)結(jié)構(gòu)。它遵循先進(jìn)先出（FIFO,First-In-First-Out）的原則，即最早被添加的元素將是第一個(gè)被移除的元素。隊(duì)列也是一種“操作受限”的線性表。

2.基本數(shù)據(jù)結(jié)構(gòu)表示：

(1)數(shù)組實(shí)現(xiàn)：使用一個(gè)一維數(shù)組來(lái)存儲(chǔ)隊(duì)列元素，并維護(hù)兩個(gè)指針：隊(duì)頭指針（front）和隊(duì)尾指針（rear）。初始時(shí)，通常front和rear都設(shè)置為0，表示隊(duì)列為空。

(2)鏈表實(shí)現(xiàn)：使用鏈節(jié)點(diǎn)鏈接各個(gè)元素，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。維護(hù)兩個(gè)指針：隊(duì)頭指針（front）指向隊(duì)列第一個(gè)元素，隊(duì)尾指針（rear）指向隊(duì)列最后一個(gè)元素。

3.基本操作詳解：

(1)入隊(duì)（enqueue）：將一個(gè)新元素添加到隊(duì)尾。

數(shù)組實(shí)現(xiàn)步驟：

a.檢查隊(duì)列是否已滿（通常(rear+1)%array_length==front）。如果滿，則無(wú)法入隊(duì)（發(fā)生隊(duì)列溢出）。

b.將新元素存儲(chǔ)在數(shù)組中索引為rear的位置（array[rear]=element）。

c.rear指針向前移動(dòng)（rear=(rear+1)%array_length）。使用模運(yùn)算實(shí)現(xiàn)循環(huán)隊(duì)列。

鏈表實(shí)現(xiàn)步驟：

a.創(chuàng)建一個(gè)新節(jié)點(diǎn)，存儲(chǔ)元素?cái)?shù)據(jù)。

b.如果隊(duì)列為空（front==NULL），則新節(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾，讓front和rear都指向新節(jié)點(diǎn)。

c.否則，將新節(jié)點(diǎn)的next指針指向當(dāng)前隊(duì)尾節(jié)點(diǎn)（rear->next）。

d.將隊(duì)尾指針（rear）更新為新節(jié)點(diǎn)。

(2)出隊(duì)（dequeue）：移除并返回隊(duì)頭元素。

數(shù)組實(shí)現(xiàn)步驟：

a.檢查隊(duì)列是否為空（通常front==rear）。如果空，則無(wú)法出隊(duì)（發(fā)生隊(duì)列下溢）。

b.獲取隊(duì)頭元素（element=array[front]）。

c.front指針向前移動(dòng)（front=(front+1)%array_length）。使用模運(yùn)算實(shí)現(xiàn)循環(huán)隊(duì)列。

d.返回獲取的元素。

鏈表實(shí)現(xiàn)步驟：

a.檢查隊(duì)列是否為空（front==NULL）。如果空，則無(wú)法出隊(duì)。

b.獲取隊(duì)頭元素（element=front->data）。

c.保存隊(duì)頭指針的下一個(gè)節(jié)點(diǎn)（next_node=front->next）。

d.釋放當(dāng)前隊(duì)頭節(jié)點(diǎn)內(nèi)存（或使其可被垃圾回收）。

e.將隊(duì)頭指針（front）更新為next_node。

f.如果更新后的front指針為NULL（原隊(duì)頭是唯一節(jié)點(diǎn)），則需要同時(shí)將rear指針也設(shè)置為NULL。

g.返回獲取的元素。

(3)查看隊(duì)頭（front或peek）：返回隊(duì)頭元素的值，但不移除它。

數(shù)組實(shí)現(xiàn)：直接返回array[front]的值（前提是隊(duì)列非空）。

鏈表實(shí)現(xiàn)：返回front->data的值（前提是隊(duì)列非空）。

(4)判斷隊(duì)空（isEmpty）：檢查隊(duì)列是否不包含任何元素。

數(shù)組實(shí)現(xiàn)：判斷front==rear。

鏈表實(shí)現(xiàn)：判斷front==NULL。

三、棧的應(yīng)用場(chǎng)景

棧的LIFO特性使其適用于需要逆序處理、回溯或管理嵌套關(guān)系的場(chǎng)景。

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

1.說(shuō)明：在程序執(zhí)行過(guò)程中，每當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，操作系統(tǒng)會(huì)為該函數(shù)創(chuàng)建一個(gè)臨時(shí)的數(shù)據(jù)結(jié)構(gòu)（棧幀或激活記錄），其中包含函數(shù)的局部變量、參數(shù)、返回地址等信息。這個(gè)棧幀被壓入函數(shù)調(diào)用棧中。當(dāng)函數(shù)執(zhí)行完畢并返回時(shí)，對(duì)應(yīng)的棧幀被彈出并銷毀。函數(shù)調(diào)用棧天然地支持遞歸調(diào)用和函數(shù)嵌套。

2.應(yīng)用詳解：

(1)遞歸算法實(shí)現(xiàn)：

步驟：將遞歸問(wèn)題轉(zhuǎn)化為可由棧模擬的迭代問(wèn)題。

例子：計(jì)算階乘n!。

a.遞歸實(shí)現(xiàn)（偽代碼）：

functionfactorial(n):

ifn==0:

return1

else:

returnnfactorial(n-1)

b.棧模擬實(shí)現(xiàn)（偽代碼）：

stack=emptystack

result=1

forifrom1ton:

stack.push(i)

whilenotstack.isEmpty():

value=stack.pop()

result=value

returnresult

優(yōu)勢(shì)：避免遞歸深度過(guò)大導(dǎo)致的遞歸調(diào)用棧溢出，轉(zhuǎn)換為迭代后更可控。

(2)代碼編譯與解釋執(zhí)行：

步驟：編譯器或解釋器在處理程序時(shí)，使用棧來(lái)管理函數(shù)嵌套、流程控制（如if-else,switch-case）和局部變量作用域。

應(yīng)用：在解析表達(dá)式、執(zhí)行語(yǔ)句時(shí)，棧用于暫存中間結(jié)果和操作符。

(3)撤銷/重做（Undo/Redo）功能：

步驟：用戶每執(zhí)行一個(gè)操作，將該操作的相關(guān)狀態(tài)或指令壓入棧中。執(zhí)行撤銷時(shí)，出棧并執(zhí)行相反操作；執(zhí)行重做時(shí)，將撤銷的操作再次壓回棧并執(zhí)行。

應(yīng)用：文本編輯器、繪圖軟件等。

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

1.說(shuō)明：使用?？梢愿咝У赜?jì)算中綴表達(dá)式（如3+42/(1-5)）、后綴表達(dá)式（如34+215-/）或前綴表達(dá)式（波蘭式，如+342-15）。

2.應(yīng)用詳解：

(1)中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式（逆波蘭式）算法（ShuntingYard算法）步驟：

初始化一個(gè)空的操作符棧和一個(gè)空的后綴表達(dá)式隊(duì)列（或列表）。

從左到右掃描中綴表達(dá)式的每個(gè)字符（token）：

a.如果是操作數(shù)（數(shù)字或變量），直接將其加入后綴表達(dá)式隊(duì)列。

b.如果是左括號(hào)'('，將其壓入操作符棧。

c.如果是右括號(hào)')'：

i.彈出并丟棄棧中的操作符，加入后綴表達(dá)式隊(duì)列，直到遇到左括號(hào)'('。彈出左括號(hào)，但不加入隊(duì)列。

ii.如果棧頂是函數(shù)名（如sin,cos），則將其彈出并加入隊(duì)列（如果需要）。

d.如果是操作符（如+,-,,/）：

i.彈出棧中所有優(yōu)先級(jí)高于或等于當(dāng)前操作符的操作符，并加入后綴表達(dá)式隊(duì)列。

ii.如果棧頂是左括號(hào)'('，則將當(dāng)前操作符壓入棧。

iii.將當(dāng)前操作符壓入操作符棧。

掃描結(jié)束后，彈出并加入操作符棧中剩余的所有操作符。

(2)后綴表達(dá)式求值算法步驟：

初始化一個(gè)空棧。

從左到右掃描后綴表達(dá)式的每個(gè)token：

a.如果是操作數(shù)，將其壓入棧。

b.如果是操作符，彈出棧頂?shù)膔equired_number個(gè)操作數(shù)（順序不重要，因?yàn)闂Ｊ荓IFO），執(zhí)行運(yùn)算（操作符+第一個(gè)操作數(shù)+第二個(gè)操作數(shù)），將結(jié)果壓回棧。

掃描結(jié)束后，棧頂元素即為表達(dá)式的值。

(3)前綴表達(dá)式求值（波蘭式）算法步驟：

需要先反轉(zhuǎn)前綴表達(dá)式，使其從右到左成為后綴表達(dá)式形式。

然后應(yīng)用后綴表達(dá)式求值算法步驟進(jìn)行計(jì)算。

（三）瀏覽器歷史記錄與后退功能

1.說(shuō)明：現(xiàn)代瀏覽器通常使用棧來(lái)管理用戶訪問(wèn)的頁(yè)面歷史。用戶訪問(wèn)的每個(gè)頁(yè)面URL或會(huì)話狀態(tài)被壓入一個(gè)棧（稱為“后退?！保?。點(diǎn)擊瀏覽器的后退按鈕相當(dāng)于從棧頂彈出當(dāng)前頁(yè)面，返回到前一個(gè)頁(yè)面。

2.應(yīng)用詳解：

(1)前進(jìn)/后退操作：

訪問(wèn)新頁(yè)面：將新頁(yè)面的標(biāo)識(shí)（如URL或會(huì)話指針）壓入后退棧。

點(diǎn)擊后退：檢查后退棧是否為空。如果不空，彈出棧頂元素，更新瀏覽器顯示的當(dāng)前頁(yè)面，并將后退棧的下一個(gè)元素（如果存在）設(shè)置為可用的“前進(jìn)?！钡臈ｍ敗?/p>

點(diǎn)擊前進(jìn)：如果存在“前進(jìn)?！鼻曳强?，彈出棧頂元素，更新瀏覽器顯示，并將該元素移回“后退棧”。

(2)雙擊后退/前進(jìn)：連續(xù)點(diǎn)擊可能涉及連續(xù)彈出棧頂元素。

（四）括號(hào)匹配

1.說(shuō)明：檢查一個(gè)字符串（如代碼、表達(dá)式）中的括號(hào)（如'(',')','{','}','[',']'）是否正確匹配和配對(duì)。

2.應(yīng)用詳解：

步驟：

a.初始化一個(gè)空棧。

b.從左到右掃描字符串的每個(gè)字符：

i.如果是開(kāi)括號(hào)（'(','{','['），將其壓入棧。

ii.如果是閉括號(hào)（')','}',']'）：

a.檢查棧是否為空。如果為空，則沒(méi)有對(duì)應(yīng)的開(kāi)括號(hào)，匹配失敗。

b.彈出棧頂?shù)拈_(kāi)括號(hào)。

c.檢查彈出的開(kāi)括號(hào)是否與當(dāng)前的閉括號(hào)類型匹配（'('與')'，'{'與'}'，'['與']'）。如果不匹配，匹配失敗。

c.掃描結(jié)束后，檢查棧是否為空。如果棧非空，說(shuō)明有未匹配的開(kāi)括號(hào)，匹配失敗。如果棧為空，則所有括號(hào)匹配成功。

應(yīng)用：編譯器錯(cuò)誤檢查、語(yǔ)法分析、驗(yàn)證代碼或配置文件格式。

四、隊(duì)列的應(yīng)用場(chǎng)景

隊(duì)列的FIFO特性使其適用于需要按順序處理元素、管理等待隊(duì)列或進(jìn)行層次遍歷的場(chǎng)景。

（一）任務(wù)調(diào)度與資源管理

1.說(shuō)明：操作系統(tǒng)和應(yīng)用程序使用隊(duì)列來(lái)管理待處理的任務(wù)或請(qǐng)求，確保它們按照請(qǐng)求的順序被處理。

2.應(yīng)用詳解：

(1)打印隊(duì)列：

步驟：用戶提交打印任務(wù)時(shí)，任務(wù)信息（如文件路徑、打印份數(shù)、紙張?jiān)O(shè)置）被入隊(duì)。

打印機(jī)驅(qū)動(dòng)程序循環(huán)檢查隊(duì)列是否為空。如果不空，出隊(duì)第一個(gè)任務(wù)，發(fā)送打印指令給打印機(jī)，直到隊(duì)列為空或發(fā)生錯(cuò)誤。

優(yōu)點(diǎn)：確保按提交順序打印，公平處理用戶請(qǐng)求。

(2)網(wǎng)絡(luò)請(qǐng)求處理：

步驟：Web服務(wù)器或客戶端應(yīng)用程序接收到的HTTP請(qǐng)求按順序入隊(duì)。

后臺(tái)線程或進(jìn)程循環(huán)出隊(duì)請(qǐng)求，分配資源（如數(shù)據(jù)庫(kù)連接、線程），處理請(qǐng)求，發(fā)送響應(yīng)。

應(yīng)用：管理并發(fā)連接，平滑處理突發(fā)流量。

(3)CPU時(shí)間片調(diào)度（概念性，非具體算法實(shí)現(xiàn)細(xì)節(jié)）：

步驟：多道程序系統(tǒng)中，就緒隊(duì)列存儲(chǔ)等待C