如何使用两个堆栈实现一个队列? [英] How to implement a queue using two stacks?
本文介绍了如何使用两个堆栈实现一个队列?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
假设我们有两个堆栈并且没有其他临时变量.
Suppose we have two stacks and no other temporary variable.
是否可以仅使用两个堆栈构造"队列数据结构?
Is to possible to "construct" a queue data structure using only the two stacks?
推荐答案
保留 2 个堆栈,我们称它们为 inbox
和 outbox
.
Keep 2 stacks, let's call them inbox
and outbox
.
入队:
- 将新元素推送到
inbox
出队:
如果
outbox
为空,则从inbox
弹出每个元素并将其推送到outbox
If
outbox
is empty, refill it by popping each element frominbox
and pushing it ontooutbox
从 outbox
使用此方法,每个元素将在每个堆栈中恰好出现一次 - 这意味着每个元素将被推送两次并弹出两次,从而提供摊销的常数时间操作.
Using this method, each element will be in each stack exactly once - meaning each element will be pushed twice and popped twice, giving amortized constant time operations.
这是一个 Java 实现:
Here's an implementation in Java:
public class Queue<E>
{
private Stack<E> inbox = new Stack<E>();
private Stack<E> outbox = new Stack<E>();
public void queue(E item) {
inbox.push(item);
}
public E dequeue() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
return outbox.pop();
}
}
这篇关于如何使用两个堆栈实现一个队列?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文