如何360收录网站,写字楼装修公司,dedecms织梦搬家公司网站模板,最好的网站建设多少钱本节讲完栈下次再讲一下队列#xff0c;最后补充一个串#xff0c;我们的线性结构基本就完事了。下图中黄色框框圈中的是我们今日份内容(分为两篇博客)#xff1a;
知识体系图 栈(Stack-LIFO)结构
栈的基础概念
栈(Stack)是一个后进先出(Last-In-First-Out)的一个特殊数据… 本节讲完栈下次再讲一下队列最后补充一个串我们的线性结构基本就完事了。下图中黄色框框圈中的是我们今日份内容(分为两篇博客)
知识体系图 栈(Stack-LIFO)结构
栈的基础概念
栈(Stack)是一个后进先出(Last-In-First-Out)的一个特殊数据结构只有一端可以操作三面环墙。按照存储方式可以分为顺序存储的栈和链式存储的栈(即顺序栈和链栈)另外还有一些特殊的栈需要我们了解单调栈、共享栈。
不管什么栈它的基本API接口(基本操作)都是入栈(Push)出栈(Pop)查看栈顶元素(Top/Peek)判断栈是否为空(isEmpty)。 栈顶top处于可以插入或删除元素的一端栈顶指针指向非空元素的下一个位置
栈底base处于不能插入或删除元素的另一端栈底指针固定指向。
空栈empty栈内不包含任意元素栈顶指针与栈底指针指向同一位置。
顺序栈
采用顺序结构存储的栈称为顺序栈它的底层是数组使用的是一段地址连续的空间。另外找一个尾指针充当栈顶指针指向栈顶元素的位置的下一个地址。判断栈为空的条件就是栈顶指针指向栈底。
1.栈的顺序存储
站的顺序存储结构可以定义为一个栈底指针一个栈顶指针
#define INIT_MAX_SIZE 20 //初始化栈时给的最大容量
typedef int DataType;//DataType的类型不确定根据习惯初始假定为int
typedef struct{DataType* base;DataType* top;
}SqStack;2.栈的基本操作
初始化
初始化时使用预先设置好的初值来开辟大小并且初始一定是空栈所以让栈顶指针指向栈底即可。
void initStack(SqStack* s)
{s-base (DataType*)malloc(sizeof(DataType)*INIT_MAX_SIZE);s-top s-base;
}
判空
如果栈顶指针与栈底指针指向同一块空间那么栈就是空的直接返回。这里传不传指针都可以不需要进行修改的操作只进行判断所以利用值传递也能实现目的
#include stdbool.h
bool isEmpty(SqStack s){return s.base s.top;
}
bool isEmpty(SqStack* s){return s-base s-top;
}
进栈
进栈之前我们先判断栈是否为满如果满栈我们不能随便加入需要扩容我们选择二倍扩容的方式如果扩容失败结束程序一旦我们扩容成功我们原来的栈顶指针也会失效使用栈底指针加上原来的满栈数跨越总步长回到栈顶的相对位置。然后将栈顶设置为元素e并自动跨越一个步长()。
/*插入元素e为新的栈顶元素*/
void Push(SqStack *s, DataType e){//满栈if(s-top s-base INIT_MAX_SIZE){int size INIT_MAX_SIZE*2;s-base (DataType*)realloc(s-base,sizeof(DataType)*size);assert(s-base);s-top s-base size/2;}*(s-top) e; //将新插入元素赋值给栈顶空间s-top; //更改栈顶指针//可以合并为*(s-top)e;
}
出栈
出栈就是要后面的元素无法访问那么只需要将栈顶指针缩减一个步长(--)即可但在此之前我们需要判断是不是空栈如果是空栈我们就没必要去进行出栈的操作了。
/*若栈不空则删除S的栈顶元素*/
void Pop(SqStack *s){if(s-top s-base){return;}S-top--; //栈顶指针减1
}获取栈顶元素
获取栈顶元素我们需要获取的栈顶指针上一个位置内存储的内容所以我们进行完判空操作后我们需要对s-top-1进行解引用(即取*)的操作。
/*读栈顶元素*/
DataType Top(SqStack s){if(s-top s-base){ //栈空return -1;}return *(s-top-1); //返回栈顶元素
}销毁栈
void destory(SqStack* s){if(s-base){free(s-base);s-tops-baseNULL;}
}
3.单调栈专题
从名字上我们就可以看出来单调栈中存放的数据应该是有序的所以单调栈本身也应该分为单调递增栈和单调递减栈。单调的方向是从栈底到栈顶。
在进行单调栈的讲解时我们会使用到上述的一些基本操作。我们来看一下单调栈的入栈过程
typedef int DataType;//此处选取int作为示例for (遍历这个数组)
{if (栈空 || 栈顶元素大于等于当前比较元素){入栈;}else{while (栈不为空 栈顶元素小于当前元素){栈顶元素出栈;更新结果;}当前数据入栈;}
}真题演练 柱状图中的最大矩形 思路当前的数字可以向两边拓展遇到比自己大的就接着拓展小的就停止然后用自己的高度乘以拓展的宽度每次都更新最大面积时间复杂度同样为O(N^2)所以我们接着借助单调栈 这里我们通过这道例题来使用一下单调递减栈 1.设置一个单调递减的栈栈内0~n为单调递增 2.当遇到小于栈顶元素的值我们开始更新数据因为有可能最大面积就会出现在栈中的序列里 3.牢记栈中数据永远是有序的这个问题比较复杂所以读者不妨对照着代码来理解问题 int largestRectangleArea(vectorint heights) {heights.push_back(-1);/同理我们希望栈中所有数据出栈所以给数组最后添加一个负数SqStack st; initStack(st);int ret 0, top;for (int i 0; i heights.size(); i){if (isEmpty(st) || heights[Top(st)] heights[i]){Push(st,i);}else{while (!isEmpty(st) heights[Top(st)] heights[i]){top Top(st);Pop(st);//i-top指的是当前矩形的宽度heights[top]就是当前的高度//再次强调栈中现在为单调递增int tmp (i - top)*heights[top];if (tmp ret)ret tmp;}Push(top);heights[top] heights[i];}}return ret;
}4.共享栈专题 利用栈底位置相对不变的特征可让两个顺序栈共享一个一维数组空间将两个栈的栈底分别设置在共享空间的两端两个栈顶向共享空间的中间延伸如下图所示 两个栈共享同一片存储空间这片存储空间不单独属于任何一个栈某个栈需要的多一点它就可能得到更多的存储空间两个栈的栈底在这片存储空间的两端当元素入栈时两个栈的栈顶指针相向而行。此时我们采取另外一种实现栈的方法不使用真正的指针使用下标索引模拟两个栈顶指针。定义方法如下 #define SharedStackMax 100typedef char SharedStackType;typedef struct{SharedStackType data[SharedStackMax];size_t top1;size_t top2;}SharedStack;
共享栈的基本操作方法 void SharedStackInit(SharedStack*stack){if(stackNULL){return;}stack-top10;stack-top2SharedStackMax;}void SharedStackPush1(SharedStack*stack,SharedStackType value){if(stack-top1stack-top2||stackNULL){return;}stack-data[stack-top1]value;return;}void SharedStackPush2(SharedStack*stack,SharedStackType value){if(stack-top2stack-top1||stackNULL){return;} stack-data[--stack-top2]value;}int SharedStackTop1(SharedStack*stack,SharedStackType*value){if(stackNULL||valueNULL){return 0;}if(stack-top10){return 0;}*valuestack-data[top1-1];return 1;}int SharedStackTop2(SharedStack*stack,SharedStackType*value){if(stackNULL||valueNULL){return 0;}if(stack-top2SharedStackMax){return 0;}*valuestack-data[stack-top2];return 1;
}void SharedStackPop1(SharedStack*stack){if(stackNULL || stack-top10){return;}stack-top1--;}void SharedStackPop2(SharedStack*stack){if(stack-top2SharedStackMax || stackNULL){return;}stack-top2;} 链栈
1.栈的链式存储
采用链式存储的栈称为链栈链栈的优点是便于多个栈共享存储空间和提高其效率且不存在栈满上溢的情况我们就省去了不断扩容的麻烦。通常采用不带头结点的单链表实现而且为了方便使用头插法头删法更简单所以我们的入栈和出栈就是单链表的头插和头删的操作。Lhead指向栈顶元素链栈的结构图如下所示 对于链栈来说空栈的概念即是Lhead指向NULL的时候。
/*构造节点*/
typedef struct StackNode{ElemType data;struct StackNode *next;
}StackNode, *LinkStackPrt;
//将StackNode* 重命名为LinkStackPrt的好处是避免下面操作出现二级指针的形式。(实质还是二级指针)/*构造链栈*/
typedef struct LinkStack{LinkStackPrt top;int count;
}LinkStack;2.链栈的基本操作
链栈的进栈
对于链栈的进栈push操作我们会创建一个栈节点然后进行链表的头插操作。
void Push(LinkStack *S, ElemType e){LinkStackPrt p (LinkStackPrt)malloc(sizeof(StackNode));p-data e;p-next S-top; //把当前的栈顶元素赋值给新节点的直接后继S-top p; //将新的结点S赋值给栈顶指针S-count;
}链栈的出栈
无需多说头删即可
Element Pop(LinkStack *S){if(StackEmpty(*S)){return -1;}Element e S-top-data;//临时存储栈顶元素LinkStackPtr p;p S-top; //将栈顶结点赋值给pS-top S-top-next; //使得栈顶指针下移一位指向后一结点free(p); //释放结点pS-count--;return e;
}栈的算法应用
递归专题
我们将递归时就提到过递归是函数的递进调用与返回而函数的调用与销毁又是以栈的形式进行的。所以能用栈解决的问题一定可以用递归解决。而能用递归的方式解决的问题栈不一定能解决但一定依托于栈的形式结构。因为对于栈结构本身来讲是作为一个容器来用的递归才是存储一系列操作这种非数据类型的特殊栈结构。
基础算法--递归算法【难点、重点】-CSDN博客 调用堆栈每次递归调用时栈上会创建一个新的堆栈帧用于存储该调用的上下文。 空间复杂度递归的深度可能导致栈溢出尤其在递归深度较大而没有适当的基本情况时。 迭代替代有些递归算法可以用显式栈或循环来实现从而避免递归带来的栈溢出问题。 四则运算表达式专题
四则运算在这里的应用其实包括后缀表达式和前缀表达式以及我们平常熟悉的中缀表达式。
缀所处的位置不同代表的含义是四则运算符所处的位置不同。例如 ab*(c/d2)中缀表达式 * a b c前缀表达式 (ab)*c a b c d - * e f / -后缀表达式 ab*(c-d)-e/f 四则运算表达式的专题我们以一道例题作为训练逆波兰表达式(前缀表达式)。 逆波兰表达式是一种把运算符前置的算术表达式例如普通的表达式2 3的逆波兰表示法为 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系也不必用括号改变运算次序例如(2 3) * 4的逆波兰表示法为* 2 3 4。本题求解逆波兰表达式的值其中运算符包括 - * /四个。 对于原逆波兰表达式- * - c d b a / e f
当我们遇到符号时将其入栈等到下面两个是数字时再出栈如果遇到数字直接让其入栈然后出栈。我们对下面的图进行详细的步骤分析 文字配合图片食用效果更甚哦 下面给出代码
#include bits/stdc.h
using namespace std;/*逆波兰表达式*/
string st -*/;
double calc() {string str; cin str;switch (str[0]) {case :return calc() calc();case -:return calc() - calc();case *:return calc() * calc();case /:return calc() / calc();default:return stod(str);}
}
signed main() {printf(%f\n, calc());return 0;
} 感谢大家观看多多支持哦
