Lin Ma - 28 days ago 11

Java Question

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 :( )