我正在使用 eclipse 阅读有关 java 语言中的树实现的信息......我发现需要实现推送和弹出方法...以下是我的老师实现的两种方法：
public class LimitedStack<E> {
private Node<E> first; // refererar till första elementet i listan
private Node<E> last; // refererar till sista elementet i listan
private int size; // antal element i listan
private int maxSize; // maximalt antal tillåtna element i listan
public LimitedStack(int maxSize) {
first = last = null;
size = 0;
this.maxSize = maxSize;
}
public void push(E x) {
Node<E> n = new Node<E>(x);
if (first == null) {//no overflow in this case
first = n;
size++;
} else { // add new node to front
n.next = first;
first = n;
if (size == maxSize) { //overflow, at least two elements
Node<E> p = first;
while (p.next.next != null) { //lookup second last
p = p.next;
}
p.next = null; //remove last from list
} else { //no overflow, increase size
size++;
}
}
}
public E pop() {
if (size == 0) {
return null;
}
E temp = first.element;
first = first.next;
size--;
return temp;
}
}
当我自己实现这些方法时，我这样做：
public void push(E x) {
if(first == null) {
first = new Node<E>(x);
} else if (size==maxSize) {
Node<E> act = first;
last =null;
first = new Node<E>(x);
first.next=act;
} else {
Node<E> act = first;
first = new Node<E>(x);
first.next=act;
}
size++;
}
public E pop() {
if(size == 0) {
return null;
} else {
Node<E> act = first;
first = act.next;
return act.element;
size--;
}
}
如果我们将其与老师的答案进行比较，我的实现是否正确？
谢谢
这是
不正确的。
在push()中，您将其分为 3 个条件。
- 链表为空
- 链表已满
- 链表既不为空也不满
您的代码将在第二个条件下失败。当链表已满时，根据老师的回答，你应该将新元素推入列表中，删除列表中的最后一个元素，链表的大小不会修改。
在代码中，您没有删除最后一个元素。将 last 设置为 null，但从不将 last 设置为正确的值而不是 null。并且链表的size仍然会增加，因为您将size++放在if else之外。
所以你的push()代码应该是这样的：
public void push(E x) {
Node<E> newNode = new Node<E>(x);
if(first == null) {
first = newNode;
size++;
} else if (size==maxSize) {
Node<E> act = first;
// last =null;
first = newNode;
first.next=act;
} else {
Node<E> act = first;
first = newNode;
first.next=act;
size++;
}
}
和你的pop()功能。实际上，您可以看到您的代码与教师的代码非常相似。但是，您需要将size--;放在return act.element;之前，因为当该方法执行return语句时，它通常会退出方法并返回给调用方，至少在您的代码中是这样。
正如@SashaSalauyou所说，这不是一棵树，它现在只是一个链表，你至少应该在你的push()和pop()写一些test codes，看看你的链表是否正确。例如，您可以尝试推送一些值并在main中弹出一些值，并使用调试器检查链表是否正常工作。
不，这是不正确的。在弹出函数中的返回语句后减小大小。