顺序栈
利用顺序存储结构实现的栈
顺序栈是栈的顺序实现。顺序栈是指利用顺序存储结构实现的栈。采用地址连续的存储空间(数组)依次存储栈中数据元素,由于入栈和出栈运算都是在栈顶进行,而栈底位置是固定不变的,可以将栈底位置设置在数组空间的起始处;栈顶位置是随入栈和出栈操作而变化的,故需用一个整型变量top来记录当前栈顶元素在数组中的位置。
解释
栈的元素依次存放在一个一维数组中。下标小的一端作为栈底。用一个变量记录栈顶位置,称“栈顶指针”。
应用
进栈是把元素存放在栈顶后面一个位置,栈顶往后移;出栈是删除栈顶元素,栈顶往前移。适合栈元素数量比较确定的情况。
表示和实现
栈的顺序存储结构是利用内存中的一片起始位置确定的连续存储区域来存放栈中的所有元素,另外为了指示栈顶的准确位置,还需要引入一个栈顶指示变量top,采用顺序存储结构的栈称为顺序栈(sequence stack)。设数组data[MAXSIZE]为栈的存储空间,其中MAX-SIZE是一个预先设定的常数,为允许进栈结点的最大可能数目,即栈的容量。初始时栈空,top等于0。当top不等于0时,data[0]为栈底元素,即为当前停留在栈中时间最长的元素;而data[top-1]为最后入栈的元素,即为栈顶元素。当top==MAXSIZE时,表示栈满,如果此时再有结点进栈,将发生称之为“上溢”(语法上表现为“数组越界”)的错误,而当top==0时再执行出栈操作,将发生称之为“下溢”的错误。图3.4给出了栈容量为6时,入栈、出栈操作以及栈空、栈满等几种典型的栈状态。由于顺序存储结构多采用一维数组存放栈,因此必须特别注意“栈上溢”错误的发生;在实现入栈操作时,先判断是否栈满(stack full),如果栈满,及时处理。
参考资料
最新修订时间:2024-01-26 05:00
目录
概述
解释
应用
表示和实现
参考资料