栈结构初探
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
> — 百度百科
栈结构是数据结构中相对来说比较简单的一个结构了，当然，栈也是属于逻辑结构中的线性表结构，只不过它是操作受限的。什么意思呢？我们前面在探索线性表的时候都知道，我们可以在线性表的任意位置插入和删除元素。但是对于栈结构来说，只能在栈顶执行相关的操作。用生活中的例子来举例的话: 就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。
所以说，从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
对于第一次接触栈这种数据结构的同学来说，可能会有一定的疑惑，因为相比于数组和链表，栈带来的更多的是限制。事实上，从功能上来说，数组或者链表确实可以替代栈。但是特定的数据结构是针对于特定的场景的抽象，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。
如何实现顺序栈
从前面栈的定义中可以得出，栈主要包含两个操作，入栈和出栈。也就是在栈顶插入一个数据和从栈顶删除一个数据。实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，叫做顺序栈，用链表实现的栈，叫做链式栈。下面我们就来一一实现。
按照国际惯例，我们还是要实现定义一些宏和辅助的变量，代码如下:
#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status;typedef int SElemType;
因为我们使用的是 C 语言来实现顺序栈，所以需要定义一个结构体类型，这里我们就定义一个 SqStack 的结构体类型，代码如下所示:
typedef struct {SElemType data[MAXSIZE];int top;}SqStack;
通过上面的代码可以看出，我们在顺序栈结构体中定义了两个属性，一个是栈顶指针 top ，注意，这里和指针变量是两个概念。然后是一个 SElemType 类型的数组 data ，我们针对栈的入栈和出栈操作就是针对于这个数组。
好的，定义完了基本的数据结构之后，我们来捋一下我们需要实现的一些栈相关的基本的操作。(这里读者可以自己思考一下再继续往下阅读本文。)
按照我们之前探索数组和链表的惯例，我们需要先初始化一个空的栈，然后需要一个方法来判断栈是否为空，接着我们要能有一个方法可以清空顺序栈。最后需要有最重要的两个方法来实现入栈和出栈。因为这里的逻辑比较简单，所以接下来我们直接上代码。
初始化一个顺序栈
Status InitStack(SqStack *S){S->top = -1;return OK;}
这里有一个注意点，就是当初始化一个空的栈的时候，我们这个栈的 top 指针是指向 -1 的，这里的 -1 并不要求是固定的值，只是我们设置的一个标志位，因为当栈不为空的时候，top 指针指向的其实是 data 数组中存储的最后一个值的下标位置。这里之所以并没有开辟内存空间，还记得我们在声明一个顺序结构存储的数组吗，我们用到了指向整型数组的指针，而指针本身在初始化之前是一个野指针，所以必须要通过 malloc 或 calloc 来分配一段内存空间，然后让指针指向这个内存空间。而这里我们是直接声明的一个数组，数组的话在入栈的时候直接添加即可。
置空一个顺序栈
再次回忆一下对顺序存储结构的数组置空的操作，我们只是直接把 length 置为空，并没有取手动的 free 掉数组的内存空间，这就是顺序存储结构的特点。所以同理，置空一个顺序栈的话，只需要把 top 指针指向 -1，就表示这个栈已经没有任何元素了。代码如下:
Status ClearStack(SqStack *S){S->top = -1;return OK;}
判断顺序栈是否为空
那么，如何判断一个顺序栈是否为空呢？显然，我们只需要判断 top 栈顶指针是否为 -1，如果为 -1，说明顺序栈已经为空，如果不等于 -1，说明还有元素尚未出栈。代码如下:
Status StackEmpty(SqStack S){if (S.top == -1) return TRUE;else return FALSE:}
获取顺序栈的长度
因为顺序栈是通过 top 栈顶指针来保存最新插入元素在数组中的下标位置，所以说获取顺序栈的长度显然就跟 top 指针有关系。那么，简单分析一下，我们就能得出顺序栈的长度刚好就是 top 的值加一。代码如下：
int StackLength(SqStack S){return S->top + 1;}
获取栈顶元素
我们首先要明确一点，获取栈顶元素和出栈一个元素并不是两回事，所以说，我们并没有对栈内部的元素有所修改，所以并不需要传入 SqStack 指针，但是呢，我们返回栈顶元素，所以需要将元素的地址传入。
但是我们在获取栈顶元素前，还需要判断一下，这个栈是否为空。
Status GetTop(SqStack S, SElemType *e){if (S.top == -1) return ERROR;*e = S.data[S.top];return OK;}
顺序栈压栈
压栈是我们学习栈结构中最为重要的操作之一，我们先简单理一下逻辑。在压栈之前，我们需要判断栈是否为空吗？显然是不需要的，但是因为我们现在是在实现一个顺序栈，也就是说这个栈的空间是有限的，所以我们需要判断栈是否已经满了，如果已满，我们就不能再执行压栈操作了。而排除掉这些边界值条件后，我们需要分两步来执行压栈操作。第一步，我们要找到我们需要在顺序栈内部的数组里面值的下标位置，而这个位置显然就只能通过 top 来找到，而默认情况下，top 是为负一的，所以我们只需要对 top 执行加一的操作，然后将传入的值赋值给新的 top 值所对应的下标。
Status PushData(SqStack *S, SElemType e){// 顺序栈已满if (S->top == MAXSIZE -1) return ERROR;S->top++;S->data[S->top] = e;return OK;}
这里其实还有另外一种更简便的写法，如下:
Status PushData(SqStack *S, SElemType e){// 顺序栈已满if (S->top == MAXSIZE -1) return ERROR;S->data[++S->top] = e;return OK;}
因为前缀的自增操作符的本质是先执行自增操作，再把自增操作之后的增值拷贝返回回来，所以这里采取前缀自增操作可以让代码看起来更加简洁。
顺序栈出栈
好的，我们现在需要实现的是顺序栈的出栈。对于出栈这个操作，我们也需要考虑边界值的情况。那就是当一个栈为空，那么对这个栈再执行出栈操作显然是不合理的。而栈是否为满并不影响我们的出栈操作。出栈的话也需要分两步操作，第一步需要准备一个指针接收通过 top 栈顶指针取出的栈顶元素的值，第二步需要将 top 指针减一来达到栈的长度减一的效果。代码如下:
Status Pop(SqStack *S, SElemType *e){if (S->top == -1) return ERROR;*e = S->data[S->top];S->top--;return OK;}
同样的，跟入栈操作一样，这里也可以优化成下面的代码:
Status Pop(SqStack *S, SElemType *e)
{
if (S->top == -1) return ERROR;
*e = S->data[S->top--];
return OK;
}
通过后缀的自减运算符，来实现先返回原来的值的拷贝，再对原来的值进行减一的操作。
遍历顺序栈
最后我们需要实现的是遍历一个顺序栈，简单分析一下，我们只需要从下标0开始遍历到栈顶指针的位置。当然，如果栈为空的话，那么就没必要进行遍历了。
Status StackTravese(SqStack S)
{
// 如果栈为空，那就没有必要遍历
if (S.top == -1) return ERROR;
int i = 0;
while (i <= S.top)
{
printf("%d ", S.data[i]);
i++;
}
printf("\n");
return OK;
}
同样的，这里我们也可以将 while 循环内部的 i++ 优化一下:
Status StackTravese(SqStack S)
{
// 如果栈为空，那就没有必要遍历
if (S.top == -1) return ERROR;
int i = 0;
while (i <= S.top)
{
printf("%d ", S.data[i++]);
}
printf("\n");
return OK;
}
至此，我们实现了关于顺序栈的八大操作，接下来我们来验证一下:
int main()
{
SqStack S;
int e;
if (InitStack(&S) == OK)
{
for (int j = 1;j < 10;j++)
{
PushData(&S, j);
}
}
printf("顺序栈中元素为:\n");
StackTraverse(S);
Pop(&S, &e);
printf("弹出栈顶元素为: %d\n", e);
StackTraverse(S);
printf("是否为空栈: %d\n", StackEmpty(S));
GetTop(S, &e);
printf("栈顶元素:%d \n栈长度:%d\n", e, StackLength(S));
ClearStack(&S);
printf("是否已经清空栈 %d, 栈长度为:%d\n", StackEmpty(S), StackLength(S));
return 0;
}
最后打印输出如下:
顺序栈中元素为:
此栈中所有的元素:1 2 3 4 5 6 7 8 9
弹出栈顶元素为: 9
此栈中所有的元素:1 2 3 4 5 6 7 8
是否为空栈: 0
栈顶元素:8
栈长度:8
是否已经清空栈 1, 栈长度为:0
如何实现一个链式栈
我们在前面已经实现了顺序存储的栈，接下来，我们需要实现链式存储的栈。首先，我们需要明确的是链式栈也是需要有 top 指针，而 top 指针指向的是栈的栈顶结点。在压栈和出栈的时候，我们都是通过栈顶指针来找到对应的结点，然后执行在这个结点之前插入新的结点或者删除这个结点。我们先定义一下结点:
typedef struct StackNode
{
// 数据域
SElemType data;
// 指针域
struct StackNode *next;
}StackNode, *LinkStackPtr;
然后我们需要定义链式栈，因为链式栈并不像顺序栈有数组可以存储值，所以这里需要增加一个 count 的整型变量来记录链式栈的长度。
typedef struct {
// 栈顶指针
LinkStackPtr top;
int count;
}LinkStack;
初始化一个链式栈
我们第一步要做的仍然是初始化，不过是初始化链式栈，初始化链式栈的话我们需要分两步来执行。第一步，需要先申请一个内存空间，然后让 top 指针指向这个内存空间，然后再让 top 指针指向 NULL 空指针，因为此时链式栈中并没有任何结点。第二步，将 count 置为 0.。
Status InitStack(LinkStack *S)
{
S->top = (LinkStackPtr)malloc(sizeof(StackNode));
if (S->top == NULL) return ERROR;
S->top = NULL;
S->count = 0;
return true;
}
置空一个链式栈
相比于顺序栈，要置空一个链式栈，就不是仅仅将 top 指针置为 0 那么简单了。我们需要遍历链式栈的所有结点，然后一一释放掉这些结点。
Status ClearStack(LinkStack *S)
{
LinkStackPtr p, q;
p = S->top;
while (p) {
q = p;
p = p->next;
free(q);
}
S->count = 0;
return OK;
}
判断链式栈是否为空
要判断链式栈是否为空，我们只需要判断 count 是否为 0 即可、
Status StackEmpty(LinkStack S)
{
if (S.count == 0) return TRUE;
else return FALSE;
}
获取链式栈的长度
同样的，要获取链式栈的长度也是根据 count 来的。
int StackLength(LinkStack S)
{
return S.count;
}
获取栈顶元素
获取栈顶元素的操作也分为两步，第一步：判断链式栈是否为空，如果链式栈为空，那么就直接返回；如果链式栈不为空，那么就来到第二步；第二步：通过栈顶 top 指针获取到对应的结点，然后从结点的数据域中取出真正的值。
Status GetTop(LinkStack S, SElemType *e)
{
if (StackEmpty(S) == TRUE) return ERROR;
*e = S.top->data;
return OK;
}
链式栈压栈
对于链式栈来说，压栈操作可以分解为以下的步骤：
- 根据传入的值新建一个链式栈结点
- 让新的链式栈结点的指针域指向栈顶指针所指向的结点
- 让 top 栈顶指针指向新创建的链式栈结点
- 让 count 加一
思路捋清楚之后，代码实现就比较简单了:
Status Push(LinkStack *S, SElemType e)
{
LinkStackPtr temp;
temp = (LinkStackPtr)malloc(sizeof(StackNode));
if (temp == NULL) return ERROR;
temp->data = e;
temp->next = S->top;
S->top->next = temp;
S->count++;
return OK;
}
链式栈出栈
链式栈的出栈，我们简单分析一下，可以分解为下列的几个步骤:
- 判断链式栈是否为空，如果为空，那么出栈操作将是非法的
- 如果链式栈不为空，则用传入的元素的指针作为左值来接收 top 栈顶指针指向的结点中的数据域
- 让 top 栈顶指针指向顶结点指针域指向的下一个链式栈结点，然后释放掉顶结点
- 让 count 减一
具体代码实现如下:
Status Pop(LinkStack *S, SElemType *e)
{
if (StackEmpty(*S) == TRUE) return ERROR;
LinkStackPtr p;
p = S->top;
*e = p->data;
S->top = S->top->next;
free(p);
S->count--;
return OK;
}
遍历链式栈
最后是遍历我们的链式栈了，相比于顺序栈，遍历链式栈实现起来并没有更复杂，代码如下:
Stack StackTraverse(LinkStack S)
{
LinkStackPtr p;
p = S.top;
while(p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}
最后，我们来验证链式栈的一系列方法:
int main()
{
printf("链式栈定义与实现\n");
\
int j;
LinkStack s;
int e;
if(InitStack(&s)==OK)
for(j=1;j<=10;j++)
Push(&s,j);
printf("栈中元素依次为：");
StackTraverse(s);
Pop(&s,&e);
printf("弹出的栈顶元素 e=%d\n",e);
StackTraverse(s);
printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));
GetTop(s,&e);
printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));
ClearStack(&s);
printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));
return 0;
}
输出结果如下:
链式栈定义与实现
栈中元素依次为：10 9 8 7 6 5 4 3 2 1
弹出的栈顶元素 e = 10
9 8 7 6 5 4 3 2 1
栈空否：0(1:空 0:否)
栈顶元素 e=9 栈的长度为9
清空栈后，栈空否：1(1:空 0:否)
若有收获，就点个赞吧
0 人点赞
