• 内容讲解

计算机中的堆栈(Stack)是一组能存储和取出数据的暂时存储单元,所有信息的存入和取出均按照后进先出(LIFO)或先进后出(FILO)的原则进行。

堆栈存取方式决定了其“一端存取”的特点,数据按顺序存入堆栈称为进栈或压栈(Push),堆栈中一个单元的数据称为栈项,栈项按与进栈相反的顺序从堆栈中取出称为出栈或弹出(Pop),最后进栈的数据或最先出栈的数据称为栈顶元素。

1.寄存器堆栈

寄存器堆栈又称串联堆栈、硬堆栈。某些计算机在CPU中设置了一组专门用于堆栈的寄存器,每个寄存器可保存一个字的数据。因为这些寄存器直接设置于CPU中,所以它们是极好的暂存单元。CPU通过进栈指令(PUSH)把数据存入堆栈,通过出栈指令(POP)把数据从堆栈中取出。

寄存器堆栈如图4-14所示:⑴空栈表示栈顶无数据,即位于栈顶的寄存器中无可用的数据;⑵存入数据a,即把数据a存入栈顶,数据a可以来自主存、程序计数器PC等部件;⑶再存入数据b,数据b位于栈顶,先进入的数据a则移至下一个寄存器;⑷执行出栈操作,位于栈顶的数据b被取出,与此同时数据a移至栈顶。

418.gif

从寄存器堆栈的数据进栈操作结果可见,最后进栈的数据位于栈顶,位于栈顶的数据出栈时最先被取出。在寄存器堆栈中,还必须有“栈空”和“栈满”的指示,以防在栈空时企图执行出栈、在栈满时企图执行进栈的误操作。这可以通过另外设置一个计数器来实现:每次进栈,计数器加1,计数值等于堆栈中寄存器个数时表示栈满;每次出栈,计数器减1,该计数值等于0时表示栈空。

寄存器堆栈的特点是仅有一个出入口,后进先出,且堆栈的容量固定,不需要占用主存。

2.存储器堆栈

当前计算机普遍采用的一种堆栈结构是存储器堆栈,也就是从主存中划出一块区域来作堆栈,又称软堆栈。这种堆栈的大小可变,栈底固定,栈顶浮动。由于主存的容量越来越大,存储器堆栈能够满足程序员对堆栈容量的要求,而且在需要时可建立多个存储器堆栈。

这种堆栈有三个主要优点:

(1) 堆栈能够具有程序员要求的任意长度;

 (2)只要程序员喜欢,愿意建立多少堆栈,就能建立多少堆栈;

(3)可以用对存储器寻址的任何一条指令来对堆栈中的数据进行寻址。

构成存储器堆栈的硬件有两部分,一是在主存中开辟用于堆栈的存储区,二是在CPU中设置一个专用的寄存器——堆栈指针SP(Stack Pointer)来保存栈顶地址。除了硬件之外,还必须有实现进栈、出栈操作的指令。

作为堆栈的存储区,其两端的存储单元有高、低地址之分,因此,存储器堆栈又可分为两种:从高地址开始生成堆栈和从低地址开始生成堆栈。

1)从高地址开始生成堆栈(自底向上生成堆栈)

从高地址开始生成堆栈是一种较常用的方式,这种堆栈的栈底地址大于栈顶地址,在建栈时,SP指向堆栈中地址最大的单元(栈底),每次进栈时,首先把要进栈的数据存入SP所指向的存储单元,然后把指针SP-1;出栈时,先把指针SP+1,然后从SP所指向的存储单元取出数据,如图4-15所示:

419.gif

进栈操作:首先数据→Msp,然后指针(SP)-1→SP,Msp表示SP所指定的存储单元;

出栈操作:首先(SP)+1→SP,然后(Msp)读出,(Msp)表示SP所指定的存储单元的内容。

2)从低地址开始生成堆栈(自顶向下生成堆栈)

这种堆栈与从高地址开始生成堆栈正好相反,它的栈底地址小于栈顶地址,建栈时SP指向堆栈中地址最小的单元(栈底)。具体操作如下:

进栈操作:首先数据→Msp,然后指针(SP)+1→SP;

出栈操作:首先(SP)-1→SP,然后(Msp)读出。

存储器堆栈的操作方式与寄存器堆栈不同,它移动的是栈顶,而在寄存器堆栈中移动的是数据。

堆栈中对数据的操作具有后进先出的特点,因此,凡是以后进先出方式进行的信息传送都可以用堆栈很方便地实现。例如,在子程序的调用中,用堆栈存放主程序的返回地址,实现子程序的嵌套和递归调用;在程序中断处理中,用堆栈存放多级中断的相关信息,实现多级中断的嵌套。