如何使用两个栈实现双端队列

Question

双端队列 ("doubled-ended queue") 可以从两端进行入队和出队操作。

如何使用 2 个栈定义双端队列的 ADT 操作？

实现还应考虑性能问题。

- Harshdeep

---

@MitchWheat - 我找不到任何清晰解释这个概念的好链接。如果你找到了一个，能否分享一下？ - Harshdeep

@MitchWheat - 只有使用堆栈实现队列，而没有使用两个堆栈进行出队的实现。 - Harshdeep

@Harshdeep 这是为了作业吗？ - Tyler Crompton

@TylerCrompton - 不是的。我的一个朋友在面试中被问到了这个问题，我们能想到的唯一解决方案已经在Andreas的答案中提到，但从性能角度来看并不好。 - Harshdeep

那是唯一的方法。应该使用链表（最好是单向链表）来实现双端队列。问题可能更多地是试图确定你朋友的解决问题的能力。这实际上也是为什么它被称为头尾链接列表的原因。 - Tyler Crompton

Answer 1

最简单的解决方法是使用一个栈作为队列的头部，另一个栈作为尾部。入队操作只需要向相应的栈推送元素，而出队操作只需要从相应的栈弹出元素即可。

然而，如果你想要从一个空栈中出队，你就需要将另一个栈中的每个元素依次弹出并推回到你想要出队的那个栈中，然后再出队最后一个元素。这种情况下的性能不是很好，所以这种实现方式的整体性能强烈依赖于工作负载。如果你的工作负载是前/后端入队和出队操作数量相当平衡的话，那么这种方法会非常快速。但是，如果你的工作负载包含了大量的交替的头部出队和尾部出队，而队列又很大，那么这显然是一种不好的方法。

希望对你有所帮助。

- Andreas Grapentin

---

这也是我想出来的解决方案，但正如你所指出的那样，性能并不好。是否可以对此实现进行修改以提高性能？ - Harshdeep

@Harshdeep 嗯，正如我所说的，性能强烈依赖于你的工作负载。唯一真正会暴露这种实现弱点的工作负载是在大队列上交替调用frontDequeue和backDequeue。否则，这将是可以接受的。 - Andreas Grapentin

你是指 frontEnqueue 和 backDequeue 吗？ - Harshdeep

@Harshdeep 不需要，前面的入队和后面的出队就可以了，因为元素只需要移动一次到“后面的出队”栈。但是如果你从两端出队，每次从不同的端口出队时都必须将元素从一个栈移动到另一个栈。编辑：假设栈是空的... - Andreas Grapentin

这个答案的关键在于你不必将整个栈倒入另一个栈中，而是应该倒出直到两个栈的大小大致相等。这为双端队列提供了最佳的平摊复杂度。 - Simply Beautiful Art

Answer 2

这是我完成它的方式，真正重要的是你要确保当你从一个栈中弹出并且它变为空时，它开始从另一个栈中弹出（我们必须确保它从栈的末尾弹出），我们可以通过将一个栈的内容排空到另一个栈中来实现这一点，并在那里继续弹出。

public class NewDeque {

这是最初的回答。

Stack<E> frontstack;
Stack<E> endstack;

public NewDeque() {

    frontstack = new Stack<>();
    endstack = new Stack<>();

}

void addFirst(E e) {

    frontstack.push(e);
}

E delFirst() {
    if (frontstack.isEmpty()) {
        while (!endstack.isEmpty()) {
            frontstack.push(endstack.pop());
        }
        return frontstack.pop();
    }
    return frontstack.pop();
}

void addLast(E e) {

    endstack.push(e);
}

E delLast() {
    if (endstack.isEmpty()) {
        while (!frontstack.isEmpty()) {
            endstack.push(frontstack.pop());
        }
        return endstack.pop();
    }
    return endstack.pop();
}

int size() {
    return frontstack.size() + endstack.size();
}

boolean isEmpty() {
    return (size() == 0) ? true : false;
}

E get(int i) {
    if (i < endstack.size()) {
        return endstack.get(endstack.size() - i - 1);
    } else {
        return frontstack.get(i - endstack.size());
    }

}

static void print(NewDeque<Integer> ds) {
    for (int i = 0; i < ds.size(); i++) {
        System.out.print(" " + ds.get(i) + " ");
    }
}

- Pedram

Answer 3

一个有趣的方法是按照以下方式进行

enqueue(q,  x)
  1) Push element x to stack1. This very simple, the problem is dequeue

dequeue(q)
  1) If stacks1 and stack2 are empty then error  "UNDERFLOW"
  2) If stack2 is empty, then 
       while (stack1 is not empty) do
           push all element from satck1 to stack2.
        end while;
  3) Pop the element from stack2 and return it.

- vrbsm

---

这实现了一个队列，而不是双端队列。 - Don Slowik

Answer 4

发现了这个解决方案，适用于ArrayStacks。 我认为，类似的方法可以适用于任何类型的堆栈。 您可以使用Andreas Grapentin的答案，但需要添加一个平衡函数，该函数应该被调用得足够少。 思路是当两个堆栈之间的平衡度过低时，您应该将它们推入一个数组（按队列顺序排序），然后在中间拆分此数组，并将其一半复制回堆栈。

- Daniil Kirichenko