1
대학의 선생님은 Stack의 구현에 대해 가르쳐 왔습니다. 그러나이 웹 사이트는 완전히 재귀 적이며 웹상의 어느 곳에서도 이와 같은 것을 보지 못했습니다. 그래서 나는 이것이 얼마나 훌륭하거나 효율적인지 궁금해하고있었습니다. Linked List (가장 효율적인 것)를 사용하고 배열을 사용하여 스택 구현을 많이 보았습니다.스택 재귀 구현 복잡성
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)입니다. 이 구현에서 잘못된 점을 보지 마십시오. –