【追梦之旅】——栈居然还能这样玩？！+ 力扣 - 有效括号-前言????

    哈喽各位友友们????，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！????我仅已此文，手把手带领大家栈的实现和力扣题解知识~ 都是精华内容，可不要错过哟！！！????????????

什么是栈？

   栈和顺序表和链表一样，是线性结构的。栈可以用数组实现，也可以用链表实现。这里采用的是动态数组（顺序结构）实现的方式。栈的特点是LIFO。什么是“LIFO”呢？用中文简单的来说就是后进先出。也有人会叫先进后出，其实都是同一个意思。

栈的C语言实现

头文件编写源码：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;

//顺序栈
typedef struct STNode
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
bool STEmpty(ST* pst);
STDataType STTop(ST* pst);
int STSize(ST* pst);

功能文件编写源码：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	//top指向栈顶元素的下一个位置
	pst->capacity = pst->top = 0;
}
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->capacity = pst->top = 0;
	pst->a = NULL;
}
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	//扩容
	if (pst->capacity == pst->top)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * (pst->capacity);
        STDataType* tem = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tem == NULL)
		{
			perror("realloc fail\n");
			exit(-1);
		}
		pst->capacity = newcapacity;
		pst->a = tem;
	}
	pst->a[pst->top] = x;
	(pst->top)++;
}
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

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

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

测试文件编写源码：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"

int main()
{

	//ST s;
	//STInit(&s);
	//STPush(&s, 1);
	//STPush(&s, 2);
	//STPush(&s, 3);
	//STPush(&s, 4);
	//STPush(&s, 3);
	//STPush(&s, 4);
	//while (!STEmpty(&s))
	//{
	//	printf("%d ", STTop(&s));
	//	STPop(&s);
	//}
	//printf("\n");

	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPop(&s);
	STPop(&s);
	while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	printf("\n");

	return 0;
}

运行结果截图：

力扣题解——有效的括号

谁说C语言不能“C”，接下来我用C语言手撕这道题目。这道题目非常巧妙的运用到了栈这个特点
我的做法是：

• 先让左括号入栈
• 遇到右括号在出栈

不理解上述思想的可以自己画图理解理解，这个我相信难不倒大家，下面是我画的一个比较粗糙的图解~

如果用C嘎嘎来写，则可以直接调用库函数的栈，而C语言就比较难受了。因为C语言没有这样的库函数，所以我们需要首先一个栈，但是不能说C语言就不能做，照样可以"C"! 。前面的栈我已经写好了，直接ctrl c + ctrl v ，复制一份到题目中即可。

题目源码：

typedef int STDataType;

//顺序栈
typedef struct STNode
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
bool STEmpty(ST* pst);
STDataType STTop(ST* pst);
int STSize(ST* pst);
#define _CRT_SECURE_NO_WARNINGS 1

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	//top指向栈顶元素的下一个位置
	pst->capacity = pst->top = 0;
}
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->capacity = pst->top = 0;
	pst->a = NULL;
}
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	//扩容
	if (pst->capacity == pst->top)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * (pst->capacity);
        STDataType* tem = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tem == NULL)
		{
			perror("realloc fail\n");
			exit(-1);
		}
		pst->capacity = newcapacity;
		pst->a = tem;
	}
	pst->a[pst->top] = x;
	(pst->top)++;
}
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

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

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



bool isValid(char * s)
{
    ST st;
    STInit(&st);
    //循环遍历字符串s，遇到\0结束
    while(*s)
    {
        if(*s == '('
        || *s == '['
        || *s == '{')
        {
            STPush(&st,*s);
        }
        else
        {
            if(STEmpty(&st))
            {
                STDestroy(&st);
                return false;
            }
            char Top = STTop(&st);
            STPop(&st);
            if(*s == ')' && Top != '('
            || *s == ']' && Top != '['
            || *s == '}' && Top != '{')
            {
                STDestroy(&st);
                return false;
            }
        }
        s++;
    }
    bool ret = STEmpty(&st);
    STDestroy(&st);
    return ret;
}

运行结果截图：