手撕数据结构之栈+例题

admin管理员组

文章数量:1487745

手撕数据结构之栈+例题

一、栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则。

如同子弹夹，我们进行添子弹和出子弹，很形象。

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

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

接下来，我们以数组栈的形式去模拟。

二、栈的头文件及基本框架

代码语言：javascript代码运行次数：0运行复制

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

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;//就是以a开头的一段连续的空间
	int top;//定义栈顶位置
	int capacity;
}ST;

void SLInit(ST* ps);
void SLDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDataType STTop(ST* ps);//获取栈顶元素

三、接口实现

1、对栈的初始化

代码语言：javascript代码运行次数：0运行复制

void SLInit(ST* ps)
{
	ST* ret = (ST*)malloc(4 * sizeof(ST));
	if (ret == NULL)
	{
		perror(malloc);
		exit(-1);
	}
	ps->a = ret;
	ps->capacity = 4;
	ps->top = 0;
}

2、栈的销毁

代码语言：javascript代码运行次数：0运行复制

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

3、入栈操作

代码语言：javascript代码运行次数：0运行复制

void STPush(ST* ps, STDataType x)
{
	assert(ps != NULL);
	//检查需不需要扩容
	if (ps->top == ps->capacity)
	{
		ps->capacity += 4;
		ST* ret = (ST*)realloc( ps->a, sizeof(ST) * ps->capacity);
		if (ret == NULL)
		{
			perror(realloc);
			exit(-1);
		}
		ps->a = ret;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

4、出栈操作

代码语言：javascript代码运行次数：0运行复制

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

5、判断栈是否为空

代码语言：javascript代码运行次数：0运行复制

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
    如果右边等式成立返回true，反之返回false
}

6、返回栈顶元素

代码语言：javascript代码运行次数：0运行复制

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

7、遍历栈

不同于其他数据结构，遍历栈不用print

代码语言：javascript代码运行次数：0运行复制

//遍历栈的特殊方式
	while (!STEmpty(&ps))
	{
		printf("%d ", STTop(&ps));
		STPop(&ps);
	}

四、有效的括号 - 力扣（LeetCode）

题目描述：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

思路：

如果是左括号就入栈，如果是右括号就与栈顶元素进行比较。这样就正好匹配题目的要求，但博主目前没有学过STL库，所以只能将上面的手撕栈CV一下啦，下面的代码为了避免冗余去除掉这一部分~

代码：

代码语言：javascript代码运行次数：0运行复制

bool isValid(char * s)
{
    char* ret = s;
    int num = 0;
    //利用奇数偶数判断数量是否匹配
    while(*ret)
    {
        num++;
        ret++;
    }
    if(num%2 != 0)
    {
        return false;
    }
    ST ps;
	SLInit(&ps);
    while(*s)
    {
    switch(*s)
    {
        case '{':
        case '[':
        case '(':
            STPush(&ps,*s);
            break;
        case ')':
        case ']':
        case '}':
            if(STSize(&ps) == 0)
                return false;
            if(*s == ']' && STTop(&ps) != '['||
               *s == ')' && STTop(&ps) != '('||
               *s == '}' && STTop(&ps) != '{')
            {
                SLDestroy(&ps);
                return false;
            }
            STPop(&ps);
            break;
    }
    s++;
    }
    //防止((出现
    if(!STEmpty(&ps))
        return false;
    return true;
}

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-15，如有侵权请联系 cloudcommunity@tencent 删除前往查看遍历数据字符串数据结构ps

本文标签： 手撕数据结构之栈例题