网站做细分领域,淄博三合一网站开发,网站建设互联,厦门专业网站建设目录
栈的概念及结构
栈的实现
创建栈
栈的初始化
入栈
出栈
取出栈顶数据
判断栈是否为空
有效数据个数
栈的销毁
全代码
stack.h
stack.c
应用
题目
示例
解题思路
代码实现 栈的概念及结构 栈是一种特殊的线性表#xff0c;其只允许在固定的一端进行插入…目录
栈的概念及结构
栈的实现
创建栈
栈的初始化
入栈
出栈
取出栈顶数据
判断栈是否为空
有效数据个数
栈的销毁
全代码
stack.h
stack.c
应用
题目
示例
解题思路
代码实现 栈的概念及结构 栈是一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。你也可以一边入一边出。 栈顶和栈底并不是固定的这是人为决定的。
栈的实现 栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。 以下的内容如果你对顺序表的实现熟悉的话就很简单。
创建栈 栈的创建需要有指向动态数组指针栈顶数据下标和容量。
typedef int STDataType;typedef struct Stack
{STDataType* arr;//指向动态数组指针int top;//栈顶数据下标int capacity;//容量
}ST;栈的初始化 将arr置为空指针top置为-1capacity置为0。
//初始化
void STInit(ST* pst)
{assert(pst);pst-arr NULL;pst-top -1;pst-capacity 0;
} 这里的top为什么要是-1呢 一般来说top应该也是0这里是-1是为了确保top是栈顶数据的下标。当然了你要是想写0也是可以的。 入栈 入栈又称压栈进栈。 首先要判断容量是否够用如果不够用的话就扩容。然后再把数据塞入即可。 //入栈
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-top 1 pst-capacity){pst-capacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* p (STDataType*)realloc(pst-arr, sizeof(STDataType) * pst-capacity);if (p NULL){perror(realloc);return;}pst-arr p;}pst-arr[pst-top] x;
} 注意这里要前置如果后置就会造成非法访问。如果top是0就要后置了。 出栈 这里要另外判断一下栈是否为空。然后只要让top--即可。 //出栈
void STPop(ST* pst)
{assert(pst);assert(pst-top -1);pst-top--;
} 取出栈顶数据 这里也要判断一下栈是否为空。然后返回下标top对应的数据即可。
//取出出栈顶数据
STDataType STTop(ST* pst)
{assert(pst);assert(pst-top -1);return pst-arr[pst-top];
} 判断栈是否为空 直接返回pst-top-1即可。
//判断栈是否为空
bool STEmpty(ST* pst)
{assert(pst);return pst-top -1;
} 该函数类型要是布尔类型。 如果top-1则返回true否则返回false。 有效数据个数 直接返回top1即可。
//有效数据个数
int STSize(ST* pst)
{assert(pst);return pst-top 1;
} 栈的销毁 用free销毁arr并将它置为空指针。其它的置为初始化值即可。
//销毁
void STDestroy(ST* pst)
{assert(pst);free(pst-arr);pst-arr NULL;pst-top -1;pst-capacity 0;
}
全代码
stack.h
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.htypedef int STDataType;typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;//初始化
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);
stack.c
#include stack.h//初始化
void STInit(ST* pst)
{assert(pst);pst-arr NULL;pst-top -1;pst-capacity 0;
}//入栈
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-top 1 pst-capacity){pst-capacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* p (STDataType*)realloc(pst-arr, sizeof(STDataType) * pst-capacity);if (p NULL){perror(realloc);return;}pst-arr p;}pst-arr[pst-top] x;
}//出栈
void STPop(ST* pst)
{assert(pst);assert(pst-top -1);pst-top--;
}//取出栈顶数据
STDataType STTop(ST* pst)
{assert(pst);assert(pst-top -1);return pst-arr[pst-top];
}//判断栈是否为空
bool STEmpty(ST* pst)
{assert(pst);return pst-top -1;
}//有效数据个数
int STSize(ST* pst)
{assert(pst);return pst-top 1;
}//销毁
void STDestroy(ST* pst)
{assert(pst);free(pst-arr);pst-arr NULL;pst-top -1;pst-capacity 0;
}
应用
题目 该题链接 https://leetcode.cn/problems/valid-parentheses/description/
示例 解题思路 这题根据栈的后进先出和边入边出的特性可以解决。 创建一个栈只让左括号入栈让右括号与栈里的数据匹配。如果匹配成功让左括号出栈继续该操作直至字符串遍历完。如果匹配不成功则直接退出。 有几个要注意的点 字符串只有右括号字符串只有左括号或只剩左或右括号arr是int的类型要把它改成char类型 代码实现
bool isValid(char* s)
{ST st;STInit(st);while(*s){if(*s ( || *s [ || *s {){STPush(st, *s);}else{if(st.top -1)//字符串只有右括号{STDestroy(st);return false;}STDataType top STTop(st);if(*s ) top ! ( || *s ] top ! [ || *s } top ! {){STDestroy(st);return false;}STPop(st);}s;}bool ret STEmpty(st);//字符串只有左括号或只剩左或右括号STDestroy(st);return ret;
}
