java - 双栈最后元素

Question

我有一个关于制作双堆栈的作业，由 redStack 和 blueStack 组成，并且有自己的操作(例如 redPush、bluePush)。但对于 pop 来说，它知道两个堆栈中最后添加的元素，并将其删除。我的问题是如何让它知道最后添加的元素？

这是我的代码:

public T pop() {
  if (redCounter > blueCounter) {
    redCounter--;
    return redStack.pop();
  }
  if (blueCounter > redCounter) {
    blueCounter--;
    return blueStack.pop();
  } 
}

我的代码显示根据每个堆栈的计数器删除最后一个元素。但如果它们彼此相等，我如何知道最后添加的一个呢？谢谢。

Answer 1

如果您必须为此使用两个堆栈，那么我将维护第三个堆栈lastAdded，它为最后推送的元素推送标签。如果最后推送的元素是红色，则推送0，否则推送1。

然后在 pop 中检查 lastAdded 是否有最后推送的元素类型，并从相应的堆栈中弹出。

public T pop() {
  if (lastAdded.empty()) {
    throw Exception();
  }
  int lastColor = lastAdded.pop();
  if (lastColor == 0) {
    return redStack.pop();
  }
  return blueStack.pop();
}

除此之外，我将简单地使用单个堆栈来执行所有操作，因为根据您对问题的描述，您想要的操作似乎与单个堆栈的操作没有什么不同。

<小时/>

更新:如果有两个堆栈，您将必须对堆栈本身进行一些修改。不要推送值本身，而是推送值 + 计数器。出栈时，将计数器值较大的元素从栈中弹出:

class DoubleStack {
  // Java 7 has its own pair class
  private class Pair<T, U> {
    private T first;
    private U second;
    public Pair(T x, U y) { first = x; second = y; }
    public T getKey() { return first; }
    public U getValue() { return second; }
  }

  private Stack<Pair<Integer, Integer>> redStack = new Stack<>(), blueStack = new Stack<>();
  private int c = 0;

  public boolean empty() {
      return redStack.empty() && blueStack.empty();
  }

  public void pushRed(int x) {
      redStack.push(new Pair<>(x, c++));
  }

  public void pushBlue(int x) {
    blueStack.push(new Pair<>(x, c++));
  }

  public int pop() {
    if (empty()) {
      return Integer.MAX_VALUE; // throw an exception
    } 
    if (redStack.empty()) {
      return popBlue();
    }
    if (blueStack.empty()) {
      return popRed();
    }
    if (redStack.peek().getValue() > blueStack.peek().getValue()) {
      return popRed();
    }
    return popBlue();
  }

  private int popRed() {
    return redStack.pop().getKey();
  }

  private int popBlue() {
    return blueStack.pop().getKey();
  }
};