Given a stack, following program recursively reverses it:
/** * @author vikky.agrawal * Stack reversal */ public class StackImpl { Node top =null; public static void main(String[] arg){ StackImpl stack=new StackImpl(); stack.stackOperations(); } public void stackOperations(){ for (int i = 1; i < 10; i++) { push((int) (Math.random() * 100)); } printStack(); top=this.reverseStack(top); System.out.println("Stack after reverse"); printStack(); } public Node reverseStack(Node tos){ ///base case if(tos==null || tos.getLink()==null){ return tos; } //point temp to last node and then set link recursively. Node temp=reverseStack(tos.getLink()); tos.getLink().setLink(tos); //a->b->c->null,set b's backward link a<-b<-c; // and set b's forward link as null tos.setLink(null); return temp; //always last node, hence top of reversed Stack } /** * Helper functions for stack operations */ public void push(int data){ if(top==null){ top=new Node(data); }else{ Node temp=new Node(data); temp.setLink(top); top=temp; } } public int pop(){ if(top==null){ return -1; }else{ Node temp=top; top=top.getLink(); return temp.getData(); } } public int peek(){ if(top!=null){ return top.getData(); }else{ return -1; } } public boolean isEmpty(){ if(top==null) return true; return false; } public int size(){ int size=0; Node temp=top; while(temp!=null){ size++; temp=temp.getLink(); } return size; } public void printStack(){ Node temp=top; System.out.print("Top->\n"); while(temp!=null){ System.out.println(temp.getData()+"\n|"); temp=temp.getLink(); } System.out.println("/null"); } /** * static inner class to be used for Stack Data Structure */ static class Node{ private int data; private Node link; Node(){ } Node(int data){ //mergedList=new Node(); this.setData(data); this.setLink(null); } public int getData(){ return this.data; } public Node getLink(){ return this.link; } public void setData(int data){ this.data=data; } public void setLink(Node link){ this.link=link; } } }
No comments:
Post a Comment