palindrome by using stack

import java.util.Stack;
import java.util.Scanner;
class Palindromstack
 {
     public static void main(String[] args)
        {
           System.out.print("Enter any string:");
           Scanner in=new Scanner(System.in);
           String inputString = in.nextLine();
           Stack stack = new Stack();
           for (int i = 0; i < inputString.length(); i++)
             {
                stack.push(inputString.charAt(i));
             }

             String reverseString = "";
             while (!stack.isEmpty())
                {
                    reverseString = reverseString+stack.pop();
                }
               if (inputString.equals(reverseString))
                  System.out.println("The input String is a palindrome.");
              else
                 System.out.println("The input String is not a palindrome.");
         }
   }

palindrome using queues


import java.util.Queue;
import java.util.Scanner;
import java.util.LinkedList;
class Palindromequeue {

    public static void main(String[] args) {

        System.out.print("Enter any string:");
        Scanner in=new Scanner(System.in);
        String inputString = in.nextLine();
        Queue queue = new LinkedList();

        for (int i = inputString.length()-1; i >=0; i--) {
            queue.add(inputString.charAt(i));
        }

        String reverseString = "";

        while (!queue.isEmpty()) {
            reverseString = reverseString+queue.remove();
        }
        if (inputString.equals(reverseString))
            System.out.println("The input String is a palindrome.");
        else
            System.out.println("The input String is not a palindrome.");

    }
}

convert a given infix expression into postfix form using stack

      import java.lang.*;
      import java.io.*;
      import java.util.*;
      class charstack
 {
 int top,size;
 char stack[],ele;
 charstack(int n)
 {
 size=n;
 top=-1;
stack=new char[n];
}
void push(char x)
{
ele=x;
if(!isfull())
{
stack[++top]=ele;
}
else
System.out.println("stack is full");
}
char pop()
{
if(!isempty())
{
return stack[top--];
}
else
{
System.out.println("stack is empty");
return 'a';
}
}
boolean isempty()
{
if(top==-1)
return true;
else
return false;
}
boolean isfull()
{

if(top>size)
return true;
else
return false;
}
void display()
{
if(!isempty())
System.out.println("="+stack[top]);
else
System.out.println("stack is empty");
}
char peek()
{
return stack[top];
}
}
class iftopf
{
charstack cs;
char pf[];
iftopf()
{
cs=new charstack(50);
pf=new char[50];
}
boolean iop(char op)
{
if(op=='+'||op=='-'||op=='*'||op=='/'||op=='('||op==')'||op=='^'||op=='%')
return true;
else
return false;
}
int prec(char op)
{
if(op=='+'||op=='-')
return 1;
else if(op=='/'||op=='*')
return 2;
else if(op=='%'||op=='^')
return 3;
return 0;
}
void infixtop(String infix)
{
char isym;
int j=0;
char ir[]=infix.toCharArray();
for(int i=0;i<ir.length;i++)
{
isym=ir[i];
if(!iop(isym))
{
pf[j]=isym;
j++;
}
else
{
if(isym=='('||cs.isempty())
cs.push(isym);
else if(isym==')')
{
while(cs.peek()!='(')
{
pf[j]=cs.pop();
j++;
}
char v=cs.pop();
}
else if(cs.isempty())
cs.push(isym);
else if(cs.isempty()||cs.peek()=='('||(prec(cs.peek())<prec(isym)))
cs.push(isym);
else
{
while((!cs.isempty())&&(cs.peek()!='(')&&prec(cs.peek())>=prec(isym))
{
pf[j]=cs.pop();
j++;
}
cs.push(isym);
}
}
}
while(!cs.isempty())
{
pf[j]=cs.pop();
j++;
}
}
void display1()
{
for(int i=0;i<pf.length-1;i++)
System.out.print(pf[i]);
}
public static void main(String args[])throws Exception
{
iftopf ob=new iftopf();
Scanner r=new Scanner(System.in);
System.out.println("enter any equation:");
String s=r.nextLine();
ob.infixtop(s);
ob.display1();
}
}
Output:

circular queue ADT using an array.

import java.util.*;
class CirQue
{
int front,rear,next=0;
int que[];
int max,count=0;
CirQue(int n)
{
max=n;
que=new int[max];
front=rear=-1;
}
boolean isfull()
{
if(front==(rear+1)%max)
return true;
else
return false;
}
boolean isempty()
{
if(front==-1&&rear==-1)
return true;
else
return false;
}
int delete()
{
if(isempty())
{
return -1;
}
else
{
count --;
int x=que[front];
if(front==rear)
front=rear=-1;
else
{
next=(front+1)%max;
front=next;
}
return x;
}
}
void insert(int item)
{
if(isempty())
{
que[++rear]=item;
front=rear;
count ++;
}
else if(!isfull())
{
next=(rear+1)%max;
if(next!=front)
{
que[next]=item;
rear=next;
}
count ++;
}
else
System.out.println("q is full");
}
void display()
{
if(isempty())
System.out.println("queue is empty");
else
next=(front)%max;
while(next<=rear)
{
System.out.println(que[next]);
next++;
}
}
int size()
{
return count;
}
public static void main(String args[])
{
int ch;
Scanner s=new Scanner(System.in);
System.out.println("enter limit");
int n=s.nextInt();
CirQue q=new CirQue(n);
do
{
System.out.println("1.insert");
System.out.println("2.delete");
System.out.println("3.display");
System.out.println("4.size");
System.out.println("enter ur choice :");
ch=s.nextInt();
switch(ch)
{
case 1:System.out.println("enter element :");
int n1=s.nextInt();
q.insert(n1);
break;
case 2:int c1=q.delete();
if(c1>0)
System.out.println("deleted element is :"+c1);
else
System.out.println("can't delete");
break;
case 3:q.display();
break;
case 4:System.out.println("queue size is "+q.size());
break;
}
}
while(ch!=0);
}
}

implement the Stack ADT,Queue ADT using an array.

stack ADT
import java.io.*;
class stackclass
{
int top,ele,stack[],size;
stackclass(int n)
{
stack=new int[n];
size=n;
top=-1;
}
void push(int x)
{
ele=x;
stack[++top]=ele;
}
int pop()
{
if(!isempty())
{
System.out.println("Deleted element is");
return stack[top--];
}
else
{
System.out.println("stack is empty");
return -1;
}
}
boolean isempty()
{
if(top==-1)
return true;
else
return false;
}
boolean isfull()
{
if(size>(top+1))
return false;
else
return true;
}
int peek()
{
if(!isempty())
return stack[top];
else
{
System.out.println("stack is empty");
return -1;
}
}
void size()
{
System.out.println("size of the stack is :"+(top+1));
}
void display()
{
if(!isempty())
{
for(int i=top;i>=0;i--)
System.out.print(stack[i]+" ");
}
else
System.out.println("stack is empty");
}
}class stacktest
{
public static void main(String args[])throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("enter the size of stack");
int size=Integer.parseInt(br.readLine());
stackclass s=new stackclass(size);
int ch,ele;
do
{
System.out.println();
System.out.println("1.push");
System.out.println("2.pop");
System.out.println("3.peek");
System.out.println("4.size");
System.out.println("5.display");
System.out.println("6.is empty");
System.out.println("7.is full");
System.out.println("8.exit");
System.out.println("enter ur choise :");
ch=Integer.parseInt(br.readLine());
switch(ch)
{
case 1:if(!s.isfull())
{
System.out.println("enter the element to insert: ");
ele=Integer.parseInt(br.readLine());
s.push(ele);
}
else
{
System.out.print("stack is overflow");
}
break;
case 2:int del=s.pop();
if(del!=-1)
System.out.println(del+" is deleted");
break;
case 3:int p=s.peek();
if(p!=-1)
System.out.println("peek element is: "+p);
break;
case 4:s.size();
break;
case 5:s.display();
break;
case 6:boolean b=s.isempty();
System.out.println(b);
break;
case 7:boolean b1=s.isfull();
System.out.println(b1);
break;
}
}
while(ch!=0);
}
}

queue ADT
import java.util.*;
class queue
{
int front,rear;
int que[];
int max,count=0;
queue(int n)
{
max=n;
que=new int[max];
front=rear=-1;
}
boolean isfull()
{
if(rear==(max-1))
return true;
else
return false;
}
boolean isempty()
{
if(front==-1)
return true;
else
return false;
}
void insert(int n)
{
if(isfull())
System.out.println("list is full");
else
{
rear++;
que[rear]=n;
if(front==-1)
front=0;
count++;
}
}
int delete()
{
int x;
if(isempty())
return -1;
else
{
x=que[front];
que[front]=0;
if(front==rear)
front=rear=-1;
else
front++;
count--;
}
return x;
}
void display()
{
if(isempty())
System.out.println("queue is empty");
else
for(int i=front;i<=rear;i++)
System.out.println(que[i]);
}
int size()
{
return count;
}
public static void main(String args[])
{
int ch;
Scanner s=new Scanner(System.in);
System.out.println("enter limit");
int n=s.nextInt();
queue q=new queue(n);
do
{
System.out.println("1.insert");
System.out.println("2.delete");
System.out.println("3.display");
System.out.println("4.size");
System.out.println("enter ur choise :");
ch=s.nextInt();
switch(ch)
{
case 1:System.out.println("enter element :");
int n1=s.nextInt();
q.insert(n1);
break;
case 2:int c1=q.delete();
if(c1>0)
System.out.println("deleted element is :"+c1);
else
System.out.println("can't delete");
break;
case 3:q.display();
break;
case 4:System.out.println("queue size is "+q.size());
break;
}
}
while(ch!=0);
}
}

implement the Stack ADT,Queue ADT using a singly linked list

stack ADT
import java.io.*;
class Stack
{
Stack top,next,prev;
int data;
Stack()
{
data=0;
next=prev=null;
}
Stack(int d)
{
data=d;
next=prev=null;
}
void push(int n)
{
Stack nn;
nn=new Stack(n);
if(top==null)
top=nn;
else
{
nn.next=top;
top.prev=nn;
top=nn;
}
}
int pop()
{
int k=top.data;
if(top.next==null){
top=null;
return k;}
else{
top=top.next;
top.prev=null;
return k;
}
}
boolean isEmpty()
{
if(top==null)
return true;
else
return false;
}
void display()
{
Stack ptr;
for(ptr=top;ptr!=null;ptr=ptr.next)
System.out.print(ptr.data+" ");
}
public static void main(String args[ ])throws Exception
{
int x;
int ch;
BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
Stack a=new Stack();
do{
System.out.println("enter 1 for pushing");
System.out.println("enter 2 for poping");
System.out.println("enter 3 for isEmpty");
System.out.println("enter 4 for display");
System.out.println("Enter 0 for exit");
System.out.println("enter ur choice ");
ch=Integer.parseInt(b.readLine());
switch(ch)
{
case 1:System.out.println("enter element to insert");
int e=Integer.parseInt(b.readLine());
a.push(e);
break;
case 2:if(!a.isEmpty())
{
int p=a.pop();
System.out.println("deleted element is "+p);
}
else
{
System.out.println("stack is empty");
}
break;
case 3:System.out.println(a.isEmpty());
break;
case 4:if(!a.isEmpty())
{
a.display();
}
else
{
System.out.println("list is empty");
}
}
}while(ch!=0);
}
}
OUTPUT:

b. queue ADT
import java.io.*;
class Qlnk
{
Qlnk front,rear,next;
int data;
Qlnk()
{
data=0;
next=null;
}
Qlnk(int d)
{
data=d;
next=null;
}
Qlnk getFront()
{
return front;
}
Qlnk getRear()
{
return rear;
}
void insertelm(int item)
{
Qlnk nn;
nn=new Qlnk(item);
if(isEmpty())
{
front=rear=nn;
}
else
{
rear.next=nn;
rear=nn;
}
}
int delelm()
{
if(isEmpty())
{
System.out.println("deletion failed");
return -1;
}
else
{
int k=front.data;
if(front!=rear)
front=front.next;
else
rear=front=null;
return k;
}
}
boolean isEmpty()
{
if(rear==null)
return true;
else
return false;
}
int size()
{
Qlnk ptr;
int cnt=0;
for(ptr=front;ptr!=null;ptr=ptr.next)
cnt++;
return cnt;
}
void display()
{
Qlnk ptr;
if(!isEmpty())
{
for(ptr=front;ptr!=null;ptr=ptr.next)
System.out.print(ptr.data+" ");
}
else
System.out.println("q is empty");
}
public static void main(String arr[])throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
Qlnk m=new Qlnk();
int ch;
do
{
System.out.println("enter 1 for insert");
System.out.println("enter 2 for deletion");
System.out.println("enter 3 for getFront");
System.out.println("enter 4 for getRear");
System.out.println("enter 5 for size");
System.out.println("enter 6 for display");
System.out.println("enter 0 for exit");
System.out.println("enter ur choice");
ch=Integer.parseInt(br.readLine());
switch(ch)
{
case 1:System.out.println("enter ele to insert");
int item=Integer.parseInt(br.readLine());
m.insertelm(item);break;
case 2:int k=m.delelm();
System.out.println("deleted ele is "+k);break;
case 3:System.out.println("front index is"+(m.getFront()).data);break;
case 4:System.out.println("rear index is"+(m.getRear()).data);break;
case 5:System.out.println("size is"+m.size());break;
case 6:m.display();break;
}
}while(ch!=0);
}
}

implement the List ADT using Arrays

import java.io.*;
interface ListADT
{
void traversal();
boolean isFull();
boolean isEmpty();
int search(int key);
void insertAtBeg(int item);
void insertAtEnd(int item);
void insertAtPos(int pos,int item);
void insertAfterPos(int pos,int item);
void insertAfterKey(int key,int item);
void delete(int key);
void deletePos(int pos);
}
class ArrayDS implements ListADT
{
int a[],n,max;
ArrayDS(int cap)
{
max=cap;
a=new int[max];
n=0;
}
public void traversal()
{
for(int i=0;i<n;i++)
System.out.print(a[i]+" ");
System.out.println("\n");
}
public boolean isFull()
{
if(n==max)
return true;
return false;
}
public boolean isEmpty()
{
if(n==0)
return true;
return false;
}
public int search(int key)
{
for(int i=0;i<n;i++)
if(a[i]==key)
return i;
return -1;
}
public void insertAtBeg(int item)
{
if(!isFull())
{
for(int i=n-1;i>=0;i--)
a[i+1]=a[i];
a[0]=item;
n++;
}
else
System.out.println("Array is Full, cannot insert");
}
public void insertAtEnd(int item)
{
if(!isFull())
{
a[n++]=item;
}
else
System.out.println("Array is Full, cannot insert");
}
public void insertAtPos(int pos,int item)
{
if(!isFull())
{
for(int i=n-1;i>=pos;i--)
a[i+1]=a[i];
a[pos]=item;
n++;
}
else
System.out.println("Cannot insert, Array is Full");
}
public void insertAfterPos(int pos,int item)
{
if(pos<n)
insertAtPos(pos+1,item);
else
System.out.println("Array is Full, cannot insert");
}
public void insertAfterKey(int key,int item)
{
int p=search(key);
if(p==-1)
System.out.println("Cannot insert");
else
insertAfterPos(p,item);
}
public void delete(int key)
{
if(!isEmpty())
{
int p=search(key);
deletePos(p);
}
else
System.out.println("Array is Empty");
}
public void deletePos(int pos)
{
if(!isEmpty())
{
if(pos<0||pos>n-1)
{
System.out.println("Cannot delete, Element not found");
}
else
{
for(int i=pos;i<n-1;i++)
a[i]=a[i+1];
n--;
}
}
else
System.out.println("Array is Empty");
}
}
class ArrayTest
{
public static void main(String arg[]) throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the size of the Array");
int n=Integer.parseInt(br.readLine());
ArrayDS ar=new ArrayDS(n);
System.out.println("Array is created");
ar.traversal();
int t,k,m=1;
do
{
System.out.println("Enter ur choice of operation");
System.out.println("1-insertAtBeg\n2-insertAtEnd\n3-insertAtPos\n4-insertAfterPos\n5-insertAfterKey\n6-deleteItem\n7-deletePos\n0-exit");
n=Integer.parseInt(br.readLine());
switch(n)
{
case 1:
System.out.println("Enter the element to be inserted");
t=Integer.parseInt(br.readLine());
ar.insertAtBeg(t);
ar.traversal();
break;
case 2:
System.out.println("Enter the element to be inserted");
t=Integer.parseInt(br.readLine());
ar.insertAtEnd(t);
ar.traversal();
break;
case 3:
System.out.println("Enter the element to be inserted:");
t=Integer.parseInt(br.readLine());
System.out.println("Enter the index position to insert at:");
k=Integer.parseInt(br.readLine());
ar.insertAtPos(k,t);
ar.traversal();
break;
case 4:
System.out.println("Enter the element to be inserted");
t=Integer.parseInt(br.readLine());
System.out.println("Enter the index position to insert after");
k=Integer.parseInt(br.readLine());
ar.insertAfterPos(k,t);
ar.traversal();
break;
case 5:
System.out.println("Enter the element to be inserted:");
t=Integer.parseInt(br.readLine());
System.out.println("Enter the key element to insert aftter:");
k=Integer.parseInt(br.readLine());
ar.insertAfterKey(k,t);
ar.traversal();
break;
case 6:
System.out.println("Enter the element to be deleted");
t=Integer.parseInt(br.readLine());
ar.delete(t);
ar.traversal();
break;
case 7:
System.out.println("Enter the position to be deleted");
t=Integer.parseInt(br.readLine());
ar.deletePos(t);
ar.traversal();
break;
case 0:
m=0;
break
default:
System.out.println("INVALID CHOICE");
}
}while(m==1);
ar.traversal();
}
}