1．棧的順序存儲
棧的順序存儲可用向量來實現(xiàn)，即利用一組地址連續(xù)的存儲單元依次存放棧中的各個數(shù)據(jù)元素，又可稱為順序棧。最先入棧的數(shù)據(jù)元素為棧底，最后入棧的數(shù)據(jù)元素為棧頂。一般將向量的低下標位置作為棧底，并保持不變，棧頂位置隨著元素的進棧和出棧操作而變化。為了方便操作，通常設(shè)一個標記top標出棧頂元素所在的位置。使用C語言，我們可將順序棧的數(shù)據(jù)類型描述如下：
結(jié)構(gòu)3-1 順序棧
#define Maxsize 100 //假設(shè)?？臻g最多為100個元素
typedef char Datatype; //假設(shè)棧元素的數(shù)據(jù)類型為字符
typedef struct
{ Datatype data[Stacksize];
int top;
}Seqstack;
該類型包含兩部分內(nèi)容：一是存放棧中數(shù)據(jù)元素的data數(shù)組，另一個是標記棧頂位置的top。在C語言的描述中，我們可約定data數(shù)組中的data[0]單元不用，并用top=0表示?？?，這也是初始化棧的狀態(tài)。在實際應用時，需聲明一個屬于上述類型的棧變量，即可對此變量進行棧的有關(guān)操作。
現(xiàn)假設(shè)有一個棧類型，其最大存儲空間Maxsize為6，s為指向該類型的棧指針，按照約定，棧中可存放的數(shù)據(jù)元素最多為5個，可存放在s->data[1]至s->data[5]中。初始狀態(tài)下s->top=0，表示?？?，如圖3-2（a）所示。當棧不滿時，可進行進棧操作，當棧不空時，可進行出棧操作。若有數(shù)據(jù)元素（A，B，C，D，E）依次進棧，則s->top每次加1，并將元素存入s->top所標記的位置，棧的狀態(tài)如圖3-2（b）、3-2（c）所示。若有數(shù)據(jù)元素出棧，則刪除s->top標記位置的數(shù)據(jù)元素，s->top每次減1，如圖3-2（d）所示。
（a）空棧 （b）A進棧 （c）棧滿 （d）E、D出棧
圖3-2 順序棧的狀態(tài)及進棧、出棧操作
可見?？蘸蜅M是進行棧操作的兩個限制條件：
棧空條件：s->top = 0，此時不能進行出棧操作
棧滿條件：s->top = Maxsize -1，此時不能進行進棧操作
2．棧的基本運算的實現(xiàn)
算法3-1 初始化
棧的初始化即創(chuàng)建一個空棧。可通過指針變量獲取該空棧。算法描述如下：
void init _seqstack(Seqstack *s)
{ s->top = 0;
}
算法3-2 判?？?/span>
對一個已創(chuàng)建的棧判斷其是否為空。若為空，則返回1，否則，返回0，函數(shù)的返回值為整型，參數(shù)為指向已知棧的指針。算法描述如下：
int empty_seqstack (Seqstack *s)
{ if(s->top == 0)
return 1;
else
return 0;
}
算法3-3 判棧滿
對一個已創(chuàng)建的棧判斷其是否為滿。若為滿，則返回1，否則，返回0，函數(shù)的返回值為整型，參數(shù)為指向已知棧的指針。算法描述如下：
int full_seqstack (Seqstack *s)
{ if(s->top == Maxsize-1)
return 1;
else
return 0;
}
算法3-4 進棧
將一個新的數(shù)據(jù)元素插入到棧中作為新的棧頂元素。注意插入前首先要判斷棧是否已滿，若棧滿，則不能插入，函數(shù)返回0值，表示插入不成功；若不滿，移動棧頂標記，插入新的數(shù)據(jù)元素，函數(shù)返回1，表示插入成功。算法描述如下：
int push_seqstack(Seqstack *s, Datatype x)
{ if(full_seqstack(s)) //判棧是否為滿
{ printf(″Overflow＼n″);
return 0;}
else
{ s->top++;
(s->data)［s->top］ = x;
return 1;}
}
算法3-5 出棧
在已知棧中刪除棧頂元素并將棧頂元素作為返回值。注意在刪除操作之前首先要判斷棧是否為為空，若為空，則不能刪除；若不為空，則返回棧頂元素，移動棧頂標記。算法描述如下：
Datatype pop_seqstack(Seqstack *s,Datatype *x)
{ if(empty_seqstack(s)) //判棧是否為空
{ printf(″Underflow＼n″); return 0;}
else
{ &x = (s->data)［s->top］;
s->top--;}
return x;
}
算法3-6 取棧頂元素
在已知棧中取出棧頂元素并將棧頂元素作為返回值。注意在取出操作之前首先要判斷棧是否為為空，若為空，則無元素可??；若不為空，則返回棧頂元素。算法描述如下：
Datatype gettop_seqstack(Seqstack *s)
{ Datatype x;
if(empty_seqstack(s)) //判棧是否為空
{printf(″Stack is empty.＼n″);
x = NULL;}
else
x = (s->data)［s->top］;
return x;
}
算法3-7 置空
將棧的棧頂標記置為初始狀態(tài)，成為空棧。算法描述如下：
void clear _seqstack(Seqstack *s)
{ s->top = 0;
}
