數組仿真鏈表的優化

在上面的程序中，每次加入一個新值都要在數組當中尋找一個空位來儲存數據，這樣做會有一個問題，就是當鏈表中加入了n個元素時，每一次都會用線性的時間復雜度去尋找空位，造成了很大的時間上的浪費，因此需要進行優化（本節內容涉及堆棧的應用，請在學完本書第二章的內容后再研究本節內容）。

用一個堆棧記錄所有沒有被加入到鏈表中的數組元素下標，棧的元素可以初始化為1…MAXN-1，以方便使用。每次對鏈表進行刪除操作時，再將刪除的數組元素所對應的數組下標入棧，下次再添加新元素進鏈表時，只需取出棧頂的數組下標即可，因為這個下標對應的數組元素顯然是空的。

這個優化方法將O（n）尋找空位的過程直接變成了O（1）。