2013年1月10日星期四

堆栈实现先进先出队列

实现思路:
        使用两个大小相同的堆栈(命名为s1,s2),来实现堆栈。队列包含一下几个操作:创建、注销、满判断、空判断、入队、出队。

创建:
       创建管理结构体,结构体包含队列容量、使用量、包含两个栈指针的数组。使用另外的库函数来创建堆栈。两个栈的大小和队列的容量相同。

注销:
       顺序注销两个栈,以及管理结构体。

满判断:
空判断:
       根据管理结构体中存储的容量和使用量来判断。

入队:
        首先使用前面的函数判断队列是否满,满则出错。将数据压入栈s1,并增加使用量计数。

出队:
        首先判断队列是否为空,空则出错。判断s2栈是否为空,空则将s1栈内容出栈,入栈到s2,s1的最后一个元素直接返回给函数调用者,不入栈;s2栈非空,则直接从s2中返回一个元素给函数调用者。返回元素要较少使用量计数。


代码实现见github(https://github.com/zhangst/exercise/tree/master/interview/fifo),这种实现还有一个问题,空间浪费。创建一个容量为16的队列,需要两个容量为16的堆栈才能实现,总空间占用为32了。


没有评论:

发表评论