社区公告:
      论坛首页 → 计算机类 → 软件水平 → 典型数据结构—栈和队列
帖子主题:典型数据结构—栈和队列
楼主

数组和记录在很多程序设计语言中都作为固有数据类型。通过使用指针数据类型和动态存储分配,很多程序设计语言也提供构造链接结构的设施。数组、记录和链接结构提供了实现所谓更高一级抽象的基本构件。本文将要讨论的两种更高一级抽象数据类型,栈和队列,对计算至关重要。

    栈是这样一种数据类型,其主要属性是由支配其元素的插入与删除的规则来决定的,被删除或移去的元素只能是最后插入的,即所谓具有后进先出(LIFO)性质或规范。

    数据类型栈的简单性使人对其重要性产生误解。许多计算机系统把栈做成其电路,并有操作这种硬件栈的机器指令。子例程的调用和返回序列都服从栈协议。算术表达式的求值都是通过对栈的操作序列来实现的。很多手持计算器都是用栈方式来操作的。在学习计算机科学时,将能看到许多栈的例子。

    队列在日常生活中经常出现并且为我们所熟悉。在银行等待服务或在电影院门口等待买票的一队人,在红灯前等待通行的一长串汽车,都是队列的例子。队列的主要特征是遵循先来先服务(First Come,first served)的原则。与栈后进先出的特征不同,在队列中,最先插入的元素将最先除去或接受服务,这样的原则与社会生活中人们公正与平等的意识是一致的。

    队列的先进先出(FIFO)原则在计算机中有很多应用。例如,在多用户分时操作系统中,等待访问磁盘驱动器的多个输入输出(I/O)请求就可能是一个队列。等待在计算机中运行的作业也形成一个队列,计算机将按照作业和I/O请求到达的先后次序进行服务,也就是按先进先出的次序服务。

    另外,还存在着一种重要的队列:在医院的急救室内每天都可以看到的例子。在危重病人多的情况下,医生必须首先抢救生命垂危的病人。在某些不太强调平等性的社会中社会地位高的人可以最先得到治疗。

    在计算机系统中,要求计算机系统服务的事件通常是最重要的事件最先服务,换句话说,按最高优先级先进先出队列(HPIFO)的原则。这种队列称之为优先级队列。优先级队列并不按进入队列的时间的先后决定服务的次序,而是按照优先级确定的次序。



发表时间:2007-7-5 11:16:00
回到顶部    第 2 楼

分清队列是先进先出,栈是后进先出的原理。


发表时间:2007-7-5 11:21:00
第 1 页