数据结构——栈

发布时间:2024年01月03日

目录

一、栈

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越写越少,生活越来越好:)

文章来源:https://blog.csdn.net/Eristic0618/article/details/135355421
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。