赞
踩
感谢各位大佬的光临,希望和大家一起进步,望得到你的三连,互三支持,一起进步
之前讲了,很多关于栈的习题,还有栈与队列的互相转换,还是补一篇栈的详解
栈(stack)是一种只允许在一端进行插入和删除操作的线性表。这一端称为栈顶,另一端称为栈底。栈的特点是后进先出(LIFO),即最后进入的元素最先出来。栈可以用来存储局部变量和一些数据,当函数或线程执行完毕,栈就会释放空间。
这样的实现它分为两种,一种是用数组去实现栈,另一种就是用链表去实现栈,我们这里主要讲的是用数组去实现栈,用链表实现栈又叫做链式栈,如果用尾做为栈顶那么尾插尾删就要设计成双向链表,否则删除数据效率会很低。
- typedef int STDataType;
- typedef struct stack
- {
- STDataType* a;
- int top;
- int capacity
- }ST;
初始化时,top给的是0的话,意味着top栈顶数据的指向下一个,top给-1的话,意味着top就是栈顶数据
- void stackInit(ST* ps)
- {
- assert(ps);
- ps->a = NULL;
- ps->top = 0;//ps->top=-1;
- ps->capacity = 0;
- }
这里和顺序表的扩容和插入一模一样
- void stackPush(ST* ps, STDataType x)
- {
- assert(ps);
- //检查扩容
- if (ps->top == ps->capacity)
- {
- int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
- STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);
- assert(tmp);
- ps->a = tmp;
- ps->capacity = newcapacity;
- }
- ps->a[ps->top] = x;
- ps->top++;
-
- }
我初始化的top为0,所以取栈顶元素的下标是top-1
- void stackPop(ST* ps)
- {
- assert(ps);
- assert(ps->top > 0);
- ps->top--;
- }
-
- STDataType stackTop(ST* ps)
- {
- assert(ps);
- assert(ps->top > 0);
- //我初始化的top为0,所以取栈顶元素的下标是top-1
- return ps->a[ps->top -1 ];
- }
- bool stackEmpty(ST* ps)
- {
- assert(ps);
- //说明栈里没有元素了
- if (ps->top == 0)
- return true;
- else
- return false;
- }
- void stackDestroy(ST* ps)
- {
- assert(ps);
- free(ps->a);
- ps->a = NULL;
- ps->capacity = ps->top = 0;
- }
然后我们来看一道例题
给定一个只包括
'('
,')'
,'{'
,'}'
,'['
,']'
的字符串s
,判断字符串是否有效。有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()" 输出:true 输入:s = "(]" 输出:false
我们先断言一下传来的不能是空指针,然后对栈进行初始化,然后设置一个循环,意思是说等这个字符串走完了之后这个循环就出了,第一步判断我们先得让左括号入栈,如果是左括号的就入栈,然后字符串加加
- assert(s);
- ST st;
- stackInit(&st);
- while (*s)
- {
- if (*s == '(' || *s == '{' || *s == '[')
- {
- stackPush(&st, *s);
- s++;
- }
然后如果不是左括号我们就可以进行第一次判断了,如果遇到了右括号,但是栈里没有数据,说明前面没有右括号不匹配,我们直接退出,如果不是这个错误的话,我们就可以取栈顶元素,把这个括号取出来删掉,然后进行左括号匹配,如果不是就直接退出,注意:stackDestroy(&st);为什么我要提前放不在后面放,因为我在这里就退出了存在开屏内存没有释放会造成内存泄露。
- else
- {
- if (stackEmpty(&st))
- {
- return false;
- }
- STDataType top = stackTop(&st);
- stackPop(&st);
- if ((*s == ')' && top != '(') || (*s == '}' && top != '{') || (*s == ']' && top != '['))
- {
- stackDestroy(&st);
- return false;
- }
- else {
- s++;
- }
-
- }
如果只有左括号没有右括号呢,所以我的结尾判断还需要特殊一点,如果栈里还有元素的话就说明还存在左括号没有出去没有匹配,所以我也不能返回正确
- bool ret = stackEmpty(&st);
- stackDestroy(&st);
- return ret;
注意这个题目是符号判断,所以我的STDataType是char类型的
- typedef char STDataType;
- typedef struct stack
- {
- STDataType* a;
- int top;
- int capacity;
- }ST;
-
- void stackInit(ST* ps)
- {
- assert(ps);
- ps->a = NULL;
- ps->top = 0;
- ps->capacity = 0;
- }
-
- void stackPush(ST* ps, STDataType x)
- {
- assert(ps);
- //检查扩容
- if (ps->top == ps->capacity)
- {
- int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
- STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
- assert(tmp);
- ps->a = tmp;
- ps->capacity = newcapacity;
- }
- ps->a[ps->top] = x;
- ps->top++;
-
- }
-
- void stackDestroy(ST* ps)
- {
- assert(ps);
- free(ps->a);
- ps->a = NULL;
- ps->capacity = ps->top = 0;
- }
-
- void stackPop(ST* ps)
- {
- assert(ps);
- assert(ps->top > 0);
- ps->top--;
- }
-
- STDataType stackTop(ST* ps)
- {
- assert(ps);
- assert(ps->top > 0);
- return ps->a[ps->top - 1];
- }
-
- bool stackEmpty(ST* ps)
- {
- assert(ps);
- if (ps->top == 0)
- return true;
- else
- return false;
- }
- bool isValid(char* s)
- {
- assert(s);
- ST st;
- stackInit(&st);
- while (*s)
- {
- if (*s == '(' || *s == '{' || *s == '[')
- {
- stackPush(&st, *s);
- s++;
- }
- else
- {
- if (stackEmpty(&st))
- {
- return false;
- }
- STDataType top = stackTop(&st);
- stackPop(&st);
- if ((*s == ')' && top != '(') || (*s == '}' && top != '{') || (*s == ']' && top != '['))
- {
- stackDestroy(&st);
- return false;
- }
- else {
- s++;
- }
-
- }
-
- }
-
- bool ret = stackEmpty(&st);
- stackDestroy(&st);
- return ret;
-
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。