算法开启小码农栈血脉
2021/10/30 20:11:03
本文主要是介绍算法开启小码农栈血脉,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
栈
栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶
出栈:栈的删除操作叫做出栈。出数据也在栈顶
栈的实现
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
栈节点
typedef int STDataType; typedef struct Stack { STDataType* a; int top; //栈顶 int capacity; //容量 }ST;
栈初始化函数StackInit
//栈初始化函数 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; }
入栈函数StackPush
//入栈函数 void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity)//判断是否扩容 { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType)); if (!tmp) { printf("relloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } //扩容扩好以后把数据给过去 ps->a[ps->top] = x; ps->top++; }
提前把栈销毁函数写好
栈销毁函数StackDestroy
//栈销毁函数 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; }
出栈函数StackPop
//出栈函数 void StackPop(ST* ps) { assert(ps); assert(ps->top>0); ps->top--; }
判断栈是否为空 函数StackEmpty
//判断栈是否为空函数 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }
取栈顶元素函数StackTop
//取栈顶部函数 STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; }
栈大小函数StackSize
//栈大小函数 int StackSize(ST* ps) { assert(ps); return ps->top; }
遍历栈
while (!StackEmpty(&stack)) { printf("%d ", StackTop(&stack)); StackPop(&stack); }
代码
Stack.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* a; int top; //栈顶 int capacity; //容量 }ST; //栈初始化函数 extern void StackInit(ST* ps); //栈销毁函数 extern void StackDestroy(ST* ps); //入栈函数 extern void StackPush(ST* ps, STDataType x); //出栈函数 extern void StackPop(ST* ps); //取栈顶部函数 extern STDataType StackTop(ST* ps); //栈大小函数 extern int StackSize(ST* ps); //判断栈是否为空函数 extern bool StackEmpty(ST* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" //栈初始化函数 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; } //入栈函数 void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity)//判断是否扩容 { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType)); if (!tmp) { printf("relloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } //扩容扩好以后把数据给过去 ps->a[ps->top] = x; ps->top++; } //栈销毁函数 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } //出栈函数 void StackPop(ST* ps) { assert(ps); assert(ps->top>0); ps->top--; } //取栈顶部函数 STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } //栈大小函数 int StackSize(ST* ps) { assert(ps); return ps->top; } //判断栈是否为空函数 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" void Test1() { ST stack = { 0 }; StackInit(&stack); StackPush(&stack, 1); StackPush(&stack, 2); StackPush(&stack, 3); StackPush(&stack, 4); //遍历栈 while (!StackEmpty(&stack)) { printf("%d ", StackTop(&stack)); StackPop(&stack); } printf("\n"); StackDestroy(&stack); } int main() { Test1(); return 0; }
练习
例1有效的括号
typedef char STDataType; typedef struct Stack { STDataType* a; int top; //栈顶 int capacity; //容量 }ST; //栈初始化函数 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; } //栈销毁函数 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = 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* tmp = (STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType)); if (!tmp) { printf("relloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } //扩容扩好以后把数据给过去 ps->a[ps->top] = x; ps->top++; } //判断栈是否为空函数 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } //取栈顶部函数 STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } //出栈函数 void StackPop(ST* ps) { assert(ps); assert(ps->top>0); ps->top--; } bool isValid(char * s){ ST st = {0}; StackInit(&st); while(*s) { //如果是左括号就入栈 if(*s == '(' || *s == '{' || *s == '[') { //入栈 StackPush(&st,*s); s++; } else { if(StackEmpty(&st)) { StackDestroy(&st); return false; } //出栈 STDataType tmp = StackTop(&st); StackPop(&st); if(*s == '}' && tmp != '{' || *s == ']' && tmp != '[' || *s == ')' && tmp != '(') { StackDestroy(&st); return false; } else { s++; } } } //如果栈不是空说明还有左括号 bool ret = StackEmpty(&st); StackDestroy(&st); return ret; }
这篇关于算法开启小码农栈血脉的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)