问题

假设我们有两个堆栈,没有其他临时变量.

是否可以只使用两个堆栈“构造”队列数据结构?

  最佳答案

保留2个堆栈,我们称之为inboxoutbox

问询:

  • 将新元素推送到inbox

排队:

  • 如果outbox为空,通过从inbox弹出每个元素并将其推送到outbox

  • postgresql – 弹出并从outbox返回顶部元素

使用此方法,每个元素将完全在每个堆栈中一次 – 意味着每个元素将被两次推动并弹出两次,给出摊销的常量时间操作.

这是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();
    }

}
 

  相同标签的其他问题

algorithmdata-structuresstackqueue