堆栈duizhan
只能在某一端插入和删除的特殊线性表.堆栈是为存储数据用的.它的存储原理类似子弹夹,子弹只能由夹的顶部压入或者弹出,先压入夹的子弹比后压入的离顶部远.因此进出子弹夹的子弹要遵循“后进先出”的原则.堆栈有两端,固定不动的一端称为栈底,浮动的一端称为栈顶.和子弹进出弹夹类似,数据元素都需从栈顶进栈或出栈,分别叫做压入、弹出.堆栈中的元素也遵循“后出先出”的原则.
在BASIC语言中可用数组来表示堆栈,堆栈的深度在定义数组时由DIM语句规定,要求压入堆栈中的数据元素个数不能超过数组的上界.由于压入或弹出操作都要在栈顶进行,因此,要设一个栈顶指针,以表示该从哪里进行操作.令变量P为栈顶指针,P=0表示空栈.当有数据要入栈时,先让指针加1,然后用赋值语句给以P为下标的数组元素赋值.即
P=P+1
STACK (P)=A
其中STACK为作为堆栈的数组名,A为入栈数据.当有元素要从P所指向的栈顶出栈时,先用赋值语句将P下标数组元素的值赋给某一变量(比如B),之后再让P减1,表示指针仍指向栈顶.即
B=STACK (P)
P=P-1.
堆栈操作作为“后到先办”的抽象,应用十分广泛.比如,程序设计语言编译中的表达式求值要用堆栈;在程序设计语言中实现递归过程要用堆栈;在各种高级语言中的子程序嵌套等都要用堆栈.