栈的主要机制可以用数组来实现,但也可以用链表来实现,栈的容量通常很小,是临时数据结构.栈只允许访问一个数据项:即插入的数据项,移除这个数据才能访问倒数第二个插入数据项,一次类推,这种机制在不少编程环境中都很有用,大部分微处理器运用基于栈的体系结构,当调用一个方法时,把他的返回地址和参数压入栈,当方法返回结束那些数据就出栈,栈就像邮政服务一样,许多人工作时收到信后,会随手将它仍在大厅桌子上的信堆上,或者把它投入一个站们的框里,等他们有空闲的时候,就会从上到下处理这些堆积的邮件,他们首先打开堆叠在最上面的信,然后做出相应的处理--付账单,扔掉邮件或者其它什么事情,第一封处理完后,接下来就会处理下一封,此时它正处于信堆的最上面,按照此方法处理下去,直到最后轮到信堆最下面的一封(此时它在信堆的最上面)
另一个模拟栈的例子是在一个普通工作口发生的情景:某人正忙于做一个长期项目(A),但是被同事打断叫去临时帮忙做另一个项目(B),当他们做到B的时候,负责财务的同事要他们去开关于旅行话费的会议C,在开会的过程中,他接到销售人员的紧急电话,花了几分钟解决了一个庞大的商品纠纷(D),挂上电话,处理完事情D接着开会,开完会C,接着做项目B,做完B后,才可以继续去做项目A,优先级的项目被压倒栈底,等待回来处理,这些就是我局的形象化例子关于栈
堆是一种树,由它实现的优先级队列的插入和删除的时间复杂度都是O(logN)尽管删除的时间变慢了一些,但是插入的时间快了很多,当速度非常重要时,而且有很多插入操作时,可以选择堆来实现优先级队列,这里的堆是一种特殊的二叉树,这也就是说除了数的最后一层节点不需要是满的,其它的每一层从左到右全是满的,它常常用一个数组来实现的.堆中的每一个节点都满足堆的条件,也就是说每一个节点的关键字都大于或等于这个节点的关键字
|