当前位置：首页 > article >正文

栈----数据结构

article 2024/12/22 15:32:55

在这里插入图片描述

栈

🔆栈的概念
🔆栈的结构
🔆栈的实现
🔆括号匹配问题
🔆结语

🔆栈的概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。**进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。**栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

🔆栈的结构

在这里插入图片描述

🔆栈的实现

数组栈gitt代码链接

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

数组栈
链式栈

🔆括号匹配问题

OJ链接

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例一：

输入：s = “()”
输出：true

示例二：

输入：s = “()[]{}”
输出：true

示例三：

输入：s = “(]”
输出：false

解题思路：

在这里插入图片描述

答案：

//动态栈的实现
typedef char STDataType;

typedef struct Stack {
	STDataType* a;
	//top 指向栈顶
	int top;
	//capacity表示栈的容量
	int capacity;
}ST;

//创建栈
ST* STCreate() {
	ST* stack = (ST*)malloc(sizeof(ST));
	if (stack == NULL) {
		perror("malloc::");
		return NULL;
	}
	STInit(stack);
	return stack;
}

//栈的初始化
void STInit(ST* ps) {
	assert(ps);
	ps->a = NULL;
	//top为-1时表示指向栈顶，top为0时表示指向栈顶的下一个
	ps->top = -1;
	ps->capacity = 0;
}

//栈的判空
bool STEmpty(ST* ps) {
	assert(ps);
	return ps->top == -1;
}

//栈的判满
bool STFull(ST* ps) {
	assert(ps);
	return (ps->top + 1 == ps->capacity);
}

//入栈
void STPush(ST* ps, STDataType val) {
	assert(ps);
	if (STFull(ps)) {
		int newcapacity = ((ps->capacity == 0) ? 4 : (2 * ps->capacity));
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL) {
			perror("realloc::");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	(ps->top)++;
	ps->a[ps->top] = val;
}

//出栈
void STPop(ST* ps) {
	assert(ps);
	assert(!STEmpty(ps));
	(ps->top)--;
}

//获取栈元素个数
int STSize(ST* ps) {
	assert(ps);
	return (ps->top) + 1;
}

//获取栈顶元素
STDataType STTop(ST* ps) {
	assert(ps);
	return ps->a[ps->top];
}

//销毁栈
void STDestroy(ST* ps) {
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = -1;
	ps->capacity = 0;
	free(ps);
}

bool isValid(char* s){
    int len = strlen(s);
    if (len <= 1) {
        return false;
    }

    ST* st = STCreate();

    char* cur = s;
    while (*cur) {
        if (*cur == '(' || *cur == '[' || *cur == '{') {
            STPush(st, *cur);
        }else if (*cur == ')' || *cur ==']' || *cur == '}') {
            if (STEmpty(st) || 
            (*cur == ')' && STTop(st) != '(') || 
            (*cur == ']' && STTop(st) != '[') || 
            (*cur == '}' && STTop(st) != '{')) {
                return false;
            }

            STPop(st);
        }
        cur++;
    }

    if (!STEmpty(st)) {
        return false;
    }

    STDestroy(st);
    st = NULL;

    return true;
}