在java中使用链表制作dropout堆栈的麻烦 [英] trouble with making a dropout stack with linked lists in java
问题描述
所以在我的作业中,我必须用 Java 实现一个 dropout 堆栈.drop-out 堆栈在各个方面都像堆栈,除了如果堆栈大小为 n,那么当 n+1 元素被压入时,第一个元素会丢失.就我而言,我设置了 n=5.我的代码运行良好,但是当我在第 5 个元素之后添加更多元素时,底部的元素没有被删除.它只是像普通堆栈一样将新的堆栈堆叠在顶部.请帮助我了解如何解决此问题.这是我的堆栈实现代码:
So in my assignment, I have to implement a dropout stack in Java. A drop-out stack behaves like a stack in every respect except that if the stack size is n, then when the n+1 element is pushed, the first element is lost. In my case, I have set n=5. My code is running fine, but when I add more elements after the 5th element, the element at the bottom is not being removed. It just keeps stacking the new ones on top like a normal stack. Please help me understand how to fix this. Here is my code for the stack implementation:
/**
* Represents a linked implementation of a stack.
*
* @author Java Foundations
* @version 4.0
*/
public class DropOutStack<T> implements StackADT<T>
{
private int count; //number of elements in the stack
private LinearNode<T> top;
/*Declares the maximum number of elements in the stack*/
private final int n = 5;//max size
private LinearNode<T> prev;
private LinearNode<T> curr;
/**
* Creates an empty stack.
*/
public DropOutStack()
{
count = 0;
top = null;
}
/**
* Adds the specified element to the top of this stack.
* @param element element to be pushed on stack
*/
public void push(T element)
{
LinearNode<T> temp = new LinearNode<T>(element);
/*Verifies that the number of elements in the stack is
* less than n. If yes, adds the new element to the stack*/
if (count < n) {
temp.setNext(top);
top = temp;
count++;
}
/*Verifies if the number of elements in the stack is greater
* than or equal to n or not, and that the n is not equal to one.
* If yes, removes the first element from the stack and adds
* the new element to the stack*/
else if(count>=n && n!=1) {
prev = top;
curr = top.getNext();
while(curr != null) {
prev = prev.getNext();
curr = curr.getNext();
}
prev.setNext(null);
count--;
push(element);
}
else //if n=1
{
top.setElement(element);
}
}
/**
* Removes the element at the top of this stack and returns a
* reference to it.
* @return element from top of stack
* @throws EmptyCollectionException if the stack is empty
*/
public T pop() throws EmptyCollectionException
{
if (isEmpty())
throw new EmptyCollectionException("stack");
T result = top.getElement();
top = top.getNext();
count--;
return result;
}
/**
* Returns a reference to the element at the top of this stack.
* The element is not removed from the stack.
* @return element on top of stack
* @throws EmptyCollectionException if the stack is empty
*/
public T peek() throws EmptyCollectionException
{
if (isEmpty())
throw new EmptyCollectionException("stack");
T result = top.getElement();
return result;
}
/**
* Returns true if this stack is empty and false otherwise.
* @return true if stack is empty
*/
public boolean isEmpty()
{
return (count ==0);
}
/**
* Returns the number of elements in this stack.
* @return number of elements in the stack
*/
public int size()
{
return count;
}
/**
* Returns a string representation of this stack.
* @return string representation of the stack
*/
public String toString()
{
String result = "";
LinearNode<T> current = top;
while (current != null) {
result = current.getElement() + "\n" + result;
current = current.getNext();
}
return result;
}
}
推荐答案
问题是您在 else if (count >= n && n !=1)
块.
当前你在 curr == null
时终止,但如果 curr
是 null
那么 prev
是最后一个列表中的节点,谁的下一个值已经是null
(curr
).
Currently you terminate when curr == null
, but if curr
is null
then prev
is the last node in the list, who's next value is already null
(curr
).
要解决此问题,请将循环条件更改为 curr.getNext() != null
.由于您总是想推送元素,因此在最后执行并简化逻辑,前提是 n(最大大小 [可怜的名称])应至少为 1.
To resolve this, change the loop condition to curr.getNext() != null
. Since you always want to push the element, just do that at the end and simplify the logic, given the precondition that n (the max size [poor name]) should be at least 1.
/**
* @pre. n >= 1
*/
public void push(T element) {
if (count >= n) {
assert top != null;
prev = null;
curr = top;
while (curr.getNext() != null) {
prev = curr;
curr = curr.getNext();
}
if (prev != null) {
prev.setNext(null);
} else {
top = null;
}
count--;
}
LinearNode<T> temp = new LinearNode<>(element);
temp.setNext(top);
top = temp;
count++;
}
这篇关于在java中使用链表制作dropout堆栈的麻烦的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!