C＃方法indexOfTop（int stackNum）如何確定堆棧的頂部？

「indexOfTop（int stackNum）」方法如何準確計算給定堆棧號的頂部？C＃方法indexOfTop（int stackNum）如何確定堆棧的頂部？

來源：破解編碼訪談189編程問題&解決方案：第3章|堆棧和隊列：3.1 - 描述如何使用單個數組來實現三個堆棧。

class FixedMultiStack 
{ 
    private int numberOfStacks = 3; 
    private int stackCapacity; 
    private int[] values; 
    private int[] sizes; 

    public FixedMultiStack(int stackSize) 
    { 
     stackCapacity = stackSize; 
     values = new int[stackSize * numberOfStacks]; 
     sizes = new int[numberOfStacks]; 
    } 
    public void push(int stackNum, int value) 
    { 
     if (isFull(stackNum)) throw new Exception("Full stack, cannot push."); 
     /* Increment stack pionter and then update top value. */ 
     sizes[stackNum]++; 
     values[indexOfTop(stackNum)] = value; 
    } 
    public int pop(int stackNum) 
    { 
     if (isEmpty(stackNum)) throw new Exception("Empty Stack, nothing to pop."); 
     int topIndex = indexOfTop(stackNum); 
     int value = values[topIndex]; //Get Top. 
     values[topIndex] = 0;   //Clear 
     sizes[stackNum]--;    //Shrink 
     return value; 

    } 
    /* Return top element. */ 
    public int peek(int stackNum) 
    { 
     if (isEmpty(stackNum)) throw new Exception("Empty Stack, nothing to peek at."); 
     return values[indexOfTop(stackNum)]; 
    } 
    public bool isFull(int stackNum) 
    { 
     return sizes[stackNum] == stackCapacity; 
    } 
    public bool isEmpty(int stackNum) 
    { 
     return sizes[stackNum] == 0; 
    } 
    /* Returns index of the top of the stack. */ 
    private int indexOfTop(int stackNum) 
    { 
     int offset = stackNum * stackCapacity; 
     int size = sizes[stackNum]; 
     return offset + size - 1; 
    }* 
}

來源

2017-06-18 Jon

它維護一個int []大小數組，用於跟蹤堆棧的大小。 –

在代碼片段的頂部，我們讀到：

private int[] sizes;

這是一個數組， - 每個三個堆塊的 - 跟蹤該堆棧元素的量的。如果我們推動某個堆棧，則會增加sizes[stackNum]。

現在堆的佈局是：

+-+-+-+-+-+-+-+-+-+-+-+-+ 
|A|A|a|a|B|b|b|b|C|C|C|c| 
+-+-+-+-+-+-+-+-+-+-+-+-+

與a用於第一堆棧保留的地方，保留用於第二堆疊b的地點，並c第三一個保留的地點。我們知道堆棧stackNum開始於stackNum * stackCapacity（請注意，stackNum開始於第一個堆棧的0）。所以通過增加佔用的位置數量，我們獲得堆棧頂部的索引。

在本例中，我用大寫字母A/B/C來表示佔用的地方。所以這裏sizes將是{2,1,3}。如果我們查詢堆棧頂部b，我們問indexOfTop(1)。現在，由於每個堆棧（在我們的示例中）都使用四個空格，因此我們的偏移量位於4*1 == 4。由於堆棧中有一個元素，所以偏移量爲4*1+1-1，因此4。

請注意，如果在堆棧上沒有元素，則索引實際上會引用前一個堆棧（或第一個元素爲-1）。所以一個好的代碼片段應該會出錯。

來源

2017-06-18 23:43:37

謝謝！你的解釋很容易理解和遵循。 – Jon

@Jon：不客氣:) –

該實現將所有N個堆棧預先分配給容量。因此，每個堆棧在大陣列中都有固定的偏移量。

初始元素的偏移量計算爲堆棧數量（從零開始）乘以固定堆棧容量。現在您只需要查找頂層元素的索引就可以將堆棧中存儲的元素的數量添加到初始元素的偏移量。

來源

2017-06-18 23:58:22 dasblinkenlight

C＃方法indexOfTop（int stackNum）如何確定堆棧的頂部？

回答

相關問題