2006年軟考程序員數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)筆記

置空隊(duì) ：InitQueue(Q)
判隊(duì)空： QueueEmpty(Q)
判隊(duì)滿： QueueFull(Q)
入隊(duì) ： EnQueue(Q,x)
出隊(duì) ： DeQueue(Q)
取隊(duì)頭元素： QueueFront(Q),不同與出隊(duì)，隊(duì)頭元素仍然保留

--------------------------------------------------------------------------------

隊(duì)列也有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)，前者稱順序隊(duì)列，后者為鏈隊(duì)。
對(duì)于順序隊(duì)列，我們要理解"假上溢"的現(xiàn)象。
我們現(xiàn)實(shí)中的隊(duì)列比如人群排隊(duì)買票，隊(duì)伍中的人是可以一邊進(jìn)去從另一頭出來的，除非地方不夠，總不會(huì)有"溢出"的現(xiàn)象，相似地，當(dāng)隊(duì)列中元素完全充滿這個(gè)向量空間時(shí)，再入隊(duì)自然就會(huì)上溢，如果隊(duì)列中已沒有元素，那么再要出隊(duì)也會(huì)下溢。
那么"假上溢"就是怎么回事呢? 
因?yàn)樵谶@里，我們的隊(duì)列是存儲(chǔ)在一個(gè)向量空間里，在這一段連續(xù)的存儲(chǔ)空間中，由一個(gè)隊(duì)列頭指針和一個(gè)尾指針表示這個(gè)隊(duì)列，當(dāng)頭指針和尾指針指向同一個(gè)位置時(shí)，隊(duì)列為空，也就是說，隊(duì)列是由兩個(gè)指針中間的元素構(gòu)成的。在隊(duì)列中，入隊(duì)和出隊(duì)并不是象現(xiàn)實(shí)中，元素一個(gè)個(gè)地向前移動(dòng)，走完了就沒有了,而是指針在移動(dòng)，當(dāng)出隊(duì)操作時(shí)，頭指針向前(即向量空間的尾部)增加一個(gè)位置，入隊(duì)時(shí)，尾指針向前增加一個(gè)位置，在某種情況下，比如說進(jìn)一個(gè)出一個(gè)，兩個(gè)指針就不停地向前移動(dòng)，直到隊(duì)列所在向量空間的尾部，這時(shí)再入隊(duì)的話，尾指針就要跑到向量空間外面去了，僅管這時(shí)整個(gè)向量空間是空的，隊(duì)列也是空的，卻產(chǎn)生了"上溢"現(xiàn)象，這就是假上溢。
為了克服這種現(xiàn)象造成的空間浪費(fèi)，我們引入循環(huán)向量的概念，就好比是把向量空間彎起來，形成一個(gè)頭尾相接的環(huán)形，這樣，當(dāng)存于其中的隊(duì)列頭尾指針移到向量空間的上界(尾部)時(shí)，再加1的操作(入隊(duì)或出隊(duì))就使指針指向向量的下界，也就是從頭開始。這時(shí)的隊(duì)列就稱循環(huán)隊(duì)列。
通常我們應(yīng)用的大都是循環(huán)隊(duì)列。由于循環(huán)的原因，光看頭尾指針重疊在一起我們并不能判斷隊(duì)列是空的還是滿的，這時(shí)就需要處理一些邊界條件，以區(qū)別隊(duì)列是空還是滿。方法至少有三種，一種是另設(shè)一個(gè)布爾變量來判斷(就是請(qǐng)別人看著，是空還是滿由他說了算)，第二種是少用一個(gè)元素空間，當(dāng)入隊(duì)時(shí)，先測試入隊(duì)后尾指針是不是會(huì)等于頭指針，如果相等就算隊(duì)已滿，不許入隊(duì)。第三種就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中的元素的總數(shù)，這樣就可以隨時(shí)知道隊(duì)列的長度了，只要隊(duì)列中的元素個(gè)數(shù)等于向量空間的長度，就是隊(duì)滿。
以上是順序隊(duì)列，我們要掌握相應(yīng)算法以解決簡單應(yīng)用問題。

--------------------------------------------------------------------------------
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列，一個(gè)鏈隊(duì)列就是一個(gè)操作受限的單鏈表。為了便于在表尾進(jìn)行插入(入隊(duì))的操作，在表尾增加一個(gè)尾指針，一個(gè)鏈隊(duì)列就由一個(gè)頭指針和一個(gè)尾指針唯一地確定。鏈隊(duì)列不存在隊(duì)滿和上溢的問題。在鏈隊(duì)列的出隊(duì)算法中，要注意當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，出隊(duì)后要同進(jìn)修改頭尾指針并使隊(duì)列變空。

--------------------------------------------------------------------------------
3.棧和隊(duì)列的應(yīng)用(領(lǐng)會(huì))
教材中舉了幾個(gè)例子，對(duì)于我們初學(xué)者來說，看上去比較繁，我們只要掌握一點(diǎn)，那就是，對(duì)于什么情況下用棧和隊(duì)列作為解決問題的數(shù)據(jù)結(jié)構(gòu)。
判斷的要點(diǎn)就是：如果這個(gè)問題滿足后進(jìn)先出(LIFO)的原則，就可以使用棧來處理。如果這個(gè)問題滿足先進(jìn)先出(FIFO)的原則，就可以使用隊(duì)列來處理。
比如簡單的說，有一個(gè)數(shù)組序列，我們輸入時(shí)按順序輸入，但是輸出時(shí)需要逆序輸出，那么它就可以利用棧來處理，把這個(gè)數(shù)組存入一個(gè)棧中就可以容易地按逆序輸出結(jié)果了。
第三章 線性表習(xí)題及答案 

--------------------------------------------------------------------------------
一、基礎(chǔ)知識(shí)題
(答案及點(diǎn)評(píng)) 3.1 設(shè)將整數(shù)1，2，3，4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序夾入其中，請(qǐng)回答下述問題： 
(1)若入、出棧次序?yàn)镻ush(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),則出棧的數(shù)字序列為何(這里Push(i)表示i進(jìn)棧，Pop( )表示出棧)? 
(2) 能否得到出棧序列1423和1432?并說明為什么不能得到或者如何得到。 
(3)請(qǐng)分析 1，2 ，3 ，4 的24種排列中，哪些序列是可以通過相應(yīng)的入出棧操作得到的。 

--------------------------------------------------------------------------------
(答案及點(diǎn)評(píng)) 3.2 鏈棧中為何不設(shè)置頭結(jié)點(diǎn)?
答：鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)行操作的，如果加了頭結(jié)點(diǎn)，等于要對(duì)頭結(jié)點(diǎn)之后的結(jié)點(diǎn)進(jìn)行操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可以了。 

--------------------------------------------------------------------------------
(答案及點(diǎn)評(píng)) 3.3 循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么? 如何判別它的空和滿? 

3.3 答：循環(huán)隊(duì)列的優(yōu)點(diǎn)是：它可以克服順序隊(duì)列的"假上溢"現(xiàn)象，能夠使存儲(chǔ)隊(duì)列的向量空間得到充分的利用。判別循環(huán)隊(duì)列的"空"或"滿"不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是另設(shè)一布爾變量來區(qū)別隊(duì)列的空和滿。二是少用一個(gè)元素的空間。每次入隊(duì)前測試入隊(duì)后頭尾指針是否會(huì)重合，如果會(huì)重合就認(rèn)為隊(duì)列已滿。三是設(shè)置一計(jì)數(shù)器記錄隊(duì)列中元素總數(shù)，不僅可判別空或滿，還可以得到隊(duì)列中元素的個(gè)數(shù)。