您现在的位置:小学生自学网>> 信息>> 学习电脑

3栈

作者: 来源: 发布时间:2009年01月14日 点击数:
 
1.栈的特点:
   栈是一种线性表,对于它所有的插入和删除都限制在表的同一端进行,这一端叫做栈的“顶”,另一端则叫做栈的“底”,其操作特点是“后进先出”。
  2.栈的一般定义:
   type
    stack=record
        data:array[1..m] of datatype;
        t:0..m
    end;
   var
    s:stack;
  3.栈的基本运算:
   (1)栈的插入push(s,x):往栈st中推入一个值为x的项目;
     若t=m则print('overflow')
     否则t:=t+1;data[t]:=x;
   (2)栈的弹出pop(s):从栈st中弹出一个项目;
     若t=0则print('underflow')
     否则t:=t-1;
   (3)读栈顶元素top(s,x):把栈顶元素的值读到变量x中,栈保持不变;
     若t=0则print('error')
     否则x:=data[t];
   (4)判栈是否为空sempty(s):这是一个布尔函数,当栈st中没有元素(即t=0)时,称它为空栈,函数取真值,否则值为假。
     若t=0则sempty:=true
     否则sempty:=false;
  4.栈的应用之一——计算表达式的值
   (1)表达式的三种形式:
     中缀表达式:运算符放在两个运算对象中间,如:(2+1)*3;
     后缀表达式:不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则,如:2 1 + 3 *;
     前缀表达式:同后缀表达式一样,不包含括号,运算符放在两个运算对象的前面,如:* + 2 1 3。
   (2)表达式的计算
   由于后缀表达式中没有括号,不需判别优先级,计算严格从左向右进行,故计算一个后缀表达式要比计算机一个中缀表达式简单得多。

  将中缀表达式转换为后缀表达式的算法思想:
   ·当读到数字直接送至输出队列中
   ·当读到运算符t时,
      a.将栈中所有优先级高于或等于t的运算符弹出,送到输出队列中;
      b.t进栈
   ·读到左括号时总是将它压入栈中
   ·读到右括号时,将靠近栈顶的第一个左括号上面的运算符全部依次弹出,送至输出队列后,再丢弃左括号。

   运用后缀表达式进行计算的具体做法:
   ·建立一个栈S
   ·从左到右读后缀表达式,读到数字就将它转换为数值压入栈S中,读到运算符则从栈中依次弹出两个数分别到Y和X,然后以“X 运算符 Y”的形式计算机出结果,再压加栈S中
   ·如果后缀表达式未读完,就重复上面过程,最后输出栈顶的数值则为结束
   示范程序

 5.栈的应用之二——递归算法的非递归实现
   示例:

上一篇:2串

下一篇:4链表