C語言中文網 目錄
首頁 > 編程筆記 > C++筆記 閱讀:224

棧及其特點和應用(C++詳解版)

像數組或鏈表一樣,也是一種數據結構,它包含一系列元素。

但是,與數組和鏈表不同的是,棧是一個后進先出(LIFO)的結構,這意味著當一個程序從棧中檢索元素時,插入到棧中的最后一個元素是第一個被檢索的元素(同樣,插入的第一個元素是最后一個被檢索的元素)。

在想象一個棧的工作方式時,可以想象一下餐廳流水線開始時的一堆盤子。當餐廳的工作人員補充餐盤時,他或她放入的第一個盤子將是最后一個被取走的,如圖 1 所示。

棧的后進先出方式就像餐廳盤子的取用方式
圖 1 棧的后進先出方式就像餐廳盤子的取用方式

餐廳中一堆盤子的LIFO特性也是棧數據結構的主要特征。放在棧上的最后一個數據元素是從棧中檢索的第一個數據。

有以下兩種類型的棧數據結構:
  1. 靜態棧:又稱"順序棧"。具有固定大小,并以數組形式實現;
  2. 動態棧:又稱"鏈棧"。可根據需要增長,并以鏈表形式實現;

棧的應用

如果某個算法需要首先處理序列中最后保存的元素,那么棧對于這種算法而言是非常有用的數據結構。

例如,計算機系統在執行程序時就會使用棧。當某個函數被調用時,計算機系統會將程序的返回地址、函數的參數以及函數的局部變量保存在棧中。當函數返回時,這些局部變量、參數和返回的地址等都將被從棧上刪除。

棧操作

棧有兩個主要操作:入棧(push,也被稱為壓棧)和出棧(pop,也被稱為彈棧)。

入棧操作會導致一個值被存儲,或者被壓入棧。例如,假設有一個空的整數棧,最多可以保存 3 個值。有了這個棧,則可以執行以下入棧操作:

push(5);
push(10);
push(15);

圖 2 顯示了在執行這些入棧操作之后的棧狀態。

入棧操作圖解
圖 2 入棧操作圖解

出棧操作將從棧中檢索(繼而刪除)一個值。假設要在如圖 2 所示的棧上執行 3 個連續的出棧操作,結果將如圖 3 所示。


圖 3 出棧操作圖解

從圖 3 可以看出,最后的出棧操作可將棧清空。

對于靜態和動態棧,都需要一個布爾 isEmpty 操作。當棧為空時,isEmpty 操作返回 true,否則返回 false。通過調用該操作,程序員可以在嘗試執行出棧操作之前確認棧上有東西。

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo