多堆疊操作的演算法及模擬

Abstract

在討論連續配位時，堆疊是很重要的資料結構之一。當我們的系統需要多個堆疊時， 推疊溢位是不可避免的。假如我們使用分開的多個堆疊，並且分配每個堆疊固定的大 小，只要有一個推疊發生溢位，我們就必須很不情願的中止程式。假如我們分配每個 堆疊最大的空間，因為幾乎不可能所有的堆疊同時用盡它們的最大空間，因此是很浪 費的方法。 多堆疊是個可變大小的堆疊共存在連續的位置，多堆疊是解決上面缺點的較佳策略。 Knuth 及Garwick 提出Knuth 演算法及Garwick 演算法，來解決多堆疊的溢位問題。 在本篇論文，我們提出兩個演算法，來處理上述問題，一個稱為雙群演算法，另一個 稱為多群演算法。 經模擬及數學分析，我們發現雙群演算法中資料移動的平均次數，小於Knuth 演算法 。經模擬，我們發現多群演算法中資料移動的平均次數，小於Garwick 演算法。