数据结构学习之栈
本篇博客我们将深入学习数据结构中栈与队列相关的内容
作者的个人gitee：楼田莉子 (riko-lou-tian) - Gitee.com
目录
概念
栈的实现
初始化
销毁
入栈
判空
出栈
获取栈顶元素
栈的有效元素个数
源代码
与栈相关的算法题（力扣）有效的括号
编辑
概念
栈是一种特殊的线性表，只允许在固定的一端进行插入删除元素的操作。进行数据插入和删除操作的一端叫栈顶，另一端叫栈底。遵循“后进先出”的原则。下图就是对栈后进先出的一种形象化演示。
栈的逻辑结构是线性的，物理结构因种类而决定。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作叫出栈。出数据也在栈顶
栈在底层上一般使用数组或者链表实现。通常是数组，因为数组插入数据的代价更小
栈的实现
stack.h——栈的结构定义和相关函数的声明
stack.c——相关函数的实现
test.c ——测试
初始化
//初始化栈
void STInit(ST* st)
{st->arr = NULL;st->top = st->capacity = 0;
}
销毁
//销毁栈
void STDestroy(ST* st)
{if (st->arr){free(st->arr);}st->arr = NULL;st->top = st->capacity = 0;
}入栈
//入栈
void STPush(ST* st, STDataType data)
{if (st->top == st->capacity){//增容int newcapacity = st->capacity==0? 4:st->capacity * 2 ;STDataType*tmp=(STDataType*)realloc(st->arr, newcapacity*sizeof(STDataType));if (tmp == NULL){printf("内存分配失败！\n");exit(1);}st->arr = tmp;st->capacity = newcapacity;}st->arr[st->top++] = data;
}判空
//判断栈是否为空
bool STIsEmpty(ST* st)
{assert(st);return st->top == 0;
}出栈
//出栈
//栈不为空才能出栈
void STpop(ST* st)
{assert(!STIsEmpty(st));--st->top;
}获取栈顶元素
//获取栈顶元素
STDataType STGetTop(ST* st)
{assert(!STIsEmpty(st));return st->arr[st->top-1];
}栈的有效元素个数
//获取栈中有效元素个数
size_t STGetValidSize(ST* st)
{return st->top;
}
源代码
stack.h
#pragma once
#include<stdio.h>
#include <stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义栈的数据类型
typedef int STDataType;
//定义栈的结构
typedef struct Stack
{STDataType*arr; // 栈底size_t top; // 有效数据个数（栈顶）size_t capacity;// 栈的容量
}ST;
//初始化栈
void STInit(ST* st);
//入栈
void STPush(ST* st, STDataType data);
//判断栈是否为空
bool STIsEmpty(ST* st);
//出栈
void STpop(ST* st);
//获取栈顶元素
STDataType STGetTop(ST* st);
//获取栈中有效元素个数
size_t STGetValidSize(ST* st);
//销毁栈
void STDestroy(ST* st);stack.c
#define _CRT_SECURE_NO_WARNINGS
#include"stack.h"
//初始化栈
void STInit(ST* st)
{st->arr = NULL;st->top = st->capacity = 0;
}
//入栈
void STPush(ST* st, STDataType data)
{if (st->top == st->capacity){//增容int newcapacity = st->capacity==0? 4:st->capacity * 2 ;STDataType*tmp=(STDataType*)realloc(st->arr, newcapacity*sizeof(STDataType));if (tmp == NULL){printf("内存分配失败！\n");exit(1);}st->arr = tmp;st->capacity = newcapacity;}st->arr[st->top++] = data;
}
//判断栈是否为空
bool STIsEmpty(ST* st)
{assert(st);return st->top == 0;
}
//出栈
//栈不为空才能出栈
void STpop(ST* st)
{assert(!STIsEmpty(st));--st->top;
}
//获取栈顶元素
STDataType STGetTop(ST* st)
{assert(!STIsEmpty(st));return st->arr[st->top-1];
}
//获取栈中有效元素个数
size_t STGetValidSize(ST* st)
{return st->top;
}
//销毁栈
void STDestroy(ST* st)
{if (st->arr){free(st->arr);}st->arr = NULL;st->top = st->capacity = 0;
}test.c
#define _CRT_SECURE_NO_WARNINGS
#include"stack.h"
void test1()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2); STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);//STpop(&st);while (!STIsEmpty(&st)){int top= STGetTop(&st);printf("%d ", top);STpop(&st);}
}
int main()
{test1();return 0;
}与栈相关的算法题（力扣）有效的括号
由上图示例可知：括号没有括号的优先级但是有闭合的顺序
思路：借助栈来实现
遍历字符串，（入栈，）取栈顶与字符比较是否匹配
答案：
//借助数据结构——栈
//定义栈的数据类型
typedef char STDataType;
//定义栈的结构
typedef struct Stack
{STDataType*arr; // 栈底size_t top; // 有效数据个数（栈顶）size_t capacity;// 栈的容量
}ST;
//初始化栈
void STInit(ST* st)
{st->arr = NULL;st->top = st->capacity = 0;
}
//入栈
void STPush(ST* st, STDataType data)
{if (st->top == st->capacity){//增容int newcapacity = st->capacity==0? 4:st->capacity * 2 ;STDataType*tmp=(STDataType*)realloc(st->arr, newcapacity*sizeof(STDataType));if (tmp == NULL){printf("内存分配失败！\n");exit(1);}st->arr = tmp;st->capacity = newcapacity;}st->arr[st->top++] = data;
}
//判断栈是否为空
bool STIsEmpty(ST* st)
{assert(st);return st->top == 0;
}
//出栈
//栈不为空才能出栈
void STpop(ST* st)
{assert(!STIsEmpty(st));--st->top;
}
//获取栈顶元素
STDataType STGetTop(ST* st)
{assert(!STIsEmpty(st));return st->arr[st->top-1];
}
//获取栈中有效元素个数
size_t STGetValidSize(ST* st)
{return st->top;
}
//销毁栈
void STDestroy(ST* st)
{if (st->arr){free(st->arr);}st->arr = NULL;st->top = st->capacity = 0;
}
//栈实现的代码
bool isValid(char* s)
{ST st;STInit(&st);char*pi=s;while(*pi!='\0'){//左括号入栈if(*pi=='('||*pi=='['||*pi=='{'){STPush(&st,*pi);}else{//判断为空的情况if(STIsEmpty(&st)){STDestroy(&st);return false;}//右括号出栈//取栈顶跟*pi比较进行匹配char top=STGetTop(&st);if((top=='('&&*pi!=')')||(top=='['&&*pi!=']')||(top=='{'&&*pi!='}')){STDestroy(&st);return false;}STpop(&st);}pi++;}bool ret =STIsEmpty(&st)?true:false;STDestroy(&st);return ret;
}本篇内容就到这里了，喜欢的话请给个点赞谢谢
封面图自取：
