CODEWITHSUNDEEP
javadata-structures
Abdelmonem Mohamed
Abdelmonem Mohamed

Reputation: 3

Double Stack-last elements

I have a homework about making a Double stack, consisting of redStack and blueStack, and have their own operations (e.g redPush, bluePush). But for the pop, it knows the last added element in both stacks, and remove it. My question is how could I make it know the last added elements?

Here's my code: 

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

My code here shows removing the last element depending on the counter for each stack. But how can I know the last added one if they are equal to each other? Thanks.

Upvotes: 0

Views: 289

Answers (1)

David G
David G

Reputation: 96875

If you must use two stacks for this then I would maintain a third stack lastAdded that pushes a label for the last pushed element. If the last pushed element was red, then push 0, otherwise 1.

Then in pop you check lastAdded for last type of element pushed, and pop from the corresponding stack.

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

Besides this I would simply use a single stack for all operations, since per your description of the problem the operations you want seem no different then that of a single stack.

Update: With exactly two stacks you would have to make some modifications to the stack itself. Instead of pushing the value itself, push the value + a counter. When popping, pop the element off the stack that has a greater counter value:

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

Upvotes: 1

Related Questions