/*
* Implements a generic type of node to implement a generic stack - see here - using a generic linked list
*/
public class Node<E> {
// instance variables
private E element;
private Node<E> next;
// create a node with null references
public Node() {
this(null, null);
}
//create a node with the given elemment and next node
public Node(E e , Node<E> n){
element = e;
next = n ;
}
//accessor methods
public E getElement(){
return element;
}
public Node<E> getNext(){
return next;
}
//modifier methods
public void setElement(E newElem){
this.element = newElem ;
}
public void setNext(Node<E> newNext){
next = newNext;
}
}
/*
* Implements the Stack interface - see here - using a singly linked list , whose nodes are objects of class Node
* All mehtods of Stack interface are executed in constant time
* Space requirement - O(n)
* New exception creation for overflow problem is not required , unlike arrays based stack
*
*/
import java.util.EmptyStackException;
public class NodeStack<E> implements Stack<E> {
protected Node<E> top;// reference to head
protected int size;
// construct an empty stack
public NodeStack() {
top = null;
size = 0;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
if (top == null)
return true;
return false;
}
@Override
public E top() throws EmptyStackException {
if(isEmpty()) throw new EmptyStackException();
return top.getElement();
}
@Override
public void push(E element) {
Node<E> v = new Node<>(element, top); // create and link in a new node
top = v;
++size;
}
@Override
public E pop() {
if(isEmpty()) throw new EmptyStackException();
E temp = top.getElement();
top = top.getNext(); // link out former top node
--size;
return temp ;
}
}
No comments:
Post a Comment