数据结构栈C

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

压栈：栈的插入操作叫做进栈/压栈/入栈。

出栈：栈的删除操作叫做出栈。

栈的实现一般可以通过使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小

接下来我们对栈采用顺序表（连续存储数据）的方式来模拟实现

头文件的创建

#pragma once

#include
#include
#include
#include

//
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;

}ST;

//初始化
void StackInit(ST* ps);

//插入
void StackPush(ST* ps, STDataType x);

//删除
void StackPop(ST* ps);

//销毁
void StackDestory(ST* ps);

//判空
bool StackEmpty(ST* ps);

//容量
int StackSize(ST* ps);

//返回栈顶元素
STDataType StackTop(ST* ps);

功能实现

#include "Stack.h"

//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

//插入
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ?4 : ps->capacity * 2;
		STDataType* tem = (STDataType*)realloc(ps->a, sizeof(STDataType*)*newCapacity);
		if (tem == NULL)
		{
			printf("realloc failn");
			exit(-1);
		}
		ps->a = tem;
		ps->capacity = newCapacity;
		
	}
	ps->a[ps->top] = x;
	ps->top++;
}

//删除
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//判空
	ps->top--;
}

//返回栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top-1];
}

//销毁
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

//判空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;//空返回真
}

//个数
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

练习

括号匹配

力扣

这道题正好可以用到我们上面所变编好的程序，在其基础上进行此题

思路：根据题目要求，括号全部成对出现时正确，我们可以把左括号全部放到栈里，之后在将其逐一拿出与s中剩余括号匹配比较。

bool isValid(char * s){
ST st;
StackInit(&st);
while(*s)
{
    if(*s=='('||*s=='{'||*s=='[')
    {
        StackPush(&st,*s);
        ++s;
    }
    else
    {
        if(StackEmpty(&st))
        {
            StackDestory(&st);
            return false;
        }
        STDataType top=StackTop(&st);
        StackPop(&st);
        if(top=='{'&&*s=='}'||
        top=='('&&*s==')'||
        top=='['&&*s==']')
        {
            ++s;
        }
        else
        {
            StackDestory(&st);
            return false;
        }
    }
}
bool ret=StackEmpty(&st);//s结束了，栈中的也全部匹配上了
StackDestory(&st);
return ret;
}