數據就是指能夠被計算機識別、存儲和加工處理的信息的載體。
數據元素是數據的基本單位，有時一個數據元素可以由若干個數據項組成。數據項是具有獨立含義的最小標識單位。如整數這個集合中，10這個數就可稱是一個數據元素.又比如在一個數據庫(關系式數據庫)中，一個記錄可稱為一個數據元素，而這個元素中的某一字段就是一個數據項。
數據結構的定義雖然沒有標準，但是它包括以下三方面內容：邏輯結構、存儲結構、和對數據的操作。這一段比較重要，我用自己的語言來說明一下，大家看看是不是這樣。
比如一個表(數據庫)，我們就稱它為一個數據結構，它由很多記錄(數據元素)組成，每個元素又包括很多字段(數據項)組成。那么這張表的邏輯結構是怎么樣的呢? 我們分析數據結構都是從結點(其實也就是元素、記錄、頂點，雖然在各種情況下所用名字不同，但說的是同一個東東)之間的關系來分析的，對于這個表中的任一個記錄(結點)，它只有一個直接前趨，只有一個直接后繼(前趨后繼就是前相鄰后相鄰的意思)，整個表只有一個開始結點和一個終端結點，那我們知道了這些關系就能明白這個表的邏輯結構了。
而存儲結構則是指用計算機語言如何表示結點之間的這種關系。如上面的表，在計算機語言中描述為連續存放在一片內存單元中，還是隨機的存放在內存中再用指針把它們鏈接在一起，這兩種表示法就成為兩種不同的存儲結構。(注意，在本課程里，我們只在高級語言的層次上討論存儲結構。)
第三個概念就是對數據的運算，比如一張表格，我們需要進行查找，增加，修改，刪除記錄等工作，而怎么樣才能進行這樣的操作呢? 這也就是數據的運算，它不僅僅是加減乘除這些算術運算了，在數據結構中，這些運算常常涉及算法問題。
弄清了以上三個問題，就可以弄清數據結構這個概念。
置空隊 ：InitQueue(Q)
判隊空： QueueEmpty(Q)
判隊滿： QueueFull(Q)
入隊 ： EnQueue(Q,x)
出隊 ： DeQueue(Q)
取隊頭元素： QueueFront(Q),不同與出隊，隊頭元素仍然保留
--------------------------------------------------------------------------------
隊列也有順序存儲和鏈式存儲兩種存儲結構，前者稱順序隊列，后者為鏈隊。
對于順序隊列，我們要理解"假上溢"的現象。
我們現實中的隊列比如人群排隊買票，隊伍中的人是可以一邊進去從另一頭出來的，除非地方不夠，總不會有"溢出"的現象，相似地，當隊列中元素完全充滿這個向量空間時，再入隊自然就會上溢，如果隊列中已沒有元素，那么再要出隊也會下溢。
那么"假上溢"就是怎么回事呢?
因為在這里，我們的隊列是存儲在一個向量空間里，在這一段連續的存儲空間中，由一個隊列頭指針和一個尾指針表示這個隊列，當頭指針和尾指針指向同一個位置時，隊列為空，也就是說，隊列是由兩個指針中間的元素構成的。在隊列中，入隊和出隊并不是象現實中，元素一個個地向前移動，走完了就沒有了,而是指針在移動，當出隊操作時，頭指針向前(即向量空間的尾部)增加一個位置，入隊時，尾指針向前增加一個位置，在某種情況下，比如說進一個出一個，兩個指針就不停地向前移動，直到隊列所在向量空間的尾部，這時再入隊的話，尾指針就要跑到向量空間外面去了，僅管這時整個向量空間是空的，隊列也是空的，卻產生了"上溢"現象，這就是假上溢。
為了克服這種現象造成的空間浪費，我們引入循環向量的概念，就好比是把向量空間彎起來，形成一個頭尾相接的環形，這樣，當存于其中的隊列頭尾指針移到向量空間的上界(尾部)時，再加1的操作(入隊或出隊)就使指針指向向量的下界，也就是從頭開始。這時的隊列就稱循環隊列。
通常我們應用的大都是循環隊列。由于循環的原因，光看頭尾指針重疊在一起我們并不能判斷隊列是空的還是滿的，這時就需要處理一些邊界條件，以區別隊列是空還是滿。方法至少有三種，一種是另設一個布爾變量來判斷(就是請別人看著，是空還是滿由他說了算)，第二種是少用一個元素空間，當入隊時，先測試入隊后尾指針是不是會等于頭指針，如果相等就算隊已滿，不許入隊。第三種就是用一個計數器記錄隊列中的元素的總數，這樣就可以隨時知道隊列的長度了，只要隊列中的元素個數等于向量空間的長度，就是隊滿。
以上是順序隊列，我們要掌握相應算法以解決簡單應用問題。
--------------------------------------------------------------------------------
隊列的鏈式存儲結構稱為鏈隊列，一個鏈隊列就是一個操作受限的單鏈表。為了便于在表尾進行插入(入隊)的操作，在表尾增加一個尾指針，一個鏈隊列就由一個頭指針和一個尾指針唯一地確定。鏈隊列不存在隊滿和上溢的問題。在鏈隊列的出隊算法中，要注意當原隊中只有一個結點時，出隊后要同進修改頭尾指針并使隊列變空。
--------------------------------------------------------------------------------
3.棧和隊列的應用(領會)
教材中舉了幾個例子，對于我們初學者來說，看上去比較繁，我們只要掌握一點，那就是，對于什么情況下用棧和隊列作為解決問題的數據結構。
判斷的要點就是：如果這個問題滿足后進先出(LIFO)的原則，就可以使用棧來處理。如果這個問題滿足先進先出(FIFO)的原則，就可以使用隊列來處理。
比如簡單的說，有一個數組序列，我們輸入時按順序輸入，但是輸出時需要逆序輸出，那么它就可以利用棧來處理，把這個數組存入一個棧中就可以容易地按逆序輸出結果了。
第三章 線性表習題及答案
--------------------------------------------------------------------------------
一、基礎知識題
(答案及點評) 3.1 設將整數1，2，3，4依次進棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答下述問題：
(1)若入、出棧次序為Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),則出棧的數字序列為何(這里Push(i)表示i進棧，Pop( )表示出棧)?
(2) 能否得到出棧序列1423和1432?并說明為什么不能得到或者如何得到。
(3)請分析 1，2 ，3 ，4 的24種排列中，哪些序列是可以通過相應的入出棧操作得到的。
--------------------------------------------------------------------------------
(答案及點評) 3.2 鏈棧中為何不設置頭結點?
答：鏈棧不需要在頭部附加頭結點，因為棧都是在頭部進行操作的，如果加了頭結點，等于要對頭結點之后的結點進行操作，反而使算法更復雜，所以只要有鏈表的頭指針就可以了。
--------------------------------------------------------------------------------
(答案及點評) 3.3 循環隊列的優點是什么? 如何判別它的空和滿?
3.3 答：循環隊列的優點是：它可以克服順序隊列的"假上溢"現象，能夠使存儲隊列的向量空間得到充分的利用。判別循環隊列的"空"或"滿"不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是另設一布爾變量來區別隊列的空和滿。二是少用一個元素的空間。每次入隊前測試入隊后頭尾指針是否會重合，如果會重合就認為隊列已滿。三是設置一計數器記錄隊列中元素總數，不僅可判別空或滿，還可以得到隊列中元素的個數。
