堆栈的操作过程,堆栈溢出

　　我们对栈的数据结构有了初步的了解。堆栈是元素的集合，类似于数组，只是数组可以通过下标随机访问。这次访问a[5]下次可以访问a[1]，但是栈的访问规则仅限于Push和Pop操作。Push (Push或push)将元素添加到堆栈的顶部，而Pop (pop或Pop)则取出当前堆栈顶部的元素，即只能访问顶部的元素，不能访问顶部的元素。如果所有元素都是同一类型，那么栈的存储也可以用数组来实现，访问操作可以通过函数接口来提供。请看下面的示例程序。

　　例12.1。堆叠反转打印

　　#包含stdio.h

　　字符堆栈[512]；

　　int top=0；

　　无效推送(字符c)

　　stack[top]=c；

　　字符弹出(无效)

　　返回堆栈[-top]；

　　int是_empty(void)

　　return top==0；

　　int main(void)

　　push( a )；

　　推( b )；

　　push( c )；

　　而(！is_empty())

　　putchar(pop())；

　　putchar( \ n )；

　　返回0；

　　}

　　Stack是栈的存储空间，变量top总是保存数组中栈顶下一个元素的下标。我们说“top总是指向栈顶的下一个元素”，或者我们称top为指针。它可以用来检查循环的正确性。这里的“top总是指向栈顶的下一个元素”实际上是一个不变量，Push和Pop操作总是保持这个条件不变。这个不变量描述的是一个数据结构而不是循环的对象，在DbC中称为类不变量。Pop操作的语义是取出stack的top元素，但是上面例子的实现实际上并没有清除原来的top元素，只是移动了top指针，原来的top元素还在那里。这就足够了，因为不可能通过Push和Pop操作访问已经取出的元素，下一个Push操作会覆盖它。putchar函数用于将一个字符打印到屏幕上，这与printf的%c函数相同。布尔函数is_empty用于防止弹出操作访问越界。我们在这里保留了足够的堆栈空间(512个元素)。其实严格来说，我们还应该在推送操作之前检查堆栈是否已满。

　　在主函数中，堆栈的顺序是 a ， b ， c ，而打印出堆栈的顺序是 c ， b ， a ，最后一个 c 先出来，所以堆栈的这种数据结构的特点可以概括为LIFO(后进先出)。我们也可以写一个递归函数逆序打印，利用函数调用的堆栈框架实现LIFO:

　　例12.2。递归反向打印

　　#包含stdio.h

　　#定义镜头3

　　char buf[LEN]={a ， b ， c }；

　　void print_backward(int pos)

　　if(pos==LEN)

　　返回；

　　向后打印(位置1)；

　　putchar(buf[pos])；

　　int main(void)

　　print _ backward(0)；

　　putchar( \ n )；

　　返回0；

　　}

　　你可能会说，堆栈和递归，逆序打印一个数组值得吗？只需编写一个简单的循环：

　　for(I=LEN-1；我我-)

　　putchar(buf[I])；

　　对于数组来说真的没必要这么复杂，因为数组可以从前到后，从后到前，甚至随机访问，但是有些数据结构就没那么自由访问了。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。