Stack Implemention in Java

  Stack Implementation [Static and Dynamic] in                                 Java

A Stack is a ordered list in which insertion and deletion are done at one end,calles as top.The last element inserted is the first one to be deleted.

Hence,it is called LAST IN FIRST OUT(LIFO)  and FIRST IN LAST OUT(FILO).

Stack ADT

->void push(String data)    :-         Insert data into stack

->String pop()                    :-          Delete data from top of statck.

Applications:-

• Balancing of symbols.
• Infix-to-postfix operation.
• Evaluation of postfix expression.
• Implementing function calls(including recursion).
• Page-visisted history in a Web Browser(Back Buttons).
• Undo sequence in a text Editor.
• Matching Tags in HTML and XML.

Implementations:-

These examples is given for only stack of strings and in which input as String separated by one space means push that two strings in stack and Hyphen i.e.(-) means perform pop operation.

e.g.

Hi I - am - 

means     

                    push("Hi")

                    push("I")

                    pop()

                    push("am")

                    pop()

                               Fixed size Array Implementation in Java.

Java Program:-

/**
 * @(#)FixedCapacityStack.java
 *
 *
 * @author 
 * @version 1.00 2015/3/2
 */

import java.io.*;
import java.util.*;


class FixedSizeStringStack{

private String s[];
private int top=0;

public FixedSizeStringStack(int N){
s=new String[N];
}

public void push(String data){
if(top==s.length){
System.out.println("OverFlow...");
return;
}
s[top++]=data;
}

public String pop(){
if(top==0){
System.out.println("UnderFlow");
return null;
}
String data=s[--top];
s[top]=null;
return data;
}

public boolean isEmpty(){
return top==0;
}


}

class FixedCapacityStack {

    public static void main(String ar[])throws IOException{
   
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer str=new StringTokenizer(br.readLine());
    FixedSizeStringStack s=new FixedSizeStringStack(10);
   
    String input=str.nextToken();
   
    while(true){
   
    if(input.equals("-")){
    System.out.print(s.pop()+" ");
    }else{
    s.push(input);
    }
   
    if(str.hasMoreTokens()){
    input=str.nextToken();
    }else{
    break;
    }
    }
   
   
    }
    
    

}
 

                                    Dynamic Implementation of Stack in Java.

Java Program:-


/**
 * @(#)StackOfStrings.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2015/3/2
 */

import java.io.*;
import java.util.*;


class StringStack{

private Node first=null;

private class Node{
String data;
Node next;
}

public void push(String s){
Node temp=new Node();
temp.data=s;
temp.next=first;
first=temp;
}

public String pop(){
String data=first.data;
first=first.next;
return data;
}

public boolean isEmpty(){
return first==null;
}
}


class StackOfStrings {

    public static void main(String ar[])throws IOException{
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer str=new StringTokenizer(br.readLine());
    StringStack s=new StringStack();
   
    String input=str.nextToken();
   
    while(true){
   
    if(input.equals("-")){
    System.out.print(s.pop()+" ");
    }else{
    s.push(input);
    }
   
    if(str.hasMoreTokens()){
    input=str.nextToken();
    }else{
    break;
    }
    }
    }
    

}



Input:-
to be or not to - be - - that - - - is

Output:-
to be not that or be


Performance:-

push operation               =>       O(1)

pop operation                 =>       O(1)

----------------X---------------X----------------X-----------------X-----------------X------------