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