我的大學老師教會了我們這個堆棧的實現。但這是一個完全遞歸的,我在網上任何地方都沒有見過這樣的事情。所以我想知道這有多好或有效。正如我所見過的使用鏈表(使用鏈表)和使用數組的很多Stacks的實現。堆棧遞歸實現複雜性
public class Stack<T>
{
private T top;
private Stack<T> base;
public Stack(){
top = null;
base = null;
}
public Stack(T data, Stack<T> base){
top = data;
this.base = base;
}
public boolean isEmpty(){
return top == null;
}
public T top(){
return top;
}
public T push(T data){
if (isEmpty()){
top = data;
base = new Stack<T>();
} else {
base = new Stack<T>(top, base);
top = data;
}
return data;
}
public T pop(){
T res = null;
if (!isEmpty()){
res = top;
top = base.top;
base = base.base;
}
return res;
}
}
請我想聽聽您的意見,因爲我真的沒有看到過這種實現任何其他。請隨時解釋複雜性!
遞歸在哪裏? – rendon
所以它是基於鏈接列表而不是數組的堆棧。這意味着O(1)的推動和流行 - 你不必擔心增長陣列。隨機訪問將是O(n),但這通常不是如何使用堆棧。 – Blorgbeard
所有的操作都是O(1)。沒有看到這個實現有什麼問題。 –