棧

2019-11-08 03:14:17

字體：大中小

供稿：網(wǎng)友

定義：棧是限定僅在表頭進行插入和刪除操作的線性表。要搞清楚這個概念，首先要明白”棧“原來的意思，如此才能把握本質(zhì)。"棧“者,存儲貨物或供旅客住宿的地方,可引申為倉庫、中轉(zhuǎn)站，所以引入到計算機領(lǐng)域里，就是指數(shù)據(jù)暫時存儲的地方，所以才有進棧、出棧的說法。首先系統(tǒng)或者數(shù)據(jù)結(jié)構(gòu)棧中數(shù)據(jù)內(nèi)容的讀取與插入（壓入push和彈出pop）是兩回事！插入是增加數(shù)據(jù)，彈出是刪除數(shù)據(jù) ，這些操作只能從棧頂即最低地址作為約束的接口界面入手操作，但讀取棧中的數(shù)據(jù)是隨便的沒有接口約束之說。很多人都誤解這個理念從而對棧產(chǎn)生困惑。^[1]而系統(tǒng)棧在計算機體系結(jié)構(gòu)中又起到一個跨部件交互的媒介區(qū)域的作用即 cpu 與內(nèi)存的交流通道，cpu只從系統(tǒng)給我們自己編寫的應(yīng)用程序所規(guī)定的棧入口線性地讀取執(zhí)行指令，用一個形象的詞來形容它就是pipeline（管道線、流水線）。cpu內(nèi)部交互具體參見 EU與BIU的概念介紹。棧作為一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進行插入和刪除操作的特殊線性表。它按照先進后出的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）。棧具有記憶作用，對棧的插入與刪除操作中，不需要改變棧底指針。棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數(shù)為零時稱為空棧。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。棧也稱為后進先出表。棧可以用來在函數(shù)調(diào)用的時候存儲斷點，做遞歸時要用到棧！ 1．進棧（PUSH）算法①若TOP≥n時，則給出溢出信息，作出錯處理（進棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）；②置TOP=TOP+1（棧指針加1，指向進棧地址）；③S(TOP)=X，結(jié)束（X為新進棧的元素）；2．退棧（POP）算法①若TOP≤0，則給出下溢信息，作出錯處理(退棧前先檢查是否已為空棧，空則下溢；不空則作②)；②X=S(TOP)，（退棧后的元素賦給X）：③TOP=TOP-1，結(jié)束（棧指針減1，指向棧頂）。

1. 棧的示意圖