Thursday, 7 August 2014

Java - Stack using Linked List



/*
 * 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