data-structures - 如何使用两个堆栈实现出队

Question

Dequeue - 双端队列：可以从两端入队和出队。

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

实施还应考虑性能。

Answer 1

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

但是，如果要从中出列的堆栈为空，则必须从另一个堆栈中弹出每个元素并将其推回要从中出列的堆栈，然后将最后一个出列。这并不是很好的性能，所以这个实现的整体性能很大程度上取决于工作负载。如果您的工作负载是前/后入队和出队操作的数量平衡，那么这将非常非常快。但是，如果您的工作负载包含大量交替的头出列和尾出列，而队列很大，那么这显然是一个不好的方法。

希望这可以帮助

Answer 2

我就是这样做的，真正重要的是你确保当你不断从一个弹出并且它变空然后它开始从另一个弹出，（我们必须确保它从堆栈的末尾弹出）我们可以通过将一个堆栈清空到另一个堆栈来做到这一点。并继续在那里流行。

公共类 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) + " ");
    }
}

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.