本章概述
- 概念
- 结构
- 栈的实现
- 算法题
- 彩蛋时刻！！！
概念
- 栈的概念：栈是一种只能在一端进行数据的删除或增加的一种线性表，它的物理结构不一定是线性的。进入数据或删除数据的一端称为栈顶，另一端称为栈底。增加（进入）数据的过程称为进栈（压栈），删除数据的过程称为出栈。如图所示：
什么数据也没有就称为空栈，如图所示：
结构
- 栈的中文解释：存储货物或供旅客住宿的房屋。我们知道存储货物的箱子或旅馆只能从一端进出（取出），所以栈的数据也是如此特性。如图所示：
- 特点：因为栈只能从一端进行数据的存储或删除，所以栈是一种受限运算。因为栈是一种数据结构，是数据结构就要存储数据。所以，这就要想一个问题了——它的底层逻辑是以什么方式去存储数据呢？在数据结构中，我们用单链表或顺序表进行底层的数据存储，所以，上面咱们提到过——栈的物理空间不一定是。如果是以单链表为底层逻辑的话，物理空间就不是连续的，如果是以顺序表为底层逻辑的话，物理空间就是连续的。我们最常以顺序表为底层逻辑进行数据的存储。进行原因的解释：栈只能从一端进行数据的存储或删除，如果我们以单链表为底层的话，我们进行尾插数据就需要遍历每个结点，时间复杂度就会增加。我们进行数据删除的时候，也需要遍历每个结点，然后再释放结点空间，时间复杂度也较大。以顺序表为底层的话，我们进行尾插数据时，可以直接找到size位置进行数据的插入，时间复杂度为
O（1）。相比于用单链表，时间复杂度降低了不少。综上所述：选择以顺序表为底层。
栈的实现
我们和单链表一样，也是给大家展示三个文件，通过代码给大家进行讲解，进行代码展示，
- 1：stack.h文件：
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDatatype;
//栈的结构形式
typedef struct stack
{STDatatype* arr;int top;int capacity;
}ST;//初始化
void STinit(ST* ps);
//判断是否为空栈
bool STcheck(ST*ps);
//栈的销毁
void STdestroy(ST*ps);//进栈
void STpushback(ST* ps, STDatatype x);
//出栈
void STpop(ST*ps);//栈取元素
STDatatype getdata(ST* ps); //每取一个数据就要出栈一个数据//获取栈中的有效数据个数
int getyouxiaodata(ST* ps);
- 2：stack.c文件：
#include "stack.h"
//栈的初始化
void STinit(ST* ps)
{assert(ps); //判断是否为空ps->arr = NULL;ps->capacity = ps->top = 0;
}//判断是否为空栈
bool STcheck(ST* ps)
{assert(ps); //判断是否为空return ps->top == 0; //空栈返回 true ,否则false
}//栈的销毁
void STdestroy(ST* ps)
{assert(ps); //判断是否为空if (ps->arr != NULL){free(ps->arr);ps->capacity = ps->top = 0;}
}//进栈
void STpushback(ST* ps, STDatatype x)
{assert(ps); //判断是否为空if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDatatype* temp = (STDatatype*)realloc(ps->arr, newcapacity * sizeof(STDatatype));if (temp == NULL){perror("realloc fail!");exit(1);}ps->arr = temp;ps->capacity = newcapacity;}ps->arr[ps->top] = x;ps->top++;
}//出栈
void STpop(ST* ps)
{assert(ps); //判断是否为空assert(!STcheck(ps)); //空栈报错ps->top--;
}//栈取元素
STDatatype getdata(ST* ps)
{assert(ps); //判断是否为空assert(!STcheck(ps));return ps->arr[ps->top - 1]; //ps->top-1只是计算最终的结果，ps->top的值不会改变
}//获取栈中的有效数据个数
int getyouxiaodata(ST* ps)
{assert(ps); //判断是否为空return ps->top;
}
- 3：test.c文件：
#define _CRT_SECURE_NO_WARNINGS 1
#include "stack.h"
void test()
{ST st;STinit(&st);STpushback(&st,1);STpushback(&st,2);STpushback(&st,3);STpushback(&st,4);printf("%d\n", getyouxiaodata(&st));STdestroy(&st);/* STpop(&st);STpop(&st);STpop(&st);*///STpop(&st);//STpop(&st);
}
int main()
{test();return 0;
}
算法题
LeetCode:有效的括号
先给大家看一下题目描述：
- 题目解读：这数组的元素全是一个个括号字符，只有对应的括号才能算是有效的括号。比如，[ { } ]这是个有效的括号，[ { ) ]为非有效的括号。我们可以运行用栈的思想，把左括号作为入栈元素，先进的元素后出。然后，再进行出栈，与其右括号进行匹配，就可以进行是否有效的括号的匹配。进行代码展示：
typedef char STDatatype;
// 栈的结构形式
typedef struct stack {STDatatype* arr;int top;int capacity;
} ST;
// 栈的初始化
void STinit(ST* ps) {assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}// 判断是否为空栈
bool STcheck(ST* ps) {assert(ps);return ps->top == 0; // 空栈返回 true ,否则false
}// 栈的销毁
void STdestroy(ST* ps) {assert(ps);if (ps->arr != NULL) {free(ps->arr);ps->capacity = ps->top = 0;}
}// 进栈
void STpushback(ST* ps, STDatatype x) {assert(ps);if (ps->top == ps->capacity) {int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDatatype* temp =(STDatatype*)realloc(ps->arr, newcapacity * sizeof(STDatatype));if (temp == NULL) {perror("realloc fail!");exit(1);}ps->arr = temp;ps->capacity = newcapacity;}ps->arr[ps->top] = x;ps->top++;
}// 出栈
void STpop(ST* ps) {assert(ps);assert(!STcheck(ps)); // 空栈报错ps->top--;
}// 栈取元素
STDatatype getdata(ST* ps) {assert(ps);assert(!STcheck(ps));return ps->arr[ps->top - 1]; // ps->top-1只是计算最终的结果，ps->top的值不会改变
}bool isValid(char* s) {assert(s);STDatatype* pi = s;ST st;STinit(&st);while (*pi != '\0') {if (*pi == '(' || *pi == '{' || *pi == '[')STpushback(&st, *pi);else {if(STcheck(&st)){STdestroy(&st);return false;}char ppt = getdata(&st);if((*pi==']'&&ppt!='[')||(*pi=='}'&&ppt!='{')||(*pi==')'&&ppt!='(')){STdestroy(&st);return false;}STpop(&st);}pi++;}if(STcheck(&st)){STdestroy(&st);return true;}else{STdestroy(&st);return false;}
}
我们可以不用再写栈，直接把我们的代码进行copy就OK了。等我们学习了C++的STL库的时候，就可以不用自己手写栈了，可以直接调用STL库里面的栈，大大节省了时间。
彩蛋时刻！！！
歌曲：《Uncover 》
每章一句：别忘了，每一次的跌倒都是为了明天的自己更强！感谢你能看到这里，点赞+关注+收藏+转发是对我最大的鼓励，咱们下期见！！！
