Johnny Sack - 2 months ago 14

Java Question

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;

}

}

Answer

The issue is that you are iterating too far over the linked list in your `else if (count >= n && n != 1)`

block.

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`

).

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++;
}
```

Source (Stackoverflow)