如何使用两个堆栈实现出列

Question

Dequeue - 双重队列：从两端进行队列排队和排队。

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

实施还应考虑到绩效。

Answer 1

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

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

希望这可以帮助

Answer 2

一个有趣的方法是这样做

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.

Answer 3

这就是我做的方式，真正重要的是你确保当你继续弹出一个它变空而它开始从另一个弹出时（我们必须确保它从栈尾弹出）我们可以通过将一个堆栈清空到另一个堆栈中来实现。并继续弹出那里。

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