摘要：棧底是固定的，而棧頂浮動(dòng)的如果棧中元素個(gè)數(shù)為零則被稱為空棧。入棧將數(shù)據(jù)保存到棧頂。鏈棧鏈棧是指棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是沒(méi)有附加頭節(jié)點(diǎn)的運(yùn)算受限的單鏈表，棧頂指針是鏈表的頭指針。

線性表是一個(gè)線性結(jié)構(gòu)，它是一個(gè)含有n≥0個(gè)節(jié)點(diǎn)的有限序列。在節(jié)點(diǎn)中，有且僅有一個(gè)開(kāi)始節(jié)點(diǎn)沒(méi)有前驅(qū)并有一個(gè)后繼節(jié)點(diǎn)，有且僅有一個(gè)終端節(jié)點(diǎn)沒(méi)有后繼并有一個(gè)前驅(qū)節(jié)點(diǎn)。其他的節(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)和一個(gè)后繼節(jié)點(diǎn)。通?？梢园岩粋€(gè)線性表表示成一個(gè)線性序列：k1，k2，…，kn，其中k1是開(kāi)始節(jié)點(diǎn)，kn是終端節(jié)點(diǎn)。

在編程領(lǐng)域中，線性結(jié)構(gòu)具有如下兩個(gè)基本特征。
（1）集合中必存在唯一的一個(gè)“第一元素”和唯一的一個(gè)“最后元素”；
（2）除最后一個(gè)元素之外，均有唯一的后繼(后件)和唯一的前驅(qū)(前件)；
由n(n≥0)個(gè)數(shù)據(jù)元素(節(jié)點(diǎn))a1，a2，…，an組成的有限序列，數(shù)據(jù)元素的個(gè)數(shù)n定義為表的長(zhǎng)度。當(dāng)n=0時(shí)稱為空表，我們通常將非空的線性表(n>0)記作：
(a1，a2，…an)
數(shù)據(jù)元素ai(1≦i≦n)沒(méi)有特殊含義，大家不必去“剖根問(wèn)底”的研究它，它只是一個(gè)抽象的符號(hào)，其具體含義在不同的情況下可以不同。

線性表雖然只是一對(duì)一的單挑，但是其操作功能非常強(qiáng)大，具備了很多操作技能。

均勻性：雖然不同數(shù)據(jù)表的數(shù)據(jù)元素是各種各樣的，但同一線性表的各數(shù)據(jù)元素必須有相同的類(lèi)型和長(zhǎng)度；
有序性：各數(shù)據(jù)元素在線性表中的位置只取決于它們的序。數(shù)據(jù)元素之前的相對(duì)位置是線性的，即存在唯一的“第一個(gè)”和“最后一個(gè)”的數(shù)據(jù)元素，除了第一個(gè)和最后一個(gè)外，其他元素前面只有一個(gè)數(shù)據(jù)元素直接前趨，后面只有一個(gè)直接后繼二、

在現(xiàn)實(shí)應(yīng)用中，有兩種實(shí)現(xiàn)線性表數(shù)據(jù)元素存儲(chǔ)功能的方法，分別是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序表操作是最簡(jiǎn)單的操作線性表的方法，此方式的主要操作功能如下所示。
（1）計(jì)算順序表的長(zhǎng)度
（2）清空操作
（3）判斷線性表是否為空
（4）判斷順序表是否為滿
（5）附加操作
（6）插入操作
（7）刪除操作
（8）獲取表元
（9）按值進(jìn)行查找

鏈比順序表要復(fù)雜一點(diǎn)，對(duì)于同一個(gè)數(shù)據(jù)，它可以和不相鄰的數(shù)據(jù)發(fā)生關(guān)系。例如農(nóng)民通常將收獲的水果賣(mài)給商販，商販將收購(gòu)的水果賣(mài)給加工廠。這是一條水果加工產(chǎn)業(yè)鏈，可以得出商販?zhǔn)寝r(nóng)民的財(cái)神、加工廠是商販的財(cái)神這一論調(diào)。在那一年的某一天，老實(shí)的農(nóng)民發(fā)現(xiàn)利潤(rùn)較低，于是拉著自己的水果不遠(yuǎn)萬(wàn)里的親自賣(mài)給了加工廠。這樣農(nóng)民伯伯獲得了更大的利潤(rùn)，而商販也不能怎么著，這個(gè)產(chǎn)業(yè)鏈還得繼續(xù)下去。
由此可見(jiàn)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不需要用地址連續(xù)的存儲(chǔ)單元來(lái)實(shí)現(xiàn)，而是通過(guò)“鏈”建立起數(shù)據(jù)元素之間的次序關(guān)系。所以它不要求邏輯上相鄰的兩個(gè)數(shù)據(jù)元素在物理結(jié)構(gòu)上也相鄰，在插入和刪除時(shí)無(wú)需移動(dòng)元素就而提高了運(yùn)行效率。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)主要有單鏈表、循環(huán)鏈表、雙向鏈表、靜態(tài)鏈表等幾種形式。

隊(duì)列和棧一樣，只允許在斷點(diǎn)處插入和刪除元素，循環(huán)隊(duì)的入隊(duì)算法如下所示。
（1）tail=tail+1；
（2）如果tail=n+1，則tail=1；
（3）如果head=tai，即尾指針與頭指針重合，則表示元素已裝滿隊(duì)列，會(huì)施行上溢出錯(cuò)處理；否則Q(tail)=X，結(jié)束整個(gè)過(guò)程，其中X表示新入出元素。

使用C語(yǔ)言定義鏈隊(duì)列的格式如下所示。

typedef struct QNode{
ElemType    data;
struct QNode    *next;
}QNode, *QueuePtr;

typedef struct {
QueuePtr     front;         /* 隊(duì)頭指針，指向頭元素         */
QueuePtr     rear;        /* 隊(duì)尾指針，指向隊(duì)尾元素     */
}LinkQueue;

（1）初始化隊(duì)列Q的目的是創(chuàng)建一個(gè)隊(duì)列
（2）入隊(duì)的目的是將一個(gè)新元素添加到隊(duì)尾，相當(dāng)于到隊(duì)列最后排隊(duì)等候。
（3）出隊(duì)的目的是取出隊(duì)頭的元素，并同時(shí)刪除該元素，使后一個(gè)元素成為隊(duì)頭。
（4）獲取隊(duì)列第1個(gè)元素，即將隊(duì)頭的元素取出，不刪除該元素，隊(duì)頭仍然是該元素。
（5）判斷隊(duì)列Q是否為空

當(dāng)使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示隊(duì)列時(shí)，需要設(shè)置隊(duì)頭指針和隊(duì)尾指針，這樣做的好處是可以設(shè)置隊(duì)頭指的針和隊(duì)尾的指針。在入隊(duì)時(shí)需要執(zhí)行如下三條語(yǔ)句。

s->next=NULL;
rear->next=s;
rear=s;

在C語(yǔ)言中，實(shí)現(xiàn)隊(duì)列鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類(lèi)型的代碼如下所示。

type struct linklist {    //鏈?zhǔn)疥?duì)列的節(jié)點(diǎn)結(jié)構(gòu)
Elemtype Entry;    //隊(duì)列的數(shù)據(jù)元素類(lèi)型
struct linklist *next;    //指向后繼節(jié)點(diǎn)的指針
}LINKLIST;

typedef struct queue{    //鏈?zhǔn)疥?duì)列
LINKLIST *front;    //隊(duì)頭指針
LINKLIST *rear;    //隊(duì)尾指針
}QUEUE; 

棧允許在同一端進(jìn)行插入和刪除操作，允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端稱為棧底(bottom)。棧底是固定的，而棧頂浮動(dòng)的；如果棧中元素個(gè)數(shù)為零則被稱為空棧。插入操作一般被稱為進(jìn)棧（PUSH），刪除操作一般被稱為退棧（POP）。
在棧中有兩種基本操作，分別是入棧和出棧。
（1）入棧（Push）
將數(shù)據(jù)保存到棧頂。在進(jìn)行入棧操作前，先修改棧頂指針，使其向上移一個(gè)元素位置，然后將數(shù)據(jù)保存到棧頂指針?biāo)傅奈恢?。入棧（Push）操作的算法如下：
①如果TOP≥ｎ，則給出溢出信息，作出錯(cuò)處理。在進(jìn)棧前首先檢查棧是否已滿，如果滿則溢出；不滿則進(jìn)入下一步驟②；
②設(shè)置TOP=TOP+1，使棧指針加１，指向進(jìn)棧地址；
③S(TOP)=X，結(jié)束操作，X為新進(jìn)棧的元素。
（2）出棧（Pop）
將棧頂?shù)臄?shù)據(jù)彈出，然后修改棧頂指針，使其指向棧中的下一個(gè)元素。出棧（Pop）操作的算法如下：
①如果TOP≤0，則輸出下溢信息，并實(shí)現(xiàn)出錯(cuò)處理。在退棧之前先檢查是否已為空棧，如果是空則下溢信息，如果不空則進(jìn)入下一步驟②；
②X=S(TOP)，退棧后的元素賦給X；
③TOP=TOP-1，結(jié)束操作，棧指針減１，指向棧頂。

順序棧是棧的順序存儲(chǔ)結(jié)構(gòu)的簡(jiǎn)稱，它是一個(gè)運(yùn)算受限的順序表。假設(shè)S是SeqStack類(lèi)型的指針變量，如果棧底位置在向量的低端，則S-＞data[0]是棧底元素。

鏈棧是指棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是沒(méi)有附加頭節(jié)點(diǎn)的、運(yùn)算受限的單鏈表，棧頂指針是鏈表的頭指針。