企业网站 自助建站,云兰装潢公司总部地址电话,网站建设软件是什么意思,林州企业网站建设一.栈的基本概念
栈是一种特殊的表#xff0c;这种表只在表首进行插入和删除操作。 因此#xff0c;表首对于栈来说具有特殊的意义#xff0c;称为栈顶。相应的#xff0c;表尾称为栈底。不含任何元素的栈称为空栈。 栈的修改遵循后进先出的原则#xff0c;Last In First…一.栈的基本概念
栈是一种特殊的表这种表只在表首进行插入和删除操作。 因此表首对于栈来说具有特殊的意义称为栈顶。相应的表尾称为栈底。不含任何元素的栈称为空栈。 栈的修改遵循后进先出的原则Last In First Out可以想象成一个水桶。
二.常用的栈运算
栈也是一个抽象数据类型。常用的栈运算如下 1StackEmpty(S):测试栈S是否为空 2StackFull(S):测试栈S是否以满 3StackTop(S):返回栈S的栈顶元素 4Push(x,S):在栈S的栈顶插入元素x简称为将元素x入栈 5Pop(S):删除并返回栈S的栈顶元素简称为抛栈
三.栈的实现
1.用数组实现栈
实现与表类似只不过要实现的运算不同。略
2.用指针实现栈
用这种方法实现的栈也叫做链栈。 因为栈是一种特殊的表所以实现与表类似只不过要实现的运算不同。
四.栈的应用
例一在对用高级语言编写的程序进行编译时会遇到表达式或字符串的括号匹配问题。 在从左到右逐个字符对给定的表达式expr进行扫描的过程中将所遇到的左括号存入一个栈中。每当扫描到一个有括号时如果栈非空就将其与栈顶的左括号想匹配并从栈顶删除该左括号若栈已空则所遇到的右括号不匹配。在完成对表达式的扫描后若栈非空则留在栈中的左括号均不匹配。
例二直方图最大面积矩形问题--单调栈
直方图最大面积矩形问题要找出包含在这个直方图中边平行于坐标轴的最大面积矩形。每个直条的宽度均为1。如上当给出的h[6,2,5,4,5,1,6]时最大面积矩形的面积是12。 设最大面积矩形为s则易知与其相交的直条中高度最小的直条整个包含在s中。而对直方图中的每个高度为h[i]的直条i都有一个包含该直条的最大矩形设其面积为a[i]。显而易见直方图最大面积矩形s的面积是当i取1到n的a[i]中的最大值。因此关键问题是对每个高度为h[i]的直条i计算包含该直条的最大矩形a[i]。(化归转化) 要计算a[i]就要计算直条i的左侧距i最近的高度小于h[i]的直条位置l(i)和直条i的右侧距i最近的高度小于h[i]的直条位置r(i)。由l(i)和r(i)的值可得a[i]h[i]*(r(i)-l(i)-1)。为此目的可以用一个栈stk来存储直条i的位置l(i)。从左到右依次考察直条并根据栈顶元素的值来计算a[i]。
int histo() {//首先创建一个栈 stk并初始化为空栈。 Stack stkStackInit(n);//定义变量 i 和 max分别表示遍历直方图数组的索引和最大矩形面积。int i0,max0;//进入循环循环条件是 i n即遍历直方图数组遍历的直方图遇到比它大的栈顶栈顶弹出直到遇到比它小的才入栈。 while(in) {//在循环内部首先检查栈是否为空或者当前直方图高度大于等于栈顶元素所对应的高度。//如果满足条件则将当前索引 i 入栈并将 i 加 1。if(StackEmpty(stk)||h[StackTop(stk)]h[i])Push(i,stk);//如果不满足条件说明当前直方图高度小于栈顶元素所对应的高度。此时需要计算以栈顶元素为高度的矩形的面积。 else {//首先将栈顶元素出栈并保存在变量 tmp 中。int tmpStackTop(stk);Pop(stk);//计算矩形的面积即高度乘以宽度保存在变量 a 中。//怎么计算矩形的宽度呢 //如果栈为空则宽度为当前索引 i //【因为如果栈为空说明出栈的元素为第一个元素那么宽度刚好就是索引1//如果不是也就是说右侧的直方图都出栈右侧的直方图高度递减宽度也为索引】 //否则宽度为当前索引 i 减去栈顶元素对应的索引再减去 1。//【简单说如果不为空此时栈中的直方图是单调递增的但考虑那些弹出的直方图都比此时直方图小所以就为i-StackTop(stk)-1】 int ah[tmp]*(StackEmpty(stk)?i:i-StackTop(stk)-1);//如果当前矩形面积 a 大于最大面积 max则更新 max 的值。if(maxa)maxa;}}//此时栈中剩余直方图是单调递增的重新遍历 //保证对每个高度为h[i]的直条i计算包含该直条的最大矩形awhile(!StackEmpty(stk)) {//下面操作和上面一样 int tmpStackTop(stk);Pop(stk);int ah[tmp]*(StackEmpty(stk)?i:i-StackTop(stk)-1);if(maxa)maxa;}//返回最大值return max;
}
