Stack is a data structure that follows the simple FILO (First In, Last out) or LIFO (Last In, First Out) rule. Imagine a real world stack where you arrange Notebooks one over the other. The first notebook you insert will be at the bottom and that will come only at last. The implementation of stack can be done in many ways. We are going to see how to make use of a Singly Linked List to the use.
We can implement stack using a Linked List in the below shown ways. One is to have the END node on top and other is to have the START node at the top. If we recollect the singly linked list data structure, insertAtFirst() is an operation which can be done in O(1) time and insertAtLast() will take O(n) time (because we need to traverse till the last node). So, we can make use of the second method to use stack using linkedlists.
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");
}
}
Cheers,
Bragaadeesh.
