棧實(shí)際上就是限定僅在表尾進(jìn)行插入和刪除操作的線性表。同時(shí)因?yàn)橹荒茉诒砦策M(jìn)行操作，所以棧又稱為后進(jìn)先出的線性表。既然棧是線性表，而線性表包括順序表和鏈表，那么同樣地，棧也包括順序棧和鏈棧。順序棧是棧的順序?qū)崿F(xiàn)，本文我們就先來討論一下順序棧。

順序棧是指利用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧。采用地址連續(xù)的存儲(chǔ)空間（數(shù)組)依次存儲(chǔ)棧中數(shù)據(jù)元素，由于入棧和出棧運(yùn)算都是在棧頂進(jìn)行，而棧底位置是固定不變的，可以將棧底位置設(shè)置在數(shù)組空間的起始處；棧頂位置是隨入棧和出棧操作而變化的，故需用一個(gè)整型變量top來記錄當(dāng)前棧頂元素在數(shù)組中的位置。

順序棧中我們定義一個(gè)top指針，其實(shí)這里只是個(gè)游標(biāo)，對(duì)應(yīng)著棧頂元素的下標(biāo)，比如top是0，那棧頂元素下標(biāo)就是0，表示只有一個(gè)0號(hào)元素，通常規(guī)定如果top等于-1，表示空棧。見下圖所示，一個(gè)有5個(gè)元素空間的順序棧結(jié)構(gòu)，當(dāng)top=1時(shí)，有兩個(gè)元素，top=-1時(shí)，空棧，top=4時(shí)，滿棧。

順序棧的代碼實(shí)現(xiàn)：

那么我們就來實(shí)現(xiàn)下順序棧的push和pop，以及清空棧clear還是先定義一下數(shù)據(jù)元素，包含一個(gè)id和一個(gè)name

typedef struct DataElement

{

int id;

const char* name;

}DataElement;

接著定義順序棧結(jié)構(gòu)，包括數(shù)組元素、top指針（游標(biāo)）、數(shù)組長度

typedef struct SeqStack

{

DataElement elements[MAX_SIZE]; //棧內(nèi)元素?cái)?shù)組

int top; //棧頂（數(shù)組中下標(biāo)），如果為-1，表明棧是空的

int length; //當(dāng)前棧的元素個(gè)數(shù)

}SeqStack;

然后我們來實(shí)現(xiàn)一下壓棧push操作。注意：我們插入的元素下標(biāo)是要將top加加后得到的值，因?yàn)閠op加加后才指向新的元素空間。

void PushSeqStack(SeqStack* seqStack, DataElement element)

{

if (seqStack->top == MAX_SIZE)

{

printf("滿棧，壓棧失敗！\n");

return;

}

seqStack->top++;

seqStack->elements[seqStack->top] = element;

seqStack->length++;

return;

}

接著實(shí)現(xiàn)彈棧pop操作，同理我們需要先將top值減減。

void PopSeqStack(SeqStack* seqStack)

{

if (seqStack->top == -1)

{

printf("空棧，彈棧失敗！\n");

return;

}

seqStack->top--;

seqStack->length--;

return;

}

然后實(shí)現(xiàn)一下初始化函數(shù)，初始化數(shù)組的長度和top指針后，直接壓棧即可。

void InitSeqStack(SeqStack* seqStack, int length, DataElement* dataArray)

{

seqStack->length = 0;

seqStack->top = -1;

for (int i = 0; i < length; i++)

{

PushSeqStack(seqStack, dataArray[i]);

}

}

接著實(shí)現(xiàn)清空棧，直接將top賦值-1，數(shù)組長度歸零即可。

void ClearSeqStack(SeqStack* seqStack)

{

seqStack->length = 0;

seqStack->top = -1;

}

然后是“是否為空”函數(shù)，也很簡單，只需判斷top是否為-1

int IsEmpty(SeqStack* seqStack)

{

if (seqStack->top == -1)

return 1;

return 0;

}

最后為了測試，實(shí)現(xiàn)一個(gè)打印順序棧。這和遍歷數(shù)組沒多大區(qū)別。

void PrintSeqStack(SeqStack* seqStack)

{

if (seqStack->top == -1)

{

printf("空棧！\n");

return;

}

for (int i = 0; i < seqStack->length; i++)

{

printf("%d\t%s\n", seqStack->elements[i].id, seqStack->elements[i].name);

}

}

測試代碼：

接著我們測試一下，先初始化待插入的數(shù)據(jù)元素DataElement dataArray[] =

{

    { 1, "離散"},

    { 2, "算法"},

    { 3, "高數(shù)"},

    { 4, "數(shù)據(jù)"}

};

然后實(shí)現(xiàn)測試函數(shù)，這次我們動(dòng)態(tài)分配順序棧空間，然后將4個(gè)元素全部壓入棧中，接著將表尾元素彈棧，最后清空棧。

void TestSeqStack()

{

    SeqStack* seqStack = (SeqStack*)malloc(sizeof(SeqStack));

    int length = sizeof(dataArray) / sizeof(dataArray[0]);

    InitSeqStack(seqStack, length, dataArray);

    printf("壓棧后：\n");

    PrintSeqStack(seqStack);

    PopSeqStack(seqStack);

    printf("彈棧后：\n");

    PrintSeqStack(seqStack);

    ClearSeqStack(seqStack);

    printf("清空棧后：\n");

    PrintSeqStack(seqStack);

    free(seqStack);

}編譯運(yùn)行，可以看到，彈棧后4號(hào)元素“數(shù)據(jù)”（下標(biāo)為3的元素）被刪除了。清空后也是沒問題。

順序棧在插入和刪除時(shí)候不需要移動(dòng)元素，只需移動(dòng)top指針。但順序棧和順序表一樣，都需要預(yù)先定好數(shù)組空間，不像鏈表那樣機(jī)動(dòng)。由于順序存儲(chǔ)結(jié)構(gòu)多采用一維數(shù)組存放棧，因此必須特別注意“棧上溢”錯(cuò)誤的發(fā)生；在實(shí)現(xiàn)入棧操作時(shí)，先判斷是否棧滿（stack full)，如果棧滿，及時(shí)處理。想要學(xué)習(xí)更多的數(shù)據(jù)結(jié)構(gòu)可以觀看本站的數(shù)據(jù)結(jié)構(gòu)和算法教程，踏上征服數(shù)據(jù)結(jié)構(gòu)之路！