文章目录

• 1.栈的概念及结构
• 2.栈的实现（数组实现）
• • 2.1栈头文件
  • 2.2函数实现
• 3.栈的习题
• • 3.1有效的括号
  • • 3.1.1思路分析
    • 3.1.2代码实现

1.栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

2.栈的实现（数组实现）

2.1栈头文件

#pragma once
#include
#include
#include
#include
#include
typedef int STDatatype;
typedef struct stack
{STDatatype* a;int top;int capacity;
}ST;
void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDatatype x);
void StackPop(ST* ps);
STDatatype StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);

2.2函数实现

#include"stack.h"
void StackInit(ST* ps)
{assert(ps);ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);if (ps->a == NULL){perror("malloc fail");exit(-1);}ps->top = 0;//top的值是值得推敲的，如果为0那么top指向的就是栈顶元素的下一个，并且top的值还是元素数量，如果top的值为-1，那么top的指向的就收栈顶元素ps->capacity = 4;}
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->top = 0;ps->capacity = 0;
}
void StackPush(ST* ps, STDatatype x)
{assert(ps);if (ps->top == ps->capacity){STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype));if (tmp == NULL){perror("malloc");exit(-1);}ps->capacity *= 2;ps->a = tmp;}ps->a[ps->top] = x;ps->top++;}
void StackPop(ST* ps)
{assert(ps);/*assert(ps->top > 0);*/assert(!StackEmpty(ps));ps->top--;}
STDatatype StackTop(ST* ps)
{assert(ps);//assert(ps->top > 0);assert(!StackEmpty(ps));return ps->a[ps->top-1];
}
bool StackEmpty(ST* ps)
{assert(ps);return(ps->top == 0);
}
int StackSize(ST* ps)
{assert(ps);return ps->top;
}

3.栈的习题

3.1有效的括号

3.1.1思路分析

首先拿到这道题我们可能会进入一个误区
我们可能会想到strlen来求字符长度奇偶性来判断是否合法，这显然想得不够全面"{{{{{{"显然这种就不好用。
这道题简单来看合不合法就是依次消掉括号，看最后能否都消除

3.1.2代码实现

typedef char STDatatype;
typedef struct stack
{STDatatype* a;int top;int capacity;
}ST;
void StackInit(ST* ps)
{assert(ps);ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);if (ps->a == NULL){perror("malloc fail");exit(-1);}ps->top = 0;ps->capacity = 4;}
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->top = 0;ps->capacity = 0;
}
void StackPush(ST* ps, STDatatype x)
{assert(ps);if (ps->top == ps->capacity){STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype));if (tmp == NULL){perror("malloc");exit(-1);}ps->capacity *= 2;ps->a = tmp;}ps->a[ps->top] = x;ps->top++;}
bool StackEmpty(ST* ps)
{assert(ps);return(ps->top == 0);
}
void StackPop(ST* ps)
{assert(ps);/*assert(ps->top > 0);*/assert(!StackEmpty(ps));ps->top--;}
STDatatype StackTop(ST* ps)
{assert(ps);//assert(ps->top > 0);assert(!StackEmpty(ps));return ps->a[ps->top-1];
}int StackSize(ST* ps)
{assert(ps);return ps->top;
}
bool isValid(char * s){ST st;StackInit(&st);while(*s){if(*s=='{'||*s=='['||*s=='('){StackPush(&st,*s);++s;}else{if(StackEmpty(&st)){return false;}char top=StackTop(&st);StackPop(&st);if((*s=='}'&&top!='{')||(*s==']'&&top!='[')||(*s==')'&&top!='(')){return false;}else{++s;}}}bool ret=StackEmpty(&st);StackDestroy(&st);return ret;}