网站怎么做关键词内链,印刷东莞网站建设技术支持,禁止网站收录,免费发布网站栈到底是什么玩意
cpu中有栈段SS寄存器和栈指针SP寄存器#xff0c;它们是用来指定当前使用的栈的物理地址。换句话说#xff0c;要想让cpu运行#xff0c;必须得有栈。栈是什么?干吗用的#xff1f;本节将给大家一个交待。
还记得数据结构中的栈吗#xff1f;那是逻辑…栈到底是什么玩意
cpu中有栈段SS寄存器和栈指针SP寄存器它们是用来指定当前使用的栈的物理地址。换句话说要想让cpu运行必须得有栈。栈是什么?干吗用的本节将给大家一个交待。
还记得数据结构中的栈吗那是逻辑上的数据存取结构是种如何用这种数据结构来存取数据的描述。在用户进程空间中堆是堆栈是栈但堆栈却是人们常说的栈和堆没关系所以咱们后面为避免混淆只说栈。
栈是线性表的一种什么是线性表如果提出这样的问题我想您可能不清楚什么是线性。线性就是具有线的性质就像一条线一样连续性强从一个方向到另一个方向。线上没有面积的概念不管是直线还是曲线在线上任意位置只能容纳一个数据对象。线性表简而言之就是一个线性存储单元结构中每个元素都有一个前驱和一个后继元素且仅各有一个。这就是线性的体现连续且任意位置只有一个元素。栈也是这样不过不同的是数据的存取都在一端进行这一端称为栈顶另一端做为存储单元的基址永远不动称为栈底。这就是上学时老师们常常说的后进先出先放进去的数据要在最后才能取出后放进去的数据最先被取出。
这里我就不用举汉诺塔这样经典的例子了毕竟上学时都听得太多了。我说个大家都认同的事实大家肯定挤过公交车吧坐过公交车的同学继续看土豪随意^_^尤其是早班车和末班车车厢里人挤人站都站不稳。先挤上车的乘客其实很倒霉的有座儿不算^_^因为他要在最后下车在拥挤的车厢中折磨的时间最长。后挤上车的乘客在下车的时候还是蛮爽的因为他会是第一个下车是率先逃出恶劣环境的人。所以挤公交车就是典型的后进先出。车厢就相当于栈乘客就相当于栈中存取的元素这个例子其实还算生动。
举的例子虽然很常见但这对于已经理解栈的同学来说我像是在说废话一样没新意。对于不理解栈的同学来说可能是依然像说废话一样说了也意会不到栈是什么。我非常理解这种心情记得当初我在学网络时老师说只要在路由器上把三层网络层IP协议不是指令指针寄存器IP禁用四层传输层上的tcp或udp协议自然就不可用了。老师为了让我们明白这种依赖关系甚至不惜举出这样的例子如果不想让某人说话 最简单的办法就是给让其睡着而不是劝他保护安静。这个例子非常浅显易懂但用例子来理解理论知识依然让我有点摸不着头脑这可不是比喻恰不恰当的事知识是严谨的不是比喻出来的。如果您现在也有这样的体会没关系以后会不断接触栈的熟了自然就理解了这只是时间问题。
初次学习数据结构时不容易理解其本质我当初在学习这门课时感觉云里雾里的似乎明白似乎又不懂老师让不懂的同学提问我又不知道该怎样描述问题不知道哪里不懂。同样的定义同样的文字描述每个人理解的都不一样。就像鱼和小鸟鱼认为自己离开水就会死水就是生命小鸟也认为没水会渴死水也是生命。但鱼和小鸟对水的理解能一样吗?赶紧回来还是说咱们的正事。栈只是一种抽象概念是一种虚拟出来的数据存取方法。其实现形式是不限的只要满足栈的定义就可以
λ首先得是线性结构并且数据的存取在线性结构的一端进行。如果您愿意可以用链表来实现也可以用数组来实现它们都是线性数据结构。λ其次需要维护一个指针用它来指向线性结构的一端数据存取都通过此指针。
前面又比喻又回忆的说了这么多栈能够干什么呢栈是一种很伟大的发明可以解决很多难题
λ表达式计算如中缀表达式和后缀表达式的转换λ函数调用无论是嵌套调用或递归调用用来维护返回地址。λ深度优先搜索算法
到现在为止我们说的只是数据结构中的栈这是逻辑上的最终我想表达的是内存中的栈这是物理上的。把数据结构中的栈的概念用物理硬件来实现这就是我们要说的栈。它同数据段、代码段一样是个内存中的区域。也就是栈段寄存器SS和栈指针SP所指向的内存区域。我们常听说的栈溢出指的就是这个内存区域无法容纳数据了。
硬件是如何实现这个栈的呢?还是那句话首先得满足栈的概念具备栈的特性即使是硬件也不能例外必须满足上面提到的这两个条件一个是线性结构一个是在栈顶对数据存取。因为它毕竟造的是栈不具备这些就不叫栈了。
线性结构这个简单内存就是直接用物理内存存取最方便了咱们要做的就是给栈指定一片内存区域就成了区域的起始地址做为栈基址存入栈基址寄存器SS中另一端是动态变化的用栈指针寄存器SP来指定。栈在使用过程中是向下扩展的所以栈顶地址肯定是小于栈底地址。
栈既然是一片内存区域访问内存就要用“段基址段内偏移地址”的形式所以栈中的内存地址也是用“段基址SS的值*16栈指针SP段内偏移地址形成的20位地址”访问到的。由于是硬件实现的栈故硬件提供了相应的方法来存取栈即push和pop指令。push指令负责把数据压入栈pop指令功能相反将其从栈中取出。不过我刚才说的不全面栈的出口和入口都是栈顶push把数据压向哪里它得知道栈顶在哪里才行。pop指令也一样它得知道哪里是栈顶才能从栈中取出正确的数据。这正是栈指针寄存器SP的作用此寄存器中的值是段内偏移地址是栈顶相对于栈底的偏移量。
栈顶SP指针是栈的出口和入口它指向的内存中存储的始终是最新的数据。push和pop就是操作这个指针所指向的内存。由于栈是从高地址向低地址发展所以栈顶、栈指针指向的地址会越来越低。push压入数据的过程是先将SP减去字长目的是避免将栈顶的数据破坏所得的差再存入SP栈顶在此被更新这样栈顶就指向了栈中下一个存储单元的位置。再将数据压入SP新的栈顶指向的新的内存地址。pop指令相反既然是在栈中弹出数据栈指针寄存器SP的值应该是增大一个数据单位。由于要弹出的数据就在当前栈顶所以在弹出数据后才将SP加上字长所得的和再存入SP从而更新了栈顶。这样SP就指向了上一个存储单元的位置。
上面提到的字长是指cpu的字长即一次可处理的数据的长度。在实模式下的字长是16。
物理内存中的栈如图: 注意啦如图所示虽然栈是向下发展但栈也是内存访问内存依然是从低地址往高地址假如当前栈顶是0x1233E栈顶数据占2字节的话其范围是0x1233E~0x1233F。个人觉得这个硬件中的栈让人感到神秘主要有两方面原因
一方面是栈指针不是自己维护这不像咱们在高级语言中自己创建的栈那样指针的一举一动都是自己在操作。不直接受控的东西往往让人心存忧虑和有点小恐慌。其实即使是这里的硬件栈咱们也可以自己维护指针如push ax可以这样代替
mov bp,sp
sub bp, 2
mov [bp],axbp默认的段寄存器就是SS用bp的时候直接操作的便是栈。bp就相当于栈指针啦自己维护毕竟太麻烦有直接省事的干吗不用呢^_^。
另一方面栈就是一片内存区域只不过“经常”操作这片内存的指令不是mov而是push、pop这两条指令无非是自动维护存取数据的位置SP寄存器的值而已大家用mov来操作这片内存不是也得要给出存取地址吗。这样看来它和普通的数据段没什么不同不要觉得它比金字塔还神秘啦。
一定要注意push和pop操作是要成对出现的这样才能维护栈平衡。否则光push不pop有进没出这栈很快就溢出啦。切记一个push要对应一个pop每键入一个pop指令一定要清楚它对应的是哪个push。
栈就先说这么多不摸索实际东西的话还是不能真正掌握和理解本书强调实践纸上谈兵可来不了真知识。
好啦官人常来玩哦
