棧實際上就是限定僅在表尾進行插入和刪除操作的線性表。同時因為只能在表尾進行操作，所以棧又稱為后進先出的線性表。既然棧是線性表，而線性表包括順序表和鏈表，那么同樣地，棧也包括順序棧和鏈棧。順序棧是棧的順序實現，本文我們就先來討論一下順序棧。

順序棧是指利用順序存儲結構實現的棧。采用地址連續的存儲空間（數組)依次存儲棧中數據元素，由于入棧和出棧運算都是在棧頂進行，而棧底位置是固定不變的，可以將棧底位置設置在數組空間的起始處；棧頂位置是隨入棧和出棧操作而變化的，故需用一個整型變量top來記錄當前棧頂元素在數組中的位置。

順序棧中我們定義一個top指針，其實這里只是個游標，對應著棧頂元素的下標，比如top是0，那棧頂元素下標就是0，表示只有一個0號元素，通常規定如果top等于-1，表示空棧。見下圖所示，一個有5個元素空間的順序棧結構，當top=1時，有兩個元素，top=-1時，空棧，top=4時，滿棧。

順序棧的代碼實現：

那么我們就來實現下順序棧的push和pop，以及清空棧clear還是先定義一下數據元素，包含一個id和一個name

typedef struct DataElement

{

int id;

const char* name;

}DataElement;

接著定義順序棧結構，包括數組元素、top指針（游標）、數組長度

typedef struct SeqStack

{

DataElement elements[MAX_SIZE]; //棧內元素數組

int top; //棧頂（數組中下標），如果為-1，表明棧是空的

int length; //當前棧的元素個數

}SeqStack;

然后我們來實現一下壓棧push操作。注意：我們插入的元素下標是要將top加加后得到的值，因為top加加后才指向新的元素空間。

void PushSeqStack(SeqStack* seqStack, DataElement element)

{

if (seqStack->top == MAX_SIZE)

{

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

return;

}

seqStack->top++;

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

seqStack->length++;

return;

}

接著實現彈棧pop操作，同理我們需要先將top值減減。

void PopSeqStack(SeqStack* seqStack)

{

if (seqStack->top == -1)

{

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

return;

}

seqStack->top--;

seqStack->length--;

return;

}

然后實現一下初始化函數，初始化數組的長度和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]);

}

}

接著實現清空棧，直接將top賦值-1，數組長度歸零即可。

void ClearSeqStack(SeqStack* seqStack)

{

seqStack->length = 0;

seqStack->top = -1;

}

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

int IsEmpty(SeqStack* seqStack)

{

if (seqStack->top == -1)

return 1;

return 0;

}

最后為了測試，實現一個打印順序棧。這和遍歷數組沒多大區別。

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);

}

}

測試代碼：

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

{

    { 1, "離散"},

    { 2, "算法"},

    { 3, "高數"},

    { 4, "數據"}

};

然后實現測試函數，這次我們動態分配順序棧空間，然后將4個元素全部壓入棧中，接著將表尾元素彈棧，最后清空棧。

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);

}編譯運行，可以看到，彈棧后4號元素“數據”（下標為3的元素）被刪除了。清空后也是沒問題。

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