网站界面设计案例教程,搜狗收录网站,wordpress下一篇调用,整合营销传播策划方案文章来源于极客时间前google工程师−王争专栏。 如何理解栈
后进者先出#xff0c;先进者后出#xff0c;这就是典型的“栈”结构。
从栈的操作特性来看#xff0c;栈是一种“操作受限”的线性表#xff0c;只允许在一端插入和删除数据。
当某个数据集合只涉及在一端插入… 文章来源于极客时间前google工程师−王争专栏。 如何理解栈
后进者先出先进者后出这就是典型的“栈”结构。
从栈的操作特性来看栈是一种“操作受限”的线性表只允许在一端插入和删除数据。
当某个数据集合只涉及在一端插入和删除数据并且满足后进先出、先进后出的特性我们就应该首选“栈”这种数据结构。
栈既可以用数组来实现也可以用链表来实现。用数组实现的栈我们叫做顺序栈用链表实现的栈我们叫做链式栈。
public class ArrayStack{//内部维护一个数组private String[] items;//栈中元素个数private int count;//栈的大小private int n;//初始化栈public ArrayStack(int n){this.items new String[n];this.n n;this.count 0;}//入栈操作public boolean push(String item){//栈空间不够返回false入栈失败if(count n) return false;items[count] item;count;return true;}//出栈操作public String pop(){if(count 0) return null;//返回下标为count-1的数组元素String tmp items[count-1];--count;return tmp;}
}空间复杂度为O(1)注意大小为n的数组并不是说空间复杂度就是O(n)。时间复杂度为O(1)
支持动态扩容的顺序栈
上述基于数组实现的栈是一个固定大小的栈。链式栈的大小不受限但要存储next指针内存消耗相对较多。
基于数组可以设计动态扩容的顺序栈 复杂度分析
出栈不设计内存的重新申请和数据的搬移出栈时间复杂度依然为O(1)。入栈有空闲空间为O(1)空间不够为O(n) 最好O(1)最坏O(n) 入栈均摊分析需要前提假设
栈空间不够时我们重新申请一个是原来大小两倍的数组。为了简化分析假设只有入栈没有出栈操作。定义不涉及内存搬移的入栈操作为simple-push操作时间复杂度为O(1)。 入栈操作的均摊时间复杂度为O(1)
栈在函数调用中的应用
比较经典的一个应用场景就是函数调用栈 操作系统给每个线程分配了一块独立的内存空间这块内存被组织成“栈”这种结构用来存储函数调用时的临时变量。每进入一个函数就会将临时变量作为一个栈帧入栈当被调用函数执行完成返回之后将这个函数对应的栈帧出栈。 int main(){int a 1;int ret 0;int res 0;ret add(3,5);printf(%d,res);return 0;
}
int add(int x,int y){int sum 0;sum xy;return sum;
}栈在表达式求值中的应用
编译器利用栈来实现表达式求值。 简单表达式比如3413*944-12/3 编译器通过两个栈来实现。 一个保存操作数的栈。一个保存运算符的栈。
遇到数字直接压入操作数栈遇到运算符就与运算符栈的栈顶元素进行比较 如果比栈顶的优先级高就将当前运算符压入栈。如果比栈顶的优先级低或者相同。从运算符栈顶取运算符从操作数栈的栈顶取2个操作数然后进行计算再把计算完的结果压入操作数栈继续比较。
栈在括号匹配中的应用
除了用栈来实现表达式求值我们还可以借助栈来检查表达式中的括号是否匹配。 {[{}]}或[{()}([])]都为合法格式而{[}()]或[({)]为不合法格式。如何检查合法性呢
我们用栈来保存未匹配的左括号从左到右依次扫描字符串。当扫描到左括号时则将其压入栈中当扫描到右括号时从栈顶取出一个左括号。能匹配继续扫描。不能匹配或者栈中没有数据则说明为非法格式。
解答开篇 当访问一串页面a-b-c之后点击浏览器的后退按钮就可以查看b和a。后退到a点击前进可以查看b和c。如果后退到a点击新的页面d就无法查看b和c了。 如何实现浏览器的前进、后退功能用两个栈可以完美解决。
顺序查看abc依次压入栈 通过浏览器后退按钮从页面c后退到页面a之后依次将c和b从栈X弹出入栈Y。 这个时候又想看bb出栈Y入栈X。 这个时候通过页面b又跳转到新的页面d页面c就无法再通过前进、后退按钮重复看了所以需要清空栈Y。
内容小结
栈是一种操作受限的数据结构只支持入栈和出栈操作。后进先出是它最大的特点。栈可以通过数组实现也可以通过链表实现。入栈、出栈时间复杂度都是O(1)。支持动态扩容的顺序栈需要重点掌握均摊时间复杂度方法。
思考
函数调用栈来保存临时变量为什么用“栈”来保存其他数据结构不行吗 其实我们不一定非要用栈来保存临时变量只不过如果这个函数调用符合后进者先出的特性用栈这种数据结构来实现是最顺理成章的选择。 从调用函数进入被调用函数对于数据来说变化的是什么呢是作用域。所以根本上只要能保证每进入一个新的函数都是一个新的作用域就可以。而要实现这个用栈就非常方便。在进入被调用函数的时候分配一段栈空间给这个函数的变量在函数结束的时候将栈顶复位正好回到调用函数的作用域内。 JVM内存管理有个“堆栈”的概念。栈内用来存储局部变量和方法调用堆内用来存储java中的对象。那JVM里面的“栈”跟我们这里说的“栈”是不是一回事呢如果不是那它为什么又叫作“栈”呢 内存中的堆栈是真实存在的物理区数据结构中的堆栈是抽象的数据存储结构。内存空间在逻辑上分为三部分代码区、静态数据区和动态数据区动态数据区又分为栈区和堆区。 代码区存储方法体的二进制代码。高级调度作业调度、中级调度内存调度、低级调度进程调度控制代码区执行代码的切换。 静态数据区存储全局变量、静态变量、常量常量包括final修饰的常量和String常量。系统自动分配和回收。 栈区存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。 堆区new一个对象的引用或地址存储在栈区指向该对象存储在堆区中的真实数据。
