Tauruser

Enjoy Every Day
posts - 34, comments - 95, trackbacks - 0, articles - 5
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

线性结构之典型——堆栈



  正如前面所说,同样的逻辑结构,在上面赋予的操作不同,就是不同的数据结构。一个数据结构要同时包含这两方面的内容。
  作为线性结构的典型——堆栈,堆栈首先就是一个线性结构,但是对这个线性结构上进行的操作进行一定的限制,就成为了堆栈。堆栈只能在表的一端进行插入和删除。摘下《The Art of Computer Progrmming》上对典型的三种线性结构的操作描述。

A stack is a linear list for which all insertions and deletions (and usually all accesses) are made at one end of the list.(堆栈)
A queue is a linear list for which all insertions are made at one end of the list; all deletions (and usually all accesses) are made at the other end.(队列)
A deque ("double-ended queue") is a linear list for which all insertions and deletions (and usually all accesses) are made at the ends of the list.(这种在中文教材里没看到,我暂且叫它为两头蛇 ^ ^)

  堆栈的存储结构实现和前面说的一样,可以用数组方式,目录表,或链表方式实现。具体的实现和操作的实现同样会在实验中提到,这里就不再重复。

  再谈一下,堆栈在实现应用当中的使用。
  实例,对子程序的调用及返回的处理。调用子程序时,将其断点依次压入堆栈,返回时再依次弹出。如递归的调用。
  另外一个实例就是实现“+-×÷”四功能的计算器程序。

这里就先介绍两个基本概念,以后再另行补上实现程序。

中缀表达式:运算符放在两个运算对象之间,称为中缀表达式。计算时先算括号内,再算括号外,多层括号从内层向外层算。无括号或同层括号内由左向右顺序执行。
后缀表达式:不再引入括号,运算符放在两个操作对象后面,称为后缀表达式。计算时所有运算按运算符出现的顺序,严格从左向右,每个运算符取其前面两个操作数,运算后的结果仍为下次的操作数,这样做与中缀表达式计算严格等价,即计算次序和结果完全相同。下面罗列几个等价的中缀表达式和后缀表达式:
中缀表达式,后缀表达式
A                     A
A+B    AB+
A+B*C           ABC*+
A*(B-C)+D    ABC-*D+
D+A/(B-C)     DABC-/+

That's all for today. THX.    


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理