管理多個堆棧時的問題

Question

調查一個解決方案來管理多個堆棧，發佈了我正在調試的問題和代碼。問題是，爲什麼函數popAt（int index）從下一個子堆棧的底部轉移？是否因爲子堆棧1的頂部的下一個元素（按堆棧推進的順序）是子堆棧2的底部元素？我不確定這種行爲是否正確，以及預期的行爲是否在堆棧1的pop元素之後，pop的下一個元素是堆棧1中位於上一個頂層之下的元素，而不是下一個堆棧的底部？

想象一下（文字）堆疊的盤子。如果堆疊太高，它可能會傾倒。因此，在現實生活中，當前一個堆棧超過某個閾值時，我們可能會啓動一個新的堆棧。一個模擬這個的數據結構SetOfStacks。 SetOfStacks應該由多個堆棧組成，並且應該在前一個堆棧超過容量時創建一個新的堆棧。 SetOfStacks.push（）和SetOfStacks.pop（）的行爲應該與單個堆棧相同（也就是說，pop（）應該返回與只有單個堆棧時相同的值），而函數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--; 
} 

}