数据结构——栈
1.概念
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
top始终指向栈顶元素
2.栈的实现
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。由下图就可以看出链表要使用更多的空间。
在栈中,通常提供以下几种接口
//初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);
//入栈,出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
//取栈顶数据
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取栈的元素个数
int STSize(ST* pst);
我们可以实现一个静态栈(数组的长度是一定),但是这种结构并不实用,我们接下来实现的是动态栈。
1.我们可以定义一个结构体( struct stack),其中有数组(SLDataType *a),栈顶元素的下标(top)和栈的空间(capacity)。
typedef int STDataType;
typedef struct Stack
{
STDataType* a;//数组
int top;
int capacity;
}ST;
2.栈的初始化和销毁:这里需要注意的是应该是将栈顶元素的下标初始化为多少呢?
通常为0.我们会将栈为空时状态定义为以下,但是如果将没有元素时top为0,这是top指向的就不是栈顶元素,而是栈顶元素的下一个元素。
//初始化和销毁
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;//top指向栈顶下一个元素
pst->capacity = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
3.栈为空的判断:我们可以用bool来代替if
//判空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
4.获取栈顶元素:这里要注意栈顶元素的下标是top-1
//取栈顶数据
STDataType STTop(ST* pst)
{
assert(pst&&pst->top>0);
return pst->a[pst->top - 1];
}
5.获取栈的元素个数:就是top
//获取栈的元素个数
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
6.入栈 :在数组尾部入栈,首先要检查一下capacity是否足够,若不够得扩容。
出栈:top--,并释放掉top
//入栈,出栈
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)//扩容
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a,sizeof(STDataType)* newcapacity);
if (tmp == NULL)//扩容没有成功
{
perror("relloc fail");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
void STPop(ST* pst)
{
assert(pst&&pst->top>0);
pst->top--;
}
总体来说,实现一个栈还是很容易的。考察的知识还不是很多。接下来可以实战一下,使用栈来解决括号匹配的问题。
思路:遍历数组,将左括号压入栈中,如果不是左括号,就与栈顶元素进行比较,遍历完成后,匹配也就完成
如果不是左括号,就要判断栈是不是为空,若为空,直接返回false,不为空,再取栈顶元素与之比较
遍历完之后,人要检查一下栈是否为空,若为空,说明匹配成功,若不为空,则匹配失败
主要代码如下
bool isValid(char* s) {
ST st;
STInit(&st);
while (*s) {
if (*s == '(' || *s == '[' || *s == '{') {
STPush(&st, *s);
} else {
if (STEmpty(&st)) {
STDestroy(&st);
return false;
}
char top = STTop(&st);
STPop(&st);
if ((top == '(' && *s != ')') || (top == '[' && *s != ']') ||
(top == '{' && *s != '}')) {
STDestroy(&st);
return false;
}
}
++s;
}
bool ret = STEmpty(&st);
STDestroy(&st);
return ret;
}
由于C语言不提供栈,所以我们必须自己实现。
原文地址:https://blog.csdn.net/2302_80339723/article/details/138914962
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!