第三章 棧和隊列
本章介紹的是 棧 和 隊列 的邏輯結構定義及在兩種存儲結構(順序存儲結構和鏈式存儲結構)上如何實現 棧和隊列的基本運算 本章的 重點 是掌握棧和隊列在兩種存儲結構上實現的基本運算 難點 是循環隊列中對邊界條件的處理
棧的邏輯結構存儲結構及其相關算法( 綜合應用 ):
棧 的邏輯結構和我們先前學過的 線性表 相同如果它是非空的則有且只有一個 開始結點 有且只能有一個 終端結點 其它的結點前後所相鄰的也只能是一個結點( 直接前趨 和 直接後繼 )但是棧的運算規則與線性表相比有更多的限制 棧(Stack) 是 僅限制在表的一端進行插入和刪除運算的線性表 通常稱插入刪除這一端為 棧頂 另一端稱為 棧底 表中無元素時為 空棧 棧的修改是按後進先出的原則進行的我們又稱棧為LIFO表(Last In First Out)
棧的基本運算有六種
構造空棧InitStack(S)
判棧空: StackEmpty(S)
判棧滿 StackFull(S)
進棧 Push(Sx)可形象地理解為壓入這時棧中會多一個元素
退棧 Pop(S) 可形象地理解為彈出彈出後棧中就無此元素了
取棧頂元素StackTop(S)不同與彈出只是使用棧頂元素的值該元素仍在棧頂不會改變
由於棧也是線性表因此線性表的存儲結構對棧也適用通常棧有 順序棧 和 鏈棧 兩種存儲結構這兩種存儲結構的不同則使得實現棧的基本運算的算法也有所不同
我們要了解的是在 順序棧 中有 上溢 和 下溢 的概念順序棧好比一個盒子我們在裡頭放了一疊書當我們要用書的話只能從第一本開始拿(你會把盒子翻過來嗎?真聰明^^)那麼當我們把書本放到這個棧中超過盒子的頂部時就放不下了(疊上去的不算哼哼)這時就是上溢 上溢也就是棧頂指針指出棧的外面 顯然是出錯了反之當棧中已沒有書時我們再去拿看看沒書把盒子拎起來看看盒底還是沒有這就是 下溢 下溢本身可以表示棧為空棧 因此可以用它來作為控制轉移的條件
鏈棧 則沒有上溢的限制它就象是一條一頭固定的鏈子可以在活動的一頭自由地增加鏈環(結點)而不會溢出 鏈棧不需要在頭部附加頭結點 因為棧都是在頭部進行操作的如果加了頭結點等於要在頭結點之後的結點進行操作反而使算法更復雜所以只要有鏈表的頭指針就可以了
以上兩種存儲結構的棧的基本操作算法是不同的我們主要 要學會進棧和退棧的基本算法以解決簡單的應用問題
隊列的邏輯結構存儲結構及其相關算法( 綜合應用 )
隊列(Queue念Q音) 也是一種運算受限的 線性表 它的運算限制與棧不同是兩頭都有限制 插入只能在表的一端進行(只進不出)而刪除只能在表的另一端進行(只出不進) 允許刪除的一端稱為 隊頭(rear) 允許插入的一端稱為 隊尾 (Front) 隊列的操作原則是先進先出的所以隊列又稱作 FIFO 表(First In First Out)
隊列的基本運算也有六種
置空隊 InitQueue(Q)
判隊空 QueueEmpty(Q)
判隊滿 QueueFull(Q)
入隊 EnQueue(Qx)
出隊 DeQueue(Q)
取隊頭元素 QueueFront(Q)不同與出隊隊頭元素仍然保留
隊列 也有順序存儲和鏈式存儲兩種存儲結構前者稱 順序隊列 後者為 鏈隊
對於順序隊列我們要理解 假上溢 的現象
我們現實中的隊列比如人群排隊買票隊伍中的人是可以一邊進去從另一頭出來的除非地方不夠總不會有溢出的現象相似地當隊列中元素完全充滿這個向量空間時再入隊自然就會上溢如果隊列中已沒有元素那麼再要出隊也會下溢
那麼假上溢就是怎麼回事呢?
因為在這裡我們的隊列是存儲在一個向量空間裡在這一段連續的存儲空間中由一個隊列頭指針和一個尾指針表示這個隊列當頭指針和尾指針指向同一個位置時隊列為空也就是說 隊列是由兩個指針中間的元素構成的 在隊列中入隊和出隊並不是象現實中元素一個個地向前移動走完了就沒有了而是 指針在移動 當出隊操作時頭指針向前(即向量空間的尾部)增加一個位置入隊時尾指針向前增加一個位置在某種情況下比如說進一個出一個兩個指針就不停地向前移動直到隊列所在向量空間的尾部這時再入隊的話尾指針就要跑到向量空間外面去了僅管這時整個向量空間是空的隊列也是空的卻產生了上溢現象這就是假上溢
為了克服這種現象造成的空間浪費我們引入 循環向量 的概念就好比是把向量空間彎起來形成一個頭尾相接的環形這樣當存於其中的隊列頭尾指針移到向量空間的上界(尾部)時再加的操作(入隊或出隊)就使指針指向向量的下界也就是從頭開始這時的隊列就稱 循環隊列
通常我們應用的大都是循環隊列由於循環的原因光看頭尾指針重疊在一起我們並不能判斷隊列是空的還是滿的這時就需要處理一些 邊界條件 以區別隊列是空還是滿方法至少有三種一種是另設一個布爾變量來判斷(就是請別人看著是空還是滿由他說了算)第二種是少用一個元素空間當入隊時先測試入隊後尾指針是不是會等於頭指針如果相等就算隊已滿不許入隊第三種就是用一個計數器記錄隊列中的元素的總數這樣就可以隨時知道隊列的長度了只要隊列中的元素個數等於向量空間的長度就是隊滿
以上是 順序隊列 我們 要掌握相應算法以解決簡單應用問題
隊列的鏈式存儲結構稱為鏈隊列一個鏈隊列就是一個操作受限的單鏈表為了便於在表尾進行插入(入隊)的操作在表尾增加一個尾指針 一個鏈隊列就由一個頭指針和一個尾指針唯一地確定 鏈隊列不存在隊滿和上溢的問題在鏈隊列的出隊算法中要 注意 當原隊中只有一個結點時出隊後要同進修改頭尾指針並使隊列變空
棧和隊列的應用( 領會 )
教材中舉了幾個例子對於我們初學者來說看上去比較繁我們只要掌握一點那就是對於什麼情況下用棧和隊列作為解決問題的數據結構
判斷的要點就是 如果這個問題滿足 後進先出(LIFO) 的原則就可以使用 棧 來處理如果這個問題滿足 先進先出(FIFO) 的原則就可以使用 隊列 來處理
比如簡單的說有一個數組序列我們輸入時按順序輸入但是輸出時需要逆序輸出那麼它就可以利用棧來處理把這個數組存入一個棧中就可以容易地按逆序輸出結果了
第三章 棧和隊列 復習要點
本章要點是
棧的定義其邏輯結構特征棧的六種基本運算棧的上溢下溢的概念
隊列的邏輯結構隊列的基本運算;循環隊列的邊界條件處理;
以上各種基本運算算法的實現算法的簡單應用
可能出的題型有填空選擇簡答算法等如:
棧和隊列是的線性表;
有一棧元素ABCD只能依次進棧 則出棧序列中以下哪個是不可能得到的()
A DCBA
B CBAD
C ABCD
D DCAB
試寫出隊列中的出隊算法;
等等
From:http://tw.wingwit.com/Article/program/sjjg/201311/23678.html
