网站左下角留言板html,阜新建设网站,seo中介平台,wordpress 彩色源码目录 前言 1. 栈 1.1栈的概念及结构 1.2 栈的实现 1.2.1 栈的定义 1.2.2 栈的初始化 1.2.3 入栈 1.2.4 出栈 1.2.5 栈的元素个数 1.2.6 栈顶数据 1.2.7 栈的判空 2.栈的应用 2.1 题目一#xff1a;括号匹配 2.1.1 思路 2.1.2 分析 2.1.3 题解 总结 前言 无论你是计算机科学专… 目录 前言 1. 栈 1.1栈的概念及结构 1.2 栈的实现 1.2.1 栈的定义 1.2.2 栈的初始化 1.2.3 入栈 1.2.4 出栈 1.2.5 栈的元素个数 1.2.6 栈顶数据 1.2.7 栈的判空 2.栈的应用 2.1 题目一括号匹配 2.1.1 思路 2.1.2 分析 2.1.3 题解 总结 前言 无论你是计算机科学专业的学生、程序设计的爱好者还是正在准备面试的求职者本文将为你提供一份全面而深入的栈和队列指南。让我们一起探索栈和队列的双重魅力为你的编程之路增添新的色彩。 1. 栈
1.1栈的概念及结构 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。 栈中的数据元素遵守后进先出LIFOLast In First Out的原则。
压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶。 1.2 栈的实现 栈的实现方法有两种一种是顺序表的栈另外一种就是链表实现的栈。相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小所以这里我们使用顺序表来实现栈。 如果熟练顺序表和链表操作那栈就会相当轻松栈的入栈出栈就相当于是尾插尾删顺序表尾插尾删的效率高这也是使用顺序表实现的原因。
1.2.1 栈的定义
首先我们需要先定义一个栈
typedef int Datatype;
typedef struct Stack
{Datatype* a;int top;int capacity;
}Stack; 栈中有栈顶top有栈的容量size还有存储的数据a 1.2.2 栈的初始化 void InItStack(Stack* ps)
{assert(ps);ps-top 0;ps-a NULL;ps-capacity 0;
} 这里对栈进行初始化时栈顶top可以置为-1也可以置为0置为0为了便于使用top作为数组下标插入数据。
1.2.3 入栈 栈已经定义完成并且进行了初始化接下来就是入栈操作。这里与顺序表的尾插略微有些不同。
void StackPush(Stack* ps, Datatype x)
{assert(ps);if (ps-top ps-capacity){int newcapacity (ps-capacity 0 ? 4 : ps-capacity * 2);Datatype* tmp (Datatype*)realloc(ps-a, sizeof(Datatype) * newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newcapacity;}ps-a[ps-top] x;//top初始化为0可以直接作为数组下标ps-top;//入栈后top便于统计元素个数和下次入栈
} 由于我们初始化时将栈的容量置为0在这里我们在入栈操作时就需要进行开辟空间但这里如果我们使用malloc开辟空间就还需要进行扩容操作所以我们直接使用realloc进行开辟空间。 realloc在扩容时如果原始区域空间为0那么它的作用就类似于malloc。 此外我们还需要有新开辟空间的大小这里我们直接使用一个判断语句newsize (ps-size 0 ? 4 : ps-size * 2); 如果size等于0就开辟4个存储数据的空间如果不等于0就直接扩容为2倍。
1.2.4 出栈 出栈操作就很简单了也不需要销毁直接进行top--
void StackPop(Stack* ps)
{assert(ps);assert(ps-top 0);ps-top--;
} 但我们需要注意栈为空的情况所有使用assert强制检查如果为空直接报错终止程序简单粗暴。
1.2.5 栈的元素个数
统计栈的元素个数接口也很简单top就是栈中元素的个数
int Stacksize(Stack* ps)
{assert(ps);return ps-top;
}
1.2.6 栈顶数据
Datatype TopData(Stack* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}
这个也非常简单需要注意栈为空的情况。
1.2.7 栈的判空
bool IsEmpty(Stack* ps)
{assert(ps);return (ps-top 0);
} 2.栈的应用 这些栈的基本操作我们已经实现了接下来我们来实际应用一下。虽然栈的基本操作更为简单但是栈在应用时数据的结构更加复杂前边的顺序表和链表是栈和队列的基础。 2.1 题目一括号匹配 这道题目我们可以使用数组实现并解决但我们已经了解了栈这道题目我们就使用顺序表栈来实现。我们可以直接复制上述栈基本操作的代码。将 typedef int Datatype; 改为typedef char Datatype;
题目描述 示例 题目链接
有效括号
2.1.1 思路 这道题目的思路很明确入栈左括号遇到匹配的右括号就出栈。如果最终栈为空就匹配成功。但匹配失败的情况有很多接下来我们进行逐个分析。 2.1.2 分析 首先是入栈如果为左括号就入栈为右括号就匹配出栈。这里使用if…else语句更为简洁入栈就需要我们调用入栈的函数接口。 其次就是匹配、出栈。但在匹配之前我们还需要考虑特殊情况就是如果没有出栈元素就直接匹配的情况所以首先我们需要有一个判空操作如果匹配时栈就为空就直接匹配失败并销毁栈这个属于左括号与右括号数量匹配失败。 接着就是顺序匹配失败这里就需要我们用到栈顶元素了如果栈顶元素与匹配的括号不匹配就直接返回false匹配失败销毁栈。 最后匹配结束存放括号数组为空栈也为空就匹配成功。 2.1.3 题解
匹配括号接口
bool isValid(char* s) {Stack st;InItStack(st);char top;while (*s){if (*s ( || *s [ || *s {){StackPush(st, *s);}else{if(IsEmpty(st)){DestoryStack(st);return false;}topTopData(st);StackPop(st);if((*s]top![)||(*s)top!()||(*s}top!{)){DestoryStack(st);return false;}}s;}bool ret IsEmpty(st);DestoryStack(st);return ret;
}
整体代码
typedef char Datatype;
typedef struct Stack
{Datatype* a;int top;int size;
}Stack;void InItStack(Stack* ps);void DestoryStack(Stack* ps);void StackPush(Stack* ps, Datatype x);void StackPop(Stack* ps);int Stacksize(Stack* ps);Datatype TopData(Stack* ps);bool IsEmpty(Stack* ps);void InItStack(Stack* ps)
{assert(ps);ps-top 0;ps-a NULL;ps-size 0;
}void DestoryStack(Stack* ps)
{assert(ps);ps-top ps-size 0;free(ps-a);ps-a NULL;
}
void StackPush(Stack* ps, Datatype x)
{assert(ps);if (ps-top ps-size){int newsize (ps-size 0 ? 4 : ps-size * 2);Datatype* tmp (Datatype*)realloc(ps-a, sizeof(Datatype) * newsize);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-size newsize;}ps-a[ps-top] x;ps-top;
}
void StackPop(Stack* ps)
{assert(ps);assert(ps-top 0);ps-top--;
}
int Stacksize(Stack* ps)
{assert(ps);return ps-top;
}
Datatype TopData(Stack* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}
bool IsEmpty(Stack* ps)
{assert(ps);return (ps-top 0);
}
bool isValid(char* s) {Stack st;InItStack(st);char top;while (*s){if (*s ( || *s [ || *s {){StackPush(st, *s);}else{if(IsEmpty(st)){DestoryStack(st);return false;}topTopData(st);StackPop(st);if((*s]top