数据结构《栈》

1、栈的概念及结构

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

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

2、栈的实现

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

进栈、出栈展示：

实现栈，最好声明与定义分开成俩个文件来处理（头文件,h（介绍接口），实现文件.c(实现接口功能)）

1、头文件.h

#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>typedef int type;
#define N 10;
//静态栈（不常用，所以我们要实现的是动态栈）
typedef struct Stack
{type arr[N];int top;//栈顶
}Stack;//动态栈
typedef struct Stack
{type* a;int top;int capacity;
}sl;// 初始化栈
void Slint(sl* p);
// 入栈
void pushpop(sl* p, type x);
// 出栈
void STpop(sl* p);
// 获取栈顶元素
type STTop(sl* p);
// 获取栈中有效元素个数
int STsize(sl* p); 
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool empty(sl* p);
// 销毁栈
void destroy(sl* p);

实现文件.c

void Slint(sl* p)
{assert(p);p->a = NULL;p->capacity = 0;p->top = 0;
}void pushpop(sl* p, type x)
{assert(p);if (p->top == p->capacity){int newcapacity = p->capacity == 0 ? sizeof(type) : 2 * p->capacity;type* new = (type*)realloc(p->a, sizeof(type) * newcapacity);if (new == NULL){perror("realloc fail");return;}p->a = new;p->capacity = newcapacity;}p->a[p->top] = x;p->top++;}void STpop(sl* p)
{assert(p);p->top--;
}type STTop(sl* p)
{assert(p);assert(p->top > 0);return p->a[p->top - 1];
}bool empty(sl* p)
{assert(p);return p->top == 0;
}void destroy(sl* p)
{free(p->a);p->a = NULL;p->capacity = 0;p->top = 0;
}int STsize(sl* p)
{assert(p);return p->top;
}

3、练习:

括号匹配问题

第一步->实现一个栈，在用栈的后进先出特性来匹配括号。
情况1：如果为‘(’、‘[’、‘{’。左括号入栈

情况2：如果为‘）’，‘}’，‘]’右括号与栈顶匹配

//实现一个栈
typedef char type;typedef struct Stack
{type* a;int top;int capacity;
}sl;void Slint(sl* p);void destroy(sl* p);void pushpop(sl* p, type x);void STpop(sl* p);type STTop(sl* p);bool empty(sl* p);int STsize(sl* p);void Slint(sl* p)
{assert(p);p->a = NULL;p->capacity = 0;p->top = 0;
}void pushpop(sl* p, type x)
{assert(p);if (p->top == p->capacity){int newcapacity = p->capacity == 0 ? sizeof(type) : 2 * p->capacity;type* new = (type*)realloc(p->a, sizeof(type) * newcapacity);if (new == NULL){perror("realloc fail");return;}p->a = new;p->capacity = newcapacity;}p->a[p->top] = x;p->top++;}void STpop(sl* p)
{assert(p);p->top--;
}type STTop(sl* p)
{assert(p);assert(p->top > 0);return p->a[p->top - 1];
}bool empty(sl* p)
{assert(p);return p->top == 0;
}void destroy(sl* p)
{free(p->a);p->a = NULL;p->capacity = 0;p->top = 0;
}int STsize(sl* p)
{assert(p);return p->top;
}
//匹配括号
bool isValid(char* s) {sl s3;Slint(&s3);while (*s){if (*s == '(' || *s == '{' || *s == '[')//情况1{pushpop(&s3, *s);}else//情况2{if(empty(&s3)){return false;}char top = STTop(&s3);STpop(&s3);if ((top == '(' && *s != ')') || (top == '[' && *s != ']') || (top == '{' && *s != '}')){return false;}}s++;}bool ret=empty(&s3);//判断栈有没有数据destroy(&s3);return ret ;}
}