Lin Ma Lin Ma - 28 days ago 11
Java Question

issues when managing multiple stacks

Investigating a solution to manage multiple stacks, posted the problem and code I am debugging. The question is, why function popAt(int index) shift from bottom of next sub-stack? Does it because of the next element (in the order of stack push) of top of sub-stack 1, is bottom element of sub-stack 2? I am not sure if this behavior is correct, and whether the expected behavior is, after pop element of stack 1, the next element to pop is the element in stack 1 which is under previous top, other than bottom of next stack?

Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. A data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack), and function popAt(int index) which performs a pop operation on a specific sub-stack.

public class SetOfStacks {
ArrayList<Stack> stacks = new ArrayList<>();
public int capacity;
public SetOfStacks(int capacity) {
this.capacity = capacity;
}
public Stack getLastStack() {
if (stacks.size() == 0) return null;
return stacks.get(stacks.size() - 1);
}
public void push(int v) { /* see earlier code */
}
public int pop() {
Stack last = getLastStack();
System.out.println(stacks.size());
int v = last.pop();
if (last.size == 0) stacks.remove(stacks.size() - 1);
return v;
}
public int popAt(int index) {
return leftShift(index, true);
}
public int leftShift(int index, boolean removeTop) {
Stack stack = stacks.get(index);
int removed_item;
if (removeTop) removed_item = stack.pop();
else removed_item = stack.removeBottom();
if (stack.isEmpty()) {
stacks.remove(index);
} else if (stacks.size() > index + 1) {
int v = leftShift(index + 1, false);
stack.push(v);
}
return removed_item;
}
}
public class Stack {
private int capacity;
public Node top, bottom;
public int size = 0;
public Stack(int capacity) {
this.capacity = capacity;
}
public boolean isAtCapacity() {
return capacity == size;
}
public void join(Node above, Node below) {
if (below != null) below.above = above;
if (above != null) above.below = below;
}
public boolean push(int v) {
if (size >= capacity) return false;
size++;
Node n = new Node(v);
if (size == 1) bottom = n;
join(n, top);
top = n;
return true;
}
public int pop() {
Node t = top;
top = top.below;
size--;
return t.value;
}
public boolean isEmpty() {
return size == 0;
}
public int removeBottom() {
Node b = bottom;
bottom = bottom.above;
if (bottom != null) bottom.below = null;
size--;
return b.value;
}
}


thanks in advance,
Lin

Answer Source

leftShift() in your code may be called recursively with increasing index, that's why if you call it with index of 1 it may pop from stack #2 then (and, in a case when all stacks were 1 element in size, it will continue with stack #3, #4 and so on :( )