数据结构——栈

目录

一、栈

1.1 栈的基本概念

1.2 栈的实现

二、栈的接口实现

（1）初始化栈

（2）入栈

?（3）出栈

（4）获取栈顶元素

（5）获取栈中有效元素个数

（6）检测栈是否为空

（7）销毁栈

三、有效的括号?

一、栈

1.1 栈的基本概念

在前面学习函数栈帧的创建和销毁（函数栈帧的创建和销毁-CSDN博客）中，我们已经对栈有了一个初步的认识，接下来我们来深入的学习栈的概念和其接口的实现。

栈是一种特殊的线性表，其特点是只允许在固定的一端进行插入或删除操作。允许进行数据插入和删除操作的一端为栈顶，另一端为栈底。

其中，栈中的数据元素遵循：LIFO（Last In First Out），即后进先出的原则。我们可以想象成往一个箱子里放书，最后放进去的书往往是最先被取出来的。

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

出栈：栈的删除操作叫做出栈，还是从栈顶删除数据

1.2 栈的实现

栈的实现一般可以通过用数组实现栈或者用链表实现栈，二者取其优，相对而言使用数组的结构实现栈会更简便高效。

因为在前面顺序表的增删查改接口实现中（数据结构——顺序表-CSDN博客）我们使用数组的结构来尾插尾删十分的方便，所以在栈的实现中我们把数组尾部定义为栈顶，头部定义成栈底即可。

二、栈的接口实现

栈和顺序表一样，可以设计成定长的静态栈或者支持动态增长的栈。因为定长栈局限性大，实际中不实用，所以我们主要实现支持动态增长的栈。

和前面的顺序表/链表接口实现相同，我们先创建一个头文件"Stack.h"和两个源文件"Stack.c"和"Test.c",具体作用为：

• Stack.h：栈的定义，头文件的引用和接口函数的声明
• Stack.c：接口函数的实现
• Test.c：测试各个函数

我们先展示"Stack.h"的完整代码，不要忘记在两个源文件中引用"Stack.h"

#pragma once //防止头文件被二次引用

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int STDataType; //如果要修改存储的数据类型可直接在此修改

typedef struct Stack 
{
	STDataType* arr;
	int top;
	int capacity; //容量
}Stack;

void StackInit(Stack* pst);//初始化栈

void StackPush(Stack* pst, STDataType x);//入栈

void StackPop(Stack* pst);//出栈

STDataType StackTop(Stack* pst);//获取栈顶元素

int StackSize(Stack* pst);//获取栈中有效元素个数

bool StackEmpty(Stack* pst);//检测栈是否为空

void StackDestory(Stack* pst);//销毁栈

其中，结构体中的"top"的含义是由初始数值决定的，下面会详细讲。接下来我们开始实现接口。

（1）初始化栈

void StackInit(Stack* pst)
{
	assert(pst);
	pst->arr = NULL;
	pst->top = 0; //top指向栈顶数据的下一个位置
	pst->capacity = 0;
}

类似的，我们可以将结构体中的top近似理解为数组的下标（虽然并不是但是能方便理解）。如果我们在初始化栈时将top初始化为0，此时栈中没有数据，top指向栈顶数据的下一个位置。

如果我们将top初始化为-1时，top则指向栈顶数据的位置。这里我们初始化为0会更好。

（2）入栈

void StackPush(Stack* pst, STDataType x)
{
	if (pst->top == pst->capacity) //容量已满，需要扩容
	{
		int NewCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; //如果容量为0则扩到4，否则扩为2倍
		STDataType* cmp = (STDataType*)realloc(pst->arr, NewCapacity * sizeof(STDataType));
        //创建一个临时指针变量来存储新空间地址，防止开辟失败
		if (cmp == NULL) //防止空间开辟失败出现空指针
		{
			perror("realloc fail");
			return;
		}
		pst->arr = cmp; //将临时指针变量中存放的新空间地址赋值给arr
		pst->capacity = NewCapacity; //空间容量更新
	}
	pst->arr[pst->top] = x; //将数据存放进栈顶元素的下一个位置
	pst->top++; //位置更新
}

?（3）出栈

void StackPop(Stack* pst)
{
	assert(pst); //断言，防止传入空指针
	assert(!StackEmpty(pst)); //断言，用检测空栈的函数返回值来判断，栈为空则不能出栈
	pst->top--; //位置更新
}

出栈只需要移动top的位置，把原来栈顶的元素“踢出”有效数据范围即可。StackEmpty函数将在后面讲到。

（4）获取栈顶元素

STDataType StackTop(Stack* pst)
{
	assert(pst); //断言，防止传入空指针
	assert(!StackEmpty(pst)); //断言，用检测空栈的函数返回值来判断，栈为空则不能获取
	return pst->arr[pst->top - 1]; //top-1为栈顶元素位置，返回其值即可
}

（5）获取栈中有效元素个数

int StackSize(Stack* pst)
{
	assert(pst); //断言，防止传入空指针
	return pst->top; //top即为有效元素个数
}

（6）检测栈是否为空

bool StackEmpty(Stack* pst)
{
	assert(pst); //断言，防止传入空指针
	return pst->top == 0; //如果top为0表达式则为真，返回值为ture，反之为false
}

这也是为什么前面断言中的StackEmpty要加逻辑取反操作符的原因，如果为栈为空，StackEmpty的返回值为true，取反为false才能触发断言。

（7）销毁栈

void StackDestory(Stack* pst)
{
	free(pst->arr); //释放arr
	pst->arr = NULL; //置空
	pst->top = pst->capacity = 0; //更新位置和容量
}

?所有接口都完成后，我们在Test.c中调试一下

??

看起来一切正常，搞多点花样试试

??

完全没问题，恭喜你完成了栈的接口实现！?

栈的接口实现到此结束，是不是比前面的链表实现简单多了？如果有兴趣的话可以来看看数据结构——带头双向循环链表-CSDN博客

趁热打铁，接下来我们用一道关于栈的OJ题来练练手吧

三、有效的括号?

OJ题链接：20. 有效的括号 - 力扣（LeetCode）

?这道题的核心思路在于：

1. 遇到左括号将其入栈
2. 遇到右括号，就将栈顶元素出栈并判断是否匹配。如果此时栈为空或不匹配说明字符串无效
3. 当字符串走到结尾时栈中仍有元素说明字符串无效，栈为空则有效?

有了核心思路，大家可以尝试自己做一下这道题?

?需要说明的是，如果我们使用C语言来做这道题会略显麻烦，因为我们需要自己写一个栈。但是刚刚我们已经写好了，所以直接cv上去即可。

将"Stack.h"和"Stack.c"整个复制到代码栏中，我们还需要修改一个地方。

??

这里我们要在栈中存放字符，直接在这里把int改成char即可，这里也体现了重命名的方便之处。

接着我们开始讲解题目的核心代码

bool isValid(char *s)
{
    Stack st; //创建栈
    StackInit(&st); //初始化栈
    while (*s) //走到字符串结尾即'/0'时循环结束
    {
        if (*s == '(' || *s == '[' || *s == '{') //遇到左括号
        {
            StackPush(&st, *s); //入栈
        }
        else //遇到右括号
        {
            if (StackEmpty(&st)) //如果此时栈为空说明不匹配
            {
                StackDestory(&st); //销毁栈防止内存泄漏
                return false;
            }
            if ((*s == ')' && StackTop(&st) != '(') 
            || (*s == ']' && StackTop(&st) != '[') 
            || (*s == '}' && StackTop(&st) != '{')) //如果右括号和栈顶元素不匹配
            {
                StackDestory(&st); //销毁栈防止内存泄漏
                return false;
            }
            else //如果右括号和栈顶元素匹配则继续
            {
                StackPop(&st); //弹出栈顶元素
            }
        }
        s++; //迭代
    }
    bool ret = StackEmpty(&st); //此时字符串走到结尾，循环结束，判断栈是否为空
    StackDestory(&st); //销毁栈防止内存泄漏
    return ret; //栈为空说明有效，返回true，反之返回false
}

??

恭喜你击败了100.00%的用户！

完.?

PS：新年到了，祝各位小伙伴bug越写越少，生活越来越好：）