Reputation: 3
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
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