我在Java中使用了两个堆栈实现了一个队列,在这里我遵循以下算法:
排队(x)
将X推到堆栈1
出列()
1)如果两个堆栈都是空的,则错误。
2)如果Stack2为空,而Stack1不为空,则将Stack1到Stack2的所有内容推送。
3)从Stack2弹出元素并将其返回。
现在,这里的问题是第一个deQueue()
操作非常慢(因为它将所有内容传输到stack2
)我们能不能修改一下算法,使deQueue
总是o(1)?还有其他选择吗?
最佳答案
你可以交换这两个堆栈。
出列()
如果两个堆栈都是空的,则错误。
如果stack2为空,则
stack1不为空,请交换两个堆栈。
弹出元素
堆叠2并返回。
使用交换时,操作始终为o(1)
如果您需要一个FIFO队列,请使用两个队列只有在需要后进先出的情况下才使用堆栈。
如果是这样,那么使用一个队列或两个队列没有区别,所以您也可以只使用一个队列如果使用线程,请使用包装队列和线程池的ExecutorService。