网站域名设置,无觅wordpress,网站用什么图片格式好,做网站关键字目录 栈 栈的实现 数组栈 数组栈的实现 栈的初始化 栈的销毁 数据入栈 判断栈是否为空 数据出栈 获取栈顶元素 获取栈内数据个数 项目实现 栈的基础练习 有效的括号 栈 栈是一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的… 目录 栈 栈的实现 数组栈 数组栈的实现 栈的初始化 栈的销毁 数据入栈 判断栈是否为空 数据出栈 获取栈顶元素 获取栈内数据个数 项目实现 栈的基础练习 有效的括号 栈 栈是一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 注意在栈中数据出栈的顺序不一定和入栈的顺序相同当数据入栈后又出栈不影响下一个数据的入栈顺序 例如 入栈1 2 3 4 5若4和5是入栈又出栈的则出栈的顺序应该是4 5 3 2 1 但是不会出现一种情况即 已经入栈的数据未在入栈后立马出栈不会出现在先入栈又立马出栈的数据的前方 例如 入栈 1 2 3 4若3和4是入栈又立马出栈则不可能出现2和1在3和4的前面 2.若进栈序列为 1,2,3,4 进栈过程中可以出栈则下列不可能的一个出栈序列是 A 1, 4, 3, 2 B 2, 3, 4, 1 C 3, 1, 4, 2 D 3, 4, 2, 1 例如本题中入栈顺序为1, 2, 3, 4那么出栈顺序最基本的就是后入先出即出栈顺序为4,3,2,1如果入栈又立马出栈的是2,3,4则有2,3,4,1如果入栈又立马出栈的是1则有1, 4, 3, 2如果入栈又立马出栈的是3, 4则有3, 4, 2, 1但是不可能存在3, 1, 4, 2因为1作为第一个入栈的要么就是入栈又立马出栈作为第一个出栈的要么就是最后一个出栈的 栈的实现 栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为栈满足后进先出或者即进即出不需要额外移动数据并且数组在尾上插入数据的代价比较小。 数组栈 //静态数组栈
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];// 数组大小固定int _top; // 栈顶
}ST;//动态数组栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a;// 数组大小不固定int _top; // 栈顶int _capacity; // 容量
}ST; 数组栈的实现 //主要实现以下功能//栈的初始化
void STInit(ST* st);
//栈的销毁
void STDestroy(ST* st);
//数据入栈
void STPush(ST* st, STDataType x);
//数据出栈
void STPop(ST* st);
//判断栈是否为空
bool STEmpty(ST* st);
//获取栈元素
STDataType STTop(ST* st);
//获取栈数据个数
int STSize(ST* st); 栈的初始化 在初始化过程中注意top的初始值设置为0代表栈内数据的下一个位置因为初始化栈代表栈内没有元素如果用0代表栈内数据的当前位置那么需要考虑该元素从何而来既然没有数据说明当前栈顶指针指向没有数据的位置而数组下标为0代表第一个元素的位置没有元素就不可能有第一个元素的位置所以此时下标为0代表下一个元素的位置此时说明栈内没有元素但是准备在下一个位置第一个元素的位置添加数据 //栈的初始化
void STInit(ST* st)
{//判断是否存在队列assert(st);//初始化队列st-data NULL;st-top 0;//栈顶指针指向存储数据的下一个位置代表栈内无数据//st-top -1;//栈顶指针指向存储数据的位置代表栈内无数据st-capacity 0;
} 栈的销毁 //栈的销毁
void STDestroy(ST* st)
{//确保有栈的存在assert(st);//销毁栈free(st-data);st-data NULL;//top和capacity更改为无数据的位置st-top st-capacity 0;
} 数据入栈 //数据入栈
void STPush(ST* st, STDataType x)
{//确保有栈的存在assert(st);//向top位置增加数据并使top向后移动//需要判断栈的容量大小if (st-top st-capacity){//如果栈的空间为0则开辟四个空间如果栈容量不为0则扩容原来容量的2倍int newCapacity st-capacity 0 ? 4 : st-capacity * 2;STDataType* tmp (STDataType*)realloc(st-data, sizeof(STDataType) * newCapacity);assert(tmp);st-data tmp;//注意更新容量大小st-capacity newCapacity;}//数据压栈并改变topst-data[st-top] x;
} 判断栈是否为空 //判断栈是否为空
bool STEmpty(ST* st)
{//确保有栈的存在assert(st);//栈为空返回真栈不为空返回假return st-top 0;//判断表达式返回值只有1和0如果为真返回1(true)如果为假返回0(false)
} 数据出栈 //数据出栈
void STPop(ST* st)
{//确保有栈的存在assert(st);//确保栈不会越界assert(!STEmpty(st));//直接移动top指针“看不见即删除”st-top--;
} 获取栈顶元素 //获取栈顶元素
STDataType STTop(ST* st)
{//确保栈存在assert(st);//确保栈不为空assert(!STEmpty(st));//top为栈内数据的下一个位置要获取当前位置的元素需要-1操作return st-data[st-top - 1];
} 获取栈内数据个数 //获取栈内数据个数
int STSize(ST* st)
{assert(st);return st-top;
} 项目实现 //头文件
#pragma once#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef int STDataType;
typedef struct stack
{STDataType* data;int top; //栈顶位置int capacity; //元素个数
}ST;//栈的初始化
void STInit(ST* st);
//栈的销毁
void STDestroy(ST* st);
//数据入栈
void STPush(ST* st, STDataType x);
//数据出栈
void STPop(ST* st);
//判断栈是否为空
bool STEmpty(ST* st);
//获取栈顶元素
STDataType STTop(ST* st);
//获取栈内数据个数
int STSize(ST* st);//实现文件
#include stack.h//栈的初始化
void STInit(ST* st)
{//判断是否存在队列assert(st);//初始化队列st-data NULL;st-top 0;//栈顶指针指向存储数据的下一个位置代表栈内无数据//st-top -1;//栈顶指针指向存储数据的位置代表栈内无数据st-capacity 0;
}//栈的销毁
void STDestroy(ST* st)
{//确保有栈的存在assert(st);//销毁栈free(st-data);st-data NULL;//top和capacity更改为无数据的位置st-top st-capacity 0;
}//数据入栈
void STPush(ST* st, STDataType x)
{//确保有栈的存在assert(st);//向top位置增加数据并使top向后移动//需要判断栈的容量大小if (st-top st-capacity){//如果栈的空间为0则开辟四个空间如果栈容量不为0则扩容原来容量的2倍int newCapacity st-capacity 0 ? 4 : st-capacity * 2;STDataType* tmp (STDataType*)realloc(st-data, sizeof(STDataType) * newCapacity);assert(tmp);st-data tmp;//注意更新容量大小st-capacity newCapacity;}//数据压栈并改变topst-data[st-top] x;
}
//数据出栈
void STPop(ST* st)
{//确保有栈的存在assert(st);//确保栈不会越界assert(!STEmpty(st));//直接移动top指针“看不见即删除”st-top--;
}
//判断栈是否为空
bool STEmpty(ST* st)
{//确保有栈的存在assert(st);//栈为空返回真栈不为空返回假return st-top 0;//判断表达式返回值只有1和0如果为真返回1(true)如果为假返回0(false)
}
//获取栈顶元素
STDataType STTop(ST* st)
{//确保栈存在assert(st);//确保栈不为空assert(!STEmpty(st));//top为栈内数据的下一个位置要获取当前位置的元素需要-1操作return st-data[st-top - 1];
}//获取栈内数据个数
int STSize(ST* st)
{assert(st);return st-top;
}//测试文件
#define _CRT_SECURE_NO_WARNINGS 1#include stack.hvoid test()
{ST st { 0 };//初始化栈STInit(st);//数据压栈STPush(st, 1);STPush(st, 2);STPush(st, 3);STPush(st, 4);STPush(st, 5);//打印栈内数据while (!STEmpty(st)){//打印栈顶数据printf(%d , STTop(st));//数据出栈以打印下一个数据STPop(st);}//栈的销毁STDestroy(st);
}int main()
{test();return 0;
} 栈的基础练习 有效的括号 题目链接20. 有效的括号 - 力扣LeetCode 给定一个只包括 ( ) { } [ ] 的字符串 s 判断字符串是否有效。 有效字符串需满足 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 思路解析 本题可以使用栈来解决当括号为左侧括号时将括号存入栈内当括号为右侧括号时将该括号与栈顶的括号进行比较比较一次进行一次出栈操作 注意本题不一定要使用C语言来解决因为C语言本身不支持泛型需要单独先实现栈才能解题本题使用C语言和栈的思路仅供参考 参考答案 /** lc appleetcode.cn id20 langc** [20] 有效的括号*/// lc codestart
// 使用C语言和栈解决问题
// 栈的声明
typedef char STDataType;
typedef struct stack
{STDataType *data;int top; // 栈顶位置int capacity; // 元素个数
} ST;// 栈的初始化
void STInit(ST *st);
// 栈的销毁
void STDestroy(ST *st);
// 数据入栈
void STPush(ST *st, STDataType x);
// 数据出栈
void STPop(ST *st);
// 判断栈是否为空
bool STEmpty(ST *st);
// 获取栈元素
STDataType STTop(ST *st);// 栈的实现
// 栈的初始化
void STInit(ST *st)
{// 判断是否存在队列assert(st);// 初始化队列st-data NULL;st-top 0; // 栈顶指针指向存储数据的下一个位置代表栈内无数据// st-top -1;//栈顶指针指向存储数据的位置代表栈内无数据st-capacity 0;
}// 栈的销毁
void STDestroy(ST *st)
{// 确保有栈的存在assert(st);// 销毁栈free(st-data);st-data NULL;st-top st-capacity 0;
}// 数据入栈
void STPush(ST *st, STDataType x)
{// 确保有栈的存在assert(st);// 向top位置增加数据并使top向后移动// 需要判断栈的容量大小if (st-top st-capacity){// 如果栈的空间为0则开辟四个空间如果栈容量不为0则扩容原来容量的2倍int newCapacity st-capacity 0 ? 4 : st-capacity * 2;STDataType *tmp (STDataType *)realloc(st-data, sizeof(STDataType) * newCapacity);assert(tmp);st-data tmp;st-capacity newCapacity;}// 数据压栈并改变topst-data[st-top] x;
}
// 数据出栈
void STPop(ST *st)
{// 确保有栈的存在assert(st);// 确保栈不会越界assert(!STEmpty(st));// 直接移动top指针“看不见即删除”st-top--;
}
// 判断栈是否为空
bool STEmpty(ST *st)
{// 确保有栈的存在assert(st);// 栈为空返回真栈不为空返回假return st-top 0; // 判断表达式返回值只有1和0如果为真返回1(true)如果为假返回0(false)
}
// 获取栈元素
STDataType STTop(ST *st)
{// 确保栈存在assert(st);// 确保栈不为空assert(!STEmpty(st));// top为栈内数据的下一个位置要获取当前位置的元素需要-1操作return st-data[st-top - 1];
}// 判断是否是有效括号
bool isValid(char *s)
{// 基本思路左括号入栈右括号时左括号出栈与右括号比较// 创建栈用于保存数据ST st {0};// 初始化栈STInit(st);// 数据入栈while (*s){if (*s ( || *s [ || *s {){// 当是左括号时数据入栈STPush(st, *s);}else{// 如果栈为空直接返回falseif (STEmpty(st)){// 返回前释放空间因为尽管没有数据但是栈的空间已经开辟STDestroy(st);return false;}// 当是右括号时数据出栈与右括号比较char top STTop(st);// 更新栈内元素STPop(st);if ((*s ) top ! () || (*s ] top ! [) || (*s } top ! {)){// 此处找不同如果此处找相同那么但凡出现一对满足的括号就会进入返回true// 返回之前销毁栈防止内存泄漏STDestroy(st);return false;}}s;}// 如果栈为空则说明匹配完成如果不为空说明栈内仍有括号没有匹配到此时说明存在单独的括号bool ret STEmpty(st);// 返回之前销毁栈STDestroy(st);return ret;
}
// lc codeend
