实现思路:
使用两个大小相同的堆栈(命名为s1,s2),来实现堆栈。队列包含一下几个操作:创建、注销、满判断、空判断、入队、出队。
创建:
创建管理结构体,结构体包含队列容量、使用量、包含两个栈指针的数组。使用另外的库函数来创建堆栈。两个栈的大小和队列的容量相同。
注销:
顺序注销两个栈,以及管理结构体。
满判断:
空判断:
根据管理结构体中存储的容量和使用量来判断。
入队:
首先使用前面的函数判断队列是否满,满则出错。将数据压入栈s1,并增加使用量计数。
出队:
首先判断队列是否为空,空则出错。判断s2栈是否为空,空则将s1栈内容出栈,入栈到s2,s1的最后一个元素直接返回给函数调用者,不入栈;s2栈非空,则直接从s2中返回一个元素给函数调用者。返回元素要较少使用量计数。
代码实现见github(https://github.com/zhangst/exercise/tree/master/interview/fifo),这种实现还有一个问题,空间浪费。创建一个容量为16的队列,需要两个容量为16的堆栈才能实现,总空间占用为32了。
没有评论:
发表评论