管理多个堆栈时的问题

Question

研究管理多个堆栈的解决方案，发布问题和我正在调试的代码。问题是，为什么函数 popAt(int index) 从下一个子堆栈的底部移动？是否因为子栈 1 顶部的下一个元素（按入栈顺序）是子栈 2 的底部元素？我不确定这种行为是否正确，以及预期的行为是否是，在弹出堆栈 1 的元素之后，要弹出的下一个元素是堆栈 1 中位于前一个顶部下方的元素，而不是下一个堆栈的底部？

想象一下（字面上的）一堆盘子。如果堆叠太高，它可能会倒塌。因此，在现实生活中，当前一个堆栈超过某个阈值时，我们可能会开始一个新堆栈。模仿这个的数据结构 SetOfStacks。 SetOfStacks 应该由多个堆栈组成，并且应该在前一个堆栈超过容量时创建一个新堆栈。 SetOfStacks.push() 和 SetOfStacks.pop() 应该与单个堆栈的行为相同（也就是说，pop() 应该 return 与只有一个堆栈时的值相同），和函数 popAt(int index) 对特定子堆栈执行弹出操作。

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

提前致谢，林

Answer 1

leftShift() 在您的代码中可能会随着索引的增加而递归调用，这就是为什么如果您使用索引 1 调用它，它可能会从堆栈 #2 弹出然后（并且，如果所有堆栈的大小都是 1 个元素，它将继续堆栈 #3、#4 等等 :( )

Answer 2

这是我在 java.

中使用 linkedList 对一堆盘子的简单解决方案

class Stack<T>{
Node top;
NodeTop nodeTop;
int count = 1;
int i = 3;
static class Node<T>{
    private T data;
    private Node next;
    Node(T data){
        this.data = data;
        next = null;
    }
}

static class NodeTop<T>{
    private Node<T> top;
    private NodeTop<T> next;
    NodeTop(Node top){
        this.top = top;
    }
}
public void push(T data){
        if(count > i){
            System.out.println("Starting new row of plates");
            NodeTop temp = new NodeTop(top);
            temp.next = nodeTop;
            nodeTop = temp;
            top = null;
            i = i + 3;
        }
        Node temp = new Node(data);
        temp.next = top;
        top = temp;
        count++;
        System.out.println(data);
}

public void pop(){
    if(top == null){
        System.out.println("Current row does not contains any plates, moving to next row");
        if(nodeTop == null){
            System.out.println("No Plates left");
            return;
        }
        top = nodeTop.top;
        nodeTop = nodeTop.next;
        i = i - 3;
    }
    System.out.println(top.data);
    top = top.next;
    count--;
}

}

管理多个堆栈时的问题

issues when managing multiple stacks

java

algorithm

stack