数据结构——栈的实现

今天，我们来写一下关于栈的博文。

1.首先我们先了解一下什么是栈？

一：概念：

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶

为了更好的理解，我们画个图辅助了解一下吧。

具体解释：

你看上面：

想要加数据的时候，就在栈顶入数据，此时叫压栈

再看，想要删数据的时候，是不是也得再栈顶出？此时叫出栈

同时，你是不是就发现了无论它是加还是删，遵循的规律都是后进先出

二：栈的实现

好了，有了上面的认识后，就可以进行实现部分了。

在此之前，我们首先得考虑考虑，我们得采用什么形式呢？是数组还是链表呢？

一般来说，两者都是可以的，但是使用数组的形式更优一些，对此我们在这里就以链表来实现它。
链式栈：可以用双向链表，但最好用单链表（用头那边当栈顶）
如果用的是数组的话，一般是尾部当栈顶

其实，感觉这里跟顺序表那些都差不多呢~

好了，至此，正式开始吧：

建立数组栈结构：

typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;

初始化部分

void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = 0;   // top是栈顶元素的下一个位置//ps->top = -1;   // top是栈顶元素位置
}

但是这里有些问题：top指向的是栈顶的下一个，先放数据再++
还是栈顶位置，一开始就在0这个位置出发。先++再放数据。给-1位置

看下图：

那么，肯定有人疑惑为什么呢？

答：因为当初始化给0时，就代表栈顶有元素了，给-1的时候就表示栈为空。

你也可以那样想到数组那个，你看：

数组[0]的时候它是不是就代表已经有一个元素了，这个元素相当于就在第一个位置那样？

同样，当你希望初始化时不需要有数据（相当于联想到数组），当0时有一个数字，这时，你给-1，是不是相当于没有数据了？

有人有问了，当你给-1的话，不会变成野指针了吗？

其实这个问题不用担心，因为这里给-1的时候就要判断了。这里0去访问是合法的，但是刚初始化没有push的内容，就会有问题了，所以如果使用0的话，还需要做出处理。

总的来说，使用0还是-1都是没有强制性要求你，都是可以的，看个人喜好了。

这里使用的0的形式。

销毁部分：

void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}

这里销毁的时候，使用-1和0，ps->top就会有一点的区别了。

插入部分

void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}

解释：

在插入之前，我们先进行判断它是否已经满了，满了的话就扩容，反之不用。

插入的话，也比较简单，由于它只能在栈顶插入嘛。因为这里使用的0的形式

所以就直接找到栈顶的位置，插进去就可以了。

ps->a[ps->top] = x;ps->top++;

删除部分

void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}

也由于只能栈顶先删，所以就减减top就可以了。

得出栈的大小部分

int STSize(ST* ps)
{assert(ps);return ps->top;
}

因为使用的是数组栈，我们又知道，数组是连续的，所以直接返回top所在的位置，就可以得出大小了。

判断空部分

bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

因为使用的是0，即栈的下一个，当它栈顶的位置是0的时候，就代表它没有数据了，也就是空。

此时返回就好了。

另外，我们上面的删是不是也得判断一下是否空的情况对不对？如果它已经空了，那么还删的话，有什么意义？对吧？

所以可以看到上面的删除部分，我们使用了断言它不为空。

找尾部分

STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}

这是说，如果你要找尾的话，数组嘛，所以直接找下标就可以了。

好了，功能已经介绍完了。

现在来附上完整代码：

Stack部分

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"void STInit(ST* ps)
{assert(ps);ps->a = (StDatatype*)malloc(sizeof(StDatatype) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->top = 0;ps->capacity = 4;
}void Destory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}void STPush(ST* ps,StDatatype x)
{if (ps->top== ps->capacity){StDatatype* temp =(StDatatype*) realloc(ps->a, sizeof(StDatatype) * ps->capacity * 2);if (temp == NULL){perror("realloc fail");return 0;}ps->a = temp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}
int size(ST* ps)
{assert(ps);return ps->top;
}
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
StDatatype STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top-1];
}

Stack.h部分

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//
//typedef struct Stack
//{
//	int a[20];
//	int top;
//};typedef char StDatatype;
typedef struct Stack
{StDatatype* a ;int top;int capacity;}ST;//ʼ
void STInit(ST* ps);
void Destory(ST* ps);
void STPush(ST* ps,StDatatype x);
void STPop(ST* ps);
int size(ST* ps);
bool STEmpty(ST* ps);
StDatatype STTop(ST* ps);
bool isValid(char* s);

测试部分：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
int main()
{ST st;STInit(&st);STPush(&st,'(');STPush(&st, ']');bool ret = isValid(&s);if (ret == "false"){printf("no");}else{printf("yes");}Destory(&st);return 0;
}

好了，到了每次鸡汤部分：

你每一步都会算数的！