Wednesday, October 20, 2010

Stack in java using link list

The three methods that stands out for a stack are pop(), push() and peek().
push() - push elements into a stack. We will use the insertAtFirst() method of LinkedList. Throws StackOverflowException when the stack is full.
pop() - remove and returns the top element from a stack. We will use the removeAtFirst() method of LinkedList. Throws StackEmptyException when the stack is empty.
peek() - return the top element from the stack without removing it. We will use the getFirst() method of LinkedList. Throws StackEmptyException when the stack is empty.

The java code for this looks very simpler. We will make use of the existing SinglyLinkedList class that we have used before.

package dsa.stack;

import dsa.linkedlist.SinglyLinkedList;

public class Stack<E> extends SinglyLinkedList<E>{

public static final int MAX_STACK_SIZE = 100;

public E pop() throws StackEmptyException{
if(this.size()==0){
throw new StackEmptyException();
}
return this.removeAtFirst();
}

public E peek() throws StackEmptyException{
if(this.size()==0){
throw new StackEmptyException();
}
return this.getFirst().data;
}

public void push(E data) throws StackOverflowException{
if(this.size()>MAX_STACK_SIZE){
throw new StackOverflowException();
}
this.insertAtFirst(data);
}

public static void main(String args[]){
Stack<Integer> stack = new Stack<Integer>();
try{
System.out.println("Pushing 1, 2, 3, 4, 5");
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
System.out.println("Pop once : "+stack.pop());
System.out.println("Peek once : "+stack.peek());
System.out.println("Pop once : "+stack.pop());
System.out.println("Pop once : "+stack.pop());
System.out.println("Pop once : "+stack.pop());
System.out.println("Pop once : "+stack.pop());
System.out.println("Pop once : "+stack.pop());
}catch(StackEmptyException e){
System.out.println(e.getMessage());
}catch(StackOverflowException e){
System.out.println(e.getMessage());
}
}
}
/*
SAMPLE OUTPUT:
Pushing 1, 2, 3, 4, 5
Pop once : 5
Peek once : 4
Pop once : 4
Pop once : 3
Pop once : 2
Pop once : 1
Stack is empty!
*/

package dsa.stack;

public class StackEmptyException extends Exception{
public StackEmptyException(){
super("Stack is empty!");
}
}
package dsa.stack;

public class StackOverflowException extends Exception{
public StackOverflowException(){
super("Stack Overflown");
}
}

No comments:

Post a Comment

Chitika