自学内容网 自学内容网

数据结构——栈

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--;
}

总体来说,实现一个栈还是很容易的。考察的知识还不是很多。接下来可以实战一下,使用栈来解决括号匹配的问题。

 .  - 力扣(LeetCode)

思路:遍历数组,将左括号压入栈中,如果不是左括号,就与栈顶元素进行比较,遍历完成后,匹配也就完成

如果不是左括号,就要判断栈是不是为空,若为空,直接返回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)!