Array LinkedList Stacks

Question

我必須使用索引0作爲我的堆棧的TOP，並且在執行此操作時遇到問題。我得到所有null s，但輸出100,200和300是我所得到的唯一數字。我忽略的實現有什麼問題嗎？推送方法應該實現ArrayListStack，在索引0推壓元件，以及應該能夠僅除去所述頂部元件（索引0）

public class NaughtyArrayStack<E> implements Stack<E> 
{ 
    private E[] data = (E[])(new Object[10]); 
    private int size; 
    public boolean isEmpty() 
    { 
     return (size == 0); 
    } 

    public void push(E newData) 
    { 
     if (size == data.length) 
     { 
      E[] newDataArray = (E[])(new Object[size*2]); 
      for (int i = 0; i < size; i++) 
       if(isEmpty()) 
        data[0] = newData; 
       else 
        newDataArray[i+1] = data[i]; 
      data = newDataArray; 
     } 

     data[0] = newData; 
     size++; 
    } 

    public static void main(String[] args) 
    { 
     Stack<Pancake> breakfast = new NaughtyArrayStack<Pancake>(); 
     for (int i = 10; i <= 300; i += 10) 
     { 
      breakfast.push(new Pancake(i)); 
     } 
    } 
} 

Answer 1

既然別人已經給你一個完整的解決方案，這裏是一個精簡版，沒有多餘的代碼（DRY）：

public void push(E newValue) 
{ 
    E[] newData = (this.size < this.data.length ? this.data : (E[])new Object[this.size * 2]); 
    System.arraycopy(this.data, 0, newData, 1, this.size); 
    newData[0] = newValue; 
    this.data = newData; 
    this.size++; 
} 

如果您還添加了這種方法，你可以打印堆棧沒有看到任何尾隨的空值：

@Override 
public String toString() { 
    StringBuilder buf = new StringBuilder().append('['); 
    for (int i = 0; i < this.size; i++) { 
     if (i != 0) buf.append(", "); 
     buf.append(this.data[i]); 
    } 
    return buf.append(']').toString(); 
} 

或者用Java 8中的簡單版本：

@Override 
public String toString() { 
    StringJoiner joiner = new StringJoiner(", ", "[", "]"); 
    for (int i = 0; i < this.size; i++) 
     joiner.add(String.valueOf(this.data[i])); 
    return joiner.toString(); 
} 

Answer 2

的問題是與線

data[0] = newData; 

您應該增加數據數組的索引，但不會這樣做，因此每個數組溢出的最後一個值只剩下了。

Answer 3

您的推送功能是錯誤的。它應該是這樣的。當您推新元素時，您需要將所有現有元素移動1個索引，否則您將最終重寫索引0並增加size。這裏是代碼：

public void push(E newData) { 
    if (size == data.length) { 
     E[] newDataArray = (E[]) (new Object[size * 2]); 
     for (int i = 0; i < size; i++) { 
      newDataArray[i + 1] = data[i]; 
     } 
     newDataArray[0] = newData; // set the top to the new element 
     data = newDataArray; // set data to reference the bigger array 
    } else { 
     // shift all the elements int he array by one so that you can add the new element to the 
     // index 0 
     int i = size - 1; 
     while (i >= 0) { 
      data[i + 1] = data[i]; 
      i--; 
     } 
     data[0] = newData; 
    } 

    size++; 
}