如何使用两个堆栈来实现出队 [英] How to implement a dequeue using two stacks

问题描述

如何使用2个堆栈定义出库队列的ADT操作。

>

实现也应该考虑到性能。

解决方案

最简单的解决方案要使用一个堆栈作为队列的头，一个作为尾部。
入队操作只是推送到相应的堆栈，出队操作只是在相应的堆栈上弹出。

但是，如果您要从中排队的堆栈为空，您必须从其他堆栈中弹出每个元素，并将其推回到要从中排队的堆栈，然后将最后一个排队。这不是很好的性能，所以这个实现的整体性能很大程度上取决于工作量。如果您的工作负载是平衡数量的前/后排队和出队操作，那么这将真的很快。但是如果你的工作量很大，那么队列很大的时候会有很多交替的出发队列和尾随队列，那么这显然是一个坏的方法。

希望这有助于

Dequeue - Doubly ended queue: en-queue and de-queue possible from both ends.

How to define ADT operations for dequeue using 2 stacks.

Implementation should also take into consideration the performance.

解决方案

the simplest solution would be to use one stack as the head of the queue, and one as the tail. The enqueue operations would just be a push to the respective stack, and the dequeue operations would just be a pop on the respective stack.

However, if the stack you want to dequeue from is empty, you'd have to pop each element from the other stack and push it back to the stack you want to dequeue from, and then dequeue the last one. That's not really good performance, so the overall performance of this implementation strongly depends on the workload. If your workload is a balanced number of front/back enqueue and dequeue operations, then this will be really really fast. But if your workload consists of a lot of alternating head-dequeues and tail-dequeues while the queue is large, then this will obviously be a bad approach.

Hope this helps

这篇关于如何使用两个堆栈来实现出队的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！