queue Implementation

Queue Implementation in java :
Standard library in java: java.util.queue:
methods in standard library

//to add element 
add() : return true if it success to add otherwise it throw exception.
offer(): return true if it success and false if it fail to add.

// retrieve and remove first element
remove(): throw exception NoSuchElementException if queue is  empty
poll(): return  null if queue is empty

//give to element but don't remove 
element(): throw exception NoSuchElementException if queue is  empty
peek(): return  null if queue is empty

Queue implementation using:
a) circular array
b) dynamic array
c) linked list

a)Circular array:
package queue;

public class Queue
{


int front;
int rear;
int capacity;
int[] array;

Queue(int size)
{
this.capacity = size;
this.rear = -1;
this.front = -1;
array = new int[capacity];
}
boolean isEmpty()
{
return (front == -1);
}
boolean isFull()
{
return ((rear + 1) % capacity == front);
}

int getQueueSize()
{
if (front == rear)
{
return 0;
}

return (capacity - front + rear + 1) % capacity;
}

boolean enQueue(int data)
{
if (this.isFull())
{
return false;
}

rear = (rear + 1) % capacity;
array[rear] = data;

if (front == -1)
{
front = rear;
}

return true;
}
int deQueue()
{
if (this.isEmpty())
{
return 0;
}

int data = array[front];

if (front == rear)
{
front = rear = -1;
}
else
{
front = (front + 1) % capacity;

}

return data;
}
public static void main(String [] arg)
{
Queue obj = new Queue(5);
System.out.println("Size of queue: " + obj.getQueueSize());
obj.enQueue(3);
obj.enQueue(4);
obj.enQueue(5);
obj.enQueue(6);
obj.enQueue(7);
obj.enQueue(8);
obj.enQueue(9);
obj.enQueue(10);
obj.enQueue(11);
obj.enQueue(12);
System.out.println("Size of queue: " + obj.getQueueSize());
System.out.println("data form queue: " + obj.deQueue());
System.out.println("data form queue: " + obj.deQueue());
System.out.println("data form queue: " + obj.deQueue());
System.out.println("data form queue: " + obj.deQueue());
System.out.println("data form queue: " + obj.deQueue());
System.out.println("data form queue: " + obj.deQueue());
System.out.println("data form queue: " + obj.deQueue());
System.out.println("data form queue: " + obj.deQueue());
}
}

Stack Implementation

Stack Implementation in java : there can be three approach to implement stack.
1) Array based
2) Dynamic array based
3) Linked list base


1) Array based Stack implementation:
package stack;

public class Stack
{
int data ;
int top;
int size;
int[] array;

Stack()
{
this.top = -1;
this.size = 20;
array = new int[this.size];
}

Stack(int value, int size)
{
this.data = value;
this.top = -1;
this.size = size;
array = new int[this.size];
}


boolean  push(int node)
{

if (this.stackIsFull())
{
return false;
}

array[++this.top] = node;
return true;
}
int pop()
{

if (this.empty())
{
return 0;
}

return array[this.top--];

}
int peek()
{

if (this.empty())
{
return 0;
}

return array[this.top];
}

void delete()
{
this.top = -1;
}
boolean empty()
{

return   this.top == -1;

}

boolean  stackIsFull()
{

return (this.top == this.size - 1);

}

public static void main(String [] arg)
{


System.out.println("Stack implementation using array");

Stack obj = new Stack();
obj.push(2);
obj.push(3);
obj.push(4);
obj.push(5);
obj.push(6);
obj.push(7);

System.out.println("Stack Element " + obj.pop());
System.out.println("Stack Element " + obj.pop());
System.out.println("Stack Element " + obj.peek());
System.out.println("Stack Element " + obj.peek());

System.out.println("Stack Element " + obj.pop());

System.out.println("Stack Element " + obj.pop());

System.out.println("Stack Element " + obj.pop());

System.out.println("Stack Element " + obj.pop());

System.out.println("Stack Element " + obj.pop());

System.out.println("Stack Element " + obj.pop());
}



}

2) Stack Implementation using dynamic array
package stack;

public class Stack
{
int data ;
int top;
int size;
int[] array;

Stack()
{
this.top = -1;
this.size = 5;
array = new int[this.size];
}

Stack(int value, int size)
{
this.data = value;
this.top = -1;
this.size = size;
array = new int[this.size];
}

void doubleStack()
{

int[] newarray = new int[this.size * 2];
System.arraycopy(this.array, 0, newarray, 0, this.size);
this.size = this.size * 2;
this.array = newarray;
}

boolean  push(int node)
{

if (this.stackIsFull())
{
this.doubleStack();
}

array[++this.top] = node;
return true;
}
int pop()
{

if (this.empty())
{
return 0;
}

return array[this.top--];

}
int peek()
{

if (this.empty())
{
return 0;
}

return array[this.top];
}

void delete()
{
this.top = -1;
}
boolean empty()
{

return   this.top == -1;

}

boolean  stackIsFull()
{

return (this.top == this.size - 1);

}

public static void main(String [] arg)
{


System.out.println("Stack implementation using array");

Stack obj = new Stack();
obj.push(2);
obj.push(3);
obj.push(4);
obj.push(5);
obj.push(6);
obj.push(7);
obj.push(8);
obj.push(9);
obj.push(01);

System.out.println("Stack Element " + obj.pop());
System.out.println("Stack Element " + obj.pop());
System.out.println("Stack Element " + obj.pop());

System.out.println("Stack Element " + obj.pop());

System.out.println("Stack Element " + obj.pop());

System.out.println("Stack Element " + obj.pop());

System.out.println("Stack Element " + obj.pop());

System.out.println("Stack Element " + obj.pop());
}



}

### Reverse the Stack elements:
void pushAtBottom(int data)
{
if (this.empty())
{
this.push(data);
return;
}

int temp = this.pop();
pushAtBottom(data);
this.push(temp);


}
void reverseStack()
{

if (this.empty())
{
return;
}

int temp = this.pop();
this.reverseStack();

this.pushAtBottom(temp);
}

LinkedList implementation

Single LinkedList implementation in java without using standard linked list library:


package example.linkedlist;

public class  LinkedList
{

int data ;
LinkedList next;
public LinkedList(int data)
{
this.data = data;
this.next = null;
}

void setdata(int value)
{
this.data = value;
}

int getdata()
{

return this.data;
}

void setnext(LinkedList  node)
{

this.next = node;
}

LinkedList getnext()
{

return this.next;
}

int listLength(LinkedList node)
{
int count = 0;

if (node == null)
{}
else
{
while (node != null)
{
count++;
node = node.getnext();
}

}

return count;
}

boolean insert(LinkedList headnode, int data, int index)
{
LinkedList newnode = new LinkedList(data);

if (headnode == null)
{

return true;
}

if (index == 1)
{
newnode.setnext(headnode.getnext());
headnode.setnext(newnode);
return true;

}

if (index < 0 || index > listLength(headnode))
{
System.out.println("index not supported");
return false;
}

for (int i = 0; i < index && headnode.getnext() != null ; i++)
{
headnode = headnode.getnext();

}

newnode.setnext(headnode.getnext());
headnode.setnext(newnode);

return true;
}

void printlist(LinkedList head)
{
while (head != null)
{
System.out.println("list vallues: " + head.data);
head = head.getnext();
}
}
boolean equal(LinkedList node)
{
if (this.data == node.data && this.next == node.next)
{
return true;
}

return false;

}

void delete(LinkedList headnode, int  node)
{
LinkedList obj = null;

while (headnode != null)
{
if (headnode.data == node)
{
if (headnode.getnext() == null)
{
headnode = null;
}
else
{
if (obj == null)
{
headnode.setdata(headnode.getnext().data);
headnode.setnext(headnode.getnext());
}
else
{
obj.setnext(headnode.getnext());
}
}
}

obj = headnode;
headnode = headnode.getnext();


}

}


public static void main(String agrs[])
{
System.out.println("linked list main block");
LinkedList head = new LinkedList(2);
System.out.println("length of linked list: " + head.listLength(head));


head.printlist(head);

head.insert(head, 3 , 1);
head.insert(head, 4 , 1);
head.insert(head, 5 , 1);
head.insert(head, 6 , 1);
head.insert(head, 7 , 1);

head.printlist(head);

System.out.println("head data: " + head.data);
head.delete(head, 2);
head.printlist(head);
}
}


Reverse the linkedList: 
LinkedList reverseRescursive(LinkedList list)         // Reverse linked list Recursively  
{
if (list == null)
{
return null;
}

if (list.getnext() == null)
{
return list;
}

LinkedList secondElem = list.getnext();
list.setnext(null);

LinkedList reverseRest = reverseRescursive(secondElem);
secondElem.setnext(list);

return reverseRest;
}

LinkedList reverseIterative(LinkedList head)           // Reverse linked list iterative 
{

LinkedList next = null, pre = null;

while (head.getnext() != null)
{
next = head.getnext();
head.setnext(pre);
pre = head;
head = next;

}

head.setnext(pre);
return head;
}

find node from a linked list at given position from end of list:
int findNodeFromEnd(LinkedList node, int position)
{
LinkedList back = node;
LinkedList front  = node;

for (int i = 1 ; i < position; i++)
{
if (front.getnext() != null)
{
front = front.getnext();
}
}

System.out.println("element " + front.getdata());

while (front.getnext() != null)
{
back = back.getnext();
front  = front.getnext();
}

return back.getdata();
}

Input / Output in Java

 Java Streams are classified into two basic types:
a) Input Stream: Read data from Source and send it to program
b) Output Stream: Takes data from program and send it to destination.

Java define two types of Stream:
a) Byte Stream: Handling input/ output  of bytes, it use to read and write binary data.
b) Character Stream: Handles data in terms of Characters it use Unicode so its more efficient.

### Byte Stream Class: Reads 8 bits bytes as a stream.

1) InputStream Class: Its a abstract  class which define methods for Reading and Closing Stream.Most of the methods defined by InputStream Class is dummy. Actual body is implementing by sub-classes.
close(); //Release the source related to the stream
read();  // read next byte
read(byte[] b) ;   //Read  Some number of bytes and store it into buffer array b
read(byte[] b , int offset, int length) //

2) DataInputStream: Its an interface, Which defines methods for reading primitives from an InputStream.
boolean readBoolean()
byte      readByte()
..........................//all primitives char, float, int,long, double

3) OutStream Class: Its an abstract class it declare some methods for writing bytes, closing streams, flushing.

Methods of the OutputStream Class:

close()   // close this stream and release resource associated to this stream.
flush()   // flush the output stream and forces and buffered output bytes to written out.
write(byte[] b)  // write from b array to output stream.
write(byte[]b, int offset, int length)
write(int b);

 4) DataOutputStream: Same like DataInputStream
void writeBoolean(boolean b);

### Character Stream:
5) ReaderStream:Its like the InputStream class  only difference is that it read characters
close()
read()......

Sub-Classes are:
BufferedReader  : reading from input stream
FileReader : reading from file
InputStreamReader : Its a bridge from byte stream to character stream. it reads bytes and decodes them into characters.

6) WriterClass: Its an abstract class like Output stream
close()
flush();

Writer sub-classes:
bufferedWriter
FileWriter
OutputStreamWriter
PrintWriter

### Files:

7) File Class:
Constructors :
                      File(String dirPath)
                      File(String dirPath, String filename)
                      File(File dirObj, String filename)
File f1 = new File("/");

File Class:
canRead();
canWrite();
createNewFile();
delete();
..
8) RandomAccessFile:
seek(long newpos)   // After seek() new read /write operation occur from newpos.
getFilePointer()  //       return the position of next /write

9) FileOutputStream:
10)BufferedInputStream
11)PrintStream
12) FileWriter
13) FileReader
14) BufferedReader
15) BufferedWriter
16) PrintWriter
17) Scanner Class

boolean hasNext()
boolean hasNextBoolean()  ....// for int, float...
String next()
int nextInt() ...................// for int, float...


18) Serialization : Serialization is a process of writing object to a byte stream. Serialization also needed in RMI(Remote Method Invocation) which is use to invoke a method on different machine  sending machine serialize the object and receiving machine de-serialize  the object.
Serialization is just a marker that class can be serialize and all sub-classes of serialize class also serialize. Variables Static ans transient are not saved during serialization

a) ObjectOutput: extends DataOutput and support object serialization
void writeObject(Object object)   /// to serialize a object

b) ObjectOutputStream: extends OutputStream, its responsible to writing object  on stream.
void writeObject(Object obj); // write object to storage or stream

c)ObjectInput: extends DataInput interface
Object readObject()

Collections in Java

Collections in java is framework that provide an architecture to store and manipulate group of objects.

1) Iterator Interface:
a) hasNext()
b) next();
c) remove(); // remove last returned element.

2) ListIterator  Interface  // ListIterator extends Iterator, it allow to traverse  in either direction.
a) add(Object obj);
b) hasNext();
c) hasPrevious();
d) next();
e) previous();
f) remove();
g) set(Object obj ); // set last returned element  next/ previous


3) RandomAccess Interface // dummy or empty interface or a marker

interface RandamAccess
{}

A Class implements only List interface provides sequential access but if a class also implements RandamAccess then it provide randam access.

4) Compatrator Interface :

int compare (Object o1, Object o2) ;// o1 > o2  then positive value


5) Collection Interface : it declare fundamental mehods because all the collection implements  collection frameworks.

boolean add ( object obj);
void clear(); //remove all the elements
boolean contains (object obj); //return true  if collection contains obj
boolean equals (object obj);
boolean isEmpty();
Iterator iterator();
boolean remove (object obj);
int size ();   //return number of elements
Object[] toArray();  // return a array which contain all the elements of cllection
String toString()  // return all the elements of collection in string enclosed between [] and separated by comma.

6) List Interface : List interface extends collection interface and in List we can add/remove   elements by index with zero based index and can have duplicate elements.

add(int index , object elements); //no element is removed  post elements are shifted up.
get(int index)
indexOf(object element)
listIterator(0
remove(int index)
set(int index, object element) //replace index element with new element.

7) Set Interface: it extends collection interface and does not provide any extra method and it not allows duplicate elements.


8) SortedSet: it extend the set and provide a behavior of sorted in ascending order.
object first()  // first element of set or smallest element
object last()   // largest element

###Collection Classes:
9) ArrayList Class:
Constructor: ArrayList() // create a array with initial capacity of ten
                     ArrayList(Collection a);  //create a list using a collection object
                     ArrayList(int capacity)
Methods:
                    void ensureCapacity(int cap);
                     void trimToSize()  // reduce the size of the array as large as the number of elements.

public static void main(String[] arg){

ArrayList a = new ArrayList();     //its a generic type  but we can restrict type of elements
System.out.println("size of ArrayList " + a.size());
System.out.println("size of ArrayList " + a.size());
a.add(11);
a.add("A");
a.add('a');
a.add(7.77);
a.add(2,'N');
System.out.println("size of ArrayList " + a.size());
System.out.println("elements  of ArrayList " + a);

}

public static void main(String[] arg){

ArrayList <String> a = new ArrayList<String>();
System.out.println("size of ArrayList " + a.size());
System.out.println("size of ArrayList " + a.size());
a.add(11);   //error ArrayList can store Strings
a.add("A");
a.add('a');       //error ArrayList can store Strings
a.add(7.77);    //error ArrayList can store Strings
a.add(2,'N');     //error ArrayList can store Strings
System.out.println("size of ArrayList " + a.size());
System.out.println("elements  of ArrayList " + a);

}

## Display elements of an ArrayList using Iterator
 Iterator it =  a.iterator();
while(it.hasNext())


## Display using array
Object a[] = a.toArray();
for (int i =0 ; i < a.length ; i++)


## for-each loop
for(String str : a);             // for(Object obj : a)

9) LinkedList Class: Implements List interface
Constructor:  LinkedList()
                      LinkedList(Collection c);


Methods:
               void addFirst(object obj);
                Object getFirst()
                Object getLast()
                 Object removeFirst/Last()

10) HashSet: Class implements Set interface it create s collection that use hash table for storage. No specific  way of order of elements
Constructor: HashSet()      //load factor .75    and capacity with 16
                     HashSet(Collection c)     //load factor .75
                     HashSet(int capacity)     //load factor .75
                     HashSet(int capacity , float fillRatio) //




11) LinkedHashSet: extends HashSet, it does not implements any other methods but store elements in  inserted order.

12) TreeSet: it provide implementation of SortedSet interface.
Constructor: TreeSet()
                     TreeSet(Collection c)
                      TreeSet(Comparator c)

13) Map Interface : A map is an object which store value with respect to key. Some map may accepts null key and null values.

Methods:
clear();
containKey(Object Key) // Return true if map have that key.
containValue(Obect Value)
entrySet()  //Return set that contain the entries in a map.
keySet()  // Return a set that contain the keys
get(Object key) // Return a value at that value
isEmpty() //true if map dont have key-value mapping
put(Object key, Object key)
remove(Object key)
size()  // Returns the number of key-value mappings in a map
values() // Returns a collection view of the values contained in this map.


14) SortedMap: extends Map and ensure  that the entries are in ascending order.
firstKey() // return first key
lastKey()

15) Map.Entry:
getKey()  // return a  key for that entry
getValue()



###Map Class
16) HashMap Class: use hash table to implement the Map Interface.
Constructor: HashMap()     //empty HashMap with default initial capacity 16 with .75 load factor.
                     HashMap(int  capacity)   //
                     HashMap(ini capacity, load factor)
                     HashMap(Map m);


17) LinkedHashMap Class: Extend the HashMap Class

18) TreeMap Class:  Implements ShortedMap interface by using tree.

Constructor: TreeMap();
                      TreeMap(Comparator c);
                      TreeMap(Map m);

### The Legacy Classes and Interface : all classes are synchronized but none of the collection classes is synchronized but we can make synchronize using synchronized block.

19) The Enumeration Interface:
hasMoreElements();
nextElement() // return the next element of this enumeration

20) Vector Class: Implements dynamic array, it is similar to ArrayList() with two difference  a) Vector is synchronize and contain legacy methods.

Constructor: Vector()   // data array with capacity 10;
                      Vector( Collection c)
                       Vector( capacity)
                         Vector(int capacity , int capacityIncriment)

Methods:
addElements(Object obj)  //add to the end of  this vector and increase size by one.
capacity()          // Return the current capacity of this Vector
copyInto(Object[] anArray) // copies the entries into specified  index.
elementAt(int index)           // return element at this index
elements()  // return an enumeration of this vector
ensureCapacity( int minCapacity)
indexOf(Object element)  
insertElementAt(Object obj, int index)
isEmpty();
removeAllElements() //remove all and set to size to zero
removeElement(Object obj)   // remove first element
removeElementAt(int index)
size();
toArray()  //Return an array containing all elements in this array
toString()  //Return  a string repersentation of this vector
trimToSize() //capacity is equal to number of elements.

21) Stack Class: LIFO stack
boolean empty();
Object peek();
Object pop();
push(Object obj);

22) Dictionary Class: Its a abstract class operates much like a Map.
Enumeration elements() // Return an enumeration of values in this dictionary
get(Object key)
isEmpty()
keys()
put(Object key, Object values)
remove(Object key)  // key and corresponding value
size();

23) HashTable Class: Its like a HashMap but its synchronize .
Constructor:
   Hashtable()            // capacity 11 and load factor .75
    HashMap(int  capacity)   //
    HashMap(ini capacity, load factor)
     HashMap(Map m);

Methods:
clear();
containsKey();
containsValue(Object values)
elements()
entrySet()
get(Object key)
isEmpty();
keys();
keySet()
put(Object key, Object values);
remove (object key)
size()
toString();
values()   //Return a Collection view


24) Properties Class: Its sub-Class of Hashtable. maintain a list of values in which keys and values both are string

Methods: along with Hashtable methods
String getProperty(String key) // Return value
String getProperty(String key, String default) // If key is not present then it send default value.
Enumeration propertyNames();   // Enumeration of all the keys
Object  setProperty(String key, String values);

Generics in Java

Create a generic Class Demo:

class Demo <T>
{
void method(T obj)    //method can take any type of data type by default it is object.
{}
}

public static void main (String [] arg)
{
Demo demo = new Demo();    //T is a object.
demo.method("string");
demo.method(10);
}

Demo <String> demo1 = new Demo<String>();
Demo <Integer> demo2 = new Demo<Integer>();
Generics works only with objects, so we cannot use for primitive data types.
Demo <int> obj3 = new Demo<int>(); // Its illegal

One generic type is not compatible with another version of the same generic type.
demo1 = demo2 //will give error because both have different type compatible.

Multi-Threaded

A thread is a single flow of control in a program.
We can create a new thread in our program : a) Extend Thread Class  b) Implement Runnable Interface.

Thread Class: It have several methods to manage threads.
   get/setName()
   get/setPriority();
   isAlive();
   join();
   run();
   sleep();
  start() // It change the threads state to Runnable, The JVM calls the run() method.
  yield() // Pause currently executing thread  and allow to execute another thread.
   currentThread();

Runnable Interface : it have run method.

Creating Thread: a) Implementing Runnable: Easiest way to create thread is create a class that implements Runnable interface. then class only need to implement run() method. run() method like a any other method  but difference is run establish the entry point of a thread and thread will end when run return. Then create a object of Thread class.
  Thread(Runnable threadobj);
   Thread(Runnable threadobj, String threadname);

After the new thread created it will start using start() method. and it will put into ready queue and start execution from run() method.

  class thread  implements Runnable
{
     public void run()
       {
System.out.println("Inside thread method");
         }
}

public class test {

                        public static void main(String[] arg){

                           thread  pl = new thread();
                          Thread  threadobj = new Thread(pl);

                            threadobj.start();
                           System.out.println(threadobj.getName());
 
                                   }
                          }

b)Create thread class Extending Thread Class: Second way to create thread is extend Thread class and create a instance of that class.

class Mythread extends Thread
{        public void run ()
           {
            System.out.println("Inside in run method");
            }
}

class threaddemo {

public static void main(String [] args)
       {  Mythread obj = new Mythread();
                 obj.start();  
}
}

Main Thread should exit at end means before main thread exits all child threads should exit. This we can achive using sleep in main but its not a good way So that we can get using join() and isAlive() method.

join the thread obj then

obj.join();
or other way is
while(obj.isAlive());

Thread Priorities : Thread.MIN_PRIORITY AND Thread.MAX_PORIORITY(vary form 1  to 10 , default is 5).

Synchronization: resource that a single thread can access at a time. we can synchronize our code using synchronized methods or synchronized statement.

synchronize method:

synchronized void method()
{}
then only one thread can call method() at same time on the same instance. until one thread doesn't finish  no other thread(based on same instance) can enter into synchronized method.

synchronize statement:
if we are using exiting class then we cant make method synchronize. then using synchronize statement  we can get desire result.
synchronized (obj)
{ obj.method();
}

so method for class object 'obj' is synchronize .
static synchronized method is lock at class level or for non-static method lock at object level. because static method have single definition for all objects of a class.

suspend() thread need resume() method.
for wait() notify() needed.

if we stop a thread then thread will dead.
Once a thread is stopped it cannot be restarted.

if we suspend a thread and that thread have a locks on some critical data structure then it will not release lock and if some other threads are waiting for that resource then it will be dead lock .

resume method also  cannot be used without suspend method.