源码分析顺序栈

栈实际上就是限定仅在表尾进行插入和删除操作的线性表。同时因为只能在表尾进行操作，所以栈又称为后进先出的线性表。既然栈是线性表，而线性表包括顺序表和链表，那么同样地，栈也包括顺序栈和链栈。顺序栈是栈的顺序实现，本文我们就先来讨论一下顺序栈。

顺序栈是指利用顺序存储结构实现的栈。采用地址连续的存储空间（数组)依次存储栈中数据元素，由于入栈和出栈运算都是在栈顶进行，而栈底位置是固定不变的，可以将栈底位置设置在数组空间的起始处；栈顶位置是随入栈和出栈操作而变化的，故需用一个整型变量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)，如果栈满，及时处理。想要学习更多的数据结构可以观看本站的数据结构和算法教程，踏上征服数据结构之路！