数据结构之栈的实现

我们来看看如何实现栈的实现

1.初始化

首先呢，我们可以还是老样子，创建一个Stack的头文件，用来声明函数，创一个相同的源文件，用来实现代码的逻辑，创一个test.c的文件，用来测试代码的逻辑，如下： 接下来，我们来看看如何实现初始化的操作： 首先，我们先把栈给创建好，如下：

typedef int STdatatype;

struct Stack
{
STdatatype* a;
int top;
int capacity;
};
typedef struct Stack Stack;

为了更方便的使用，我们小小的typedef一下，节省一下我们的时间。 其中top在这里为指向栈顶元素的下一个位置，capacity就为容量啦，至于top为啥是指向栈顶元素的下一个位置，一会我们初始化的时候就直到啦。

//头文件
void STInit(Stack* st);

那么接下来我们来初始化一下：

void STInit(Stack* st)
{
assert(st);//保证为有效指针
st->a == NULL;
st->top = st->capacity = 0;//如果top为指向栈顶元素的下一个位置，那么top为0，反之，top为-1
}

2.销毁

//头文件
void STDestroy(Stack* st);

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

这没啥可说的，过。

3.入栈

//头文件
void STPush(Stack* st, STdatatype data);

void STPush(Stack* st, STdatatype data)
{
assert(st);
if(st->top == st->capacity)
{
int newcapacity = (st->capacity == 0)?4;st->capacity * 2;
STdatatype tmp = realloc(st->a,newcapacity*sizeof(STdatatype));
if(tmp == NULL)
{
perror("realloc fail");
return;
}
st->a = tmp;
st->capacity = newcapacity;
}
st->a[st->top]=data;
st->top++;

}

我们入栈的话，这里就需要考虑到扩容的情况，这里用一个三目操作符，意思是，如过st->capacity == 0，那么就把值置为4，否则为st->capacity * 2，接下来保存新开辟的空间，再赋给st->a即可，接着入栈，st->top++即可。

4.出栈

//头文件
void STPop(Stack* st);

void STPop(Stack* st)
{
assert(st);
assert(st->top > 0);
st->top—;
}

这里更是没啥好说的，就是为了使代码测试时更加细节，可以assert(st->top > 0)

5.取栈顶数据

//头文件
STdatatype STTop(Stack* st);

STdatatype STTop(Stack* st)
{
assert(st);
assert(st->top > 0);
return st->a[st->top – 1];
}

没啥好说，过。

6.判空

//头文件
bool STEmpty(Stack* st);

bool STEmpty(Stack* st)
{
assert(st);
return st->top == 0;
}

同样没啥好说，如果st->top == 0那么说明为真，返回true，如果为假，就返回false

7.获取元素个数

//头文件
int STSize(Stack* st);

int STSize(Stack* st)
{
assert(st);
return st->top;
}

没啥好说，过！

8.测试

总的还说，这里不是特别难，我们就简单来看一看测试用例：

#include "stack.h"

int main()
{
Stack ST;
STInit(&ST);
STPush(&ST, 1);
STPush(&ST, 2);
STPush(&ST, 3);
STPush(&ST, 4);
while (!STEmpty(&ST))
{
printf("%d ", STTop(&ST));
STPop(&ST);
}

STDestroy(&ST);

return 0;
}

9.栈oj题目之有效的括号

https://leetcode.cn/problems/valid-parentheses/submissions/704775206/

#include <stdbool.h>
#include <string.h>

bool isValid(char* s)
{
int len = strlen(s);
char Stack[len + 1];
int top = –1;
for (int i = 0; i < len; i++)
{
char ch = s[i];
if (ch == '(' || ch == '[' || ch == '{')
{
Stack[++top] = ch;
}
else
{
if (top == –1)
{
return false;
}
char topChar = Stack[top];
if ((ch == ')' && topChar != '(') || (ch == ']' && topChar != '[') || (ch == '}' && topChar != '{'))
{
return false;
}
top—;
}

}
return top == –1;
}

解题思路：使用栈

栈是一种“后进先出”的数据结构，非常适合处理括号匹配问题。我们可以遍历字符串的每个字符：

• 如果遇到左括号，将其压入栈中。

• 如果遇到右括号，则检查栈顶是否是对应的左括号：

• 如果栈为空，说明没有左括号与之匹配，返回 false。

• 如果栈顶不是对应的左括号，返回 false。

• 如果匹配，则弹出栈顶元素，继续遍历。

• 遍历结束后，如果栈为空，说明所有括号都正确匹配，返回 true；否则返回 false。

为什么栈能工作？因为括号的嵌套特性：最近出现的左括号必须最先被闭合，这正是栈的“后进先出”特性。 算法步骤：

• 初始化一个空栈。

• 遍历字符串 s 的每个字符 ch：

• 如果 ch 是左括号 (、[ 或 {，将其压入栈。

如果 ch 是右括号：

• 如果栈为空，则返回 false。

• 否则，取出栈顶元素，检查是否与当前右括号匹配：

• 如果是 )，栈顶应为 (

• 如果是 ]，栈顶应为 [

• 如果是 }，栈顶应为 {

• 如果不匹配，返回 false。

• 如果匹配，将栈顶弹出，继续。

• 遍历结束后，如果栈为空，返回 true；否则返回 false。

最后结尾不要忘记检查栈是否为空