Implementing Queue in Java

 
Queue is a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first to be removed. Suppose if a queue contains 4 elements and 5th element added at back and if we need to remove that element then we need to remove all front 4 elements first. As like Stack implementation in java we can implement Queue Data Structure and also we have operations in Queue like enqueue(), dequeue(), front(), isempty() etc.,
Implementing Queue in Java

enqueue() - Insert element in front of the Queue.

dequeue() - Return front element and remove same element from the Queue.

front() - Same as dequeue() returns front element but same element won't be removed from the Queue.

clean() - cleans the Queue.



Lets see simple example to implement Queue using ArrayList and using Generics for holding any datatype.



import java.util.ArrayList;
import java.util.List;

public class MyQueue <E>{

 private List<E> list = null;
 
 public MyQueue() {
  list = new ArrayList<E>();
 }

 public void enqueue(E val){
  list.add(val);
 }
 
 public E dequeue(){
  E val = null;
  if(list.size() > 0){
   val = list.get(0);
   list.remove(0);
  }  
  return val;
 }
 
 public boolean isEmpty(){
  if(list.size() == 0)return true;
  else return false;
 }
 
 public int size(){
  return list.size();
 }
 
 public E front(){
  E val = null;
  if(list.size() > 0){
   val = list.get(0);
  }  
  return val;
 }
 
 public void clean(){
  list = new ArrayList<E>();
 }
 
 @Override
 public String toString() {
  return list.toString();
 }
}


Our Queue class is ready and we can test with below code.


public class TestMyQueue {

 public static void main(String[] args) {
  
  MyQueue<String> queue = new MyQueue<String>();
  
  int qSize = queue.size();
  System.out.println("QUEUE SIZE : "+qSize);
  
  //ENQUEUE
  queue.enqueue("one");
  queue.enqueue("two");
  queue.enqueue("three");
  queue.enqueue("four");
  queue.enqueue("five");
  System.out.println("5 ELEMENTS ADDED IN QUEUE");
  qSize = queue.size();
  System.out.println("QUEUE SIZE : "+qSize);
  
  //QUEUE
  System.out.println("QUEUE      : "+queue);
  
  //FRONT
  System.out.println("FRONT       : "+queue.front());
  
  //DEQUEUE
  System.out.println("DEQUEUE        : "+queue.dequeue());
    
  qSize = queue.size();
  System.out.println("QUEUE SIZE : "+qSize);
  
  //FRONT
  System.out.println("FRONT       : "+queue.front());
  
  //ISEMPTY
  System.out.println("EMPTY      : "+queue.isEmpty());
  
  //CLEAN
  queue.clean();
  System.out.println("QUEUE CLEANED");
  
  //ISEMPTY
  System.out.println("EMPTY      : "+queue.isEmpty());
  
 }
}


OUTPUT:


QUEUE SIZE     : 0
5 ELEMENTS ADDED IN QUEUE
QUEUE SIZE     : 5
QUEUE             : [one, two, three, four, five]
FRONT             : one
DEQUEUE         : one
QUEUE SIZE      : 4
FRONT             : two
EMPTY             : false
QUEUE CLEANED
EMPTY             : true






Implement Stack in Java

 
In our earlier tutorial we have seen how to use default Stack class in Java and their methods like push, pop, peek etc., Suppose in any of the interview if interviewer asked us to implement our own Stack class which holds any type of data like Integer, String or even other datatypes. Then we need to go with Generics and need to implement our Stack class.

Lets see simple example to implement Stack using ArrayList and using Generics for holding any datatype.


import java.util.ArrayList;

public class MyStack <E> {

 ArrayList<E> list = null;
 
 public MyStack() {
  list = new ArrayList<E>();
 }
 
 public E push(E val){
  list.add(val);
  return val;
 }
 
 public E pop(){
  E val = list.get(list.size()-1);
  list.remove(list.size()-1);
  return val;
 }
 
 public E peek(){
  E val = list.get(list.size()-1);
  return val;
 }

 public int size(){
  return list.size();
 }
 
 public int search(E val){
  int id = -1;
  if(list.contains(val)){
   id = list.indexOf(val);
  }
  return id;
 }
 
 public boolean empty(){
  if(list.size() == 0) return true;
  else return false;
 }
 
 @Override
 public String toString() {
  return list.toString();
 }
}


Our Stack class is ready and we can test with below code.


public class TestMyStack {

 public static void main(String[] args) {
  
  MyStack<Integer> stack = new MyStack<Integer>();
  
  int stkSize = stack.size();
  System.out.println("STACK SIZE : "+stkSize);
  
  //PUSH
  stack.push(11);
  stack.push(21);
  stack.push(31);
  stack.push(41);
  stack.push(51);
  
  stkSize = stack.size();
  System.out.println("STACK SIZE : "+stkSize);
  
  //STACK
  System.out.println("STACK      : "+stack);
  
  //PEEK
  System.out.println("PEEK       : "+stack.peek());
  
  //POP
  System.out.println("POP        : "+stack.pop());
  
  
  stkSize = stack.size();
  System.out.println("STACK SIZE : "+stkSize);
  
  //PEEK
  System.out.println("PEEK       : "+stack.peek());
  
  //EMPTY
  System.out.println("EMPTY      : "+stack.empty());
  
  //SEARCH
  System.out.println("SEARCH     : "+stack.search(21));
  
  //SEARCH
  System.out.println("SEARCH     : "+stack.search(700));
 }
}


OUTPUT:


STACK SIZE : 0
STACK SIZE : 5
STACK        : [11, 21, 31, 41, 51]
PEEK          : 51
POP            : 51
STACK SIZE : 4
PEEK          : 41
EMPTY        : false
SEARCH      : 1
SEARCH      : -1



Stack class in java

 
Basically Stack represents last-in-first-out (LIFO) ordering of objects. In Java Stack extends Vector and defines its own five methods along with default methods which allow a vector to be treated as a stack and those methods are
Stack class in java

push()
- Pushes the element or object into the stack and it returns the same element. 

pop()
- Removes the first element from the stack and it returns the same element. 
empty()

- Checks whether the stack is empty or not. Returns true if stack is empty else false.

peek()
- Similar to pop(), return first element from the stack but it won't remove the element. 

search()
- Searches for the element from the stack and returns the offset of the element if found else returns -1. 

Lets see simple example in java how to use Stack class.


import java.util.Stack;

public class StackTest {

 public static void main(String[] args) {
  
  Stack<Integer> stack = new Stack<Integer>();
  
  int stkSize = stack.size();
  System.out.println("STACK SIZE : "+stkSize);
  
  //PUSH
  stack.push(11);
  stack.push(21);
  stack.push(31);
  stack.push(41);
  stack.push(51);
  
  stkSize = stack.size();
  System.out.println("STACK SIZE : "+stkSize);
  
  //STACK
  System.out.println("STACK      : "+stack);
  
  //PEEK
  System.out.println("PEEK       : "+stack.peek());
  
  //POP
  System.out.println("POP        : "+stack.pop());
  
  
  stkSize = stack.size();
  System.out.println("STACK SIZE : "+stkSize);
  
  //PEEK
  System.out.println("PEEK       : "+stack.peek());
  
  //EMPTY
  System.out.println("EMPTY      : "+stack.empty());
  
  //SEARCH
  System.out.println("SEARCH     : "+stack.search(21));
  
  //SEARCH
  System.out.println("SEARCH     : "+stack.search(700));
 } 
}


OUTPUT:


STACK SIZE  : 0
STACK SIZE  : 5
STACK         : [11, 21, 31, 41, 51]
PEEK           : 51
POP            : 51
STACK SIZE : 4
PEEK          : 41
EMPTY        : false
SEARCH      : 3
SEARCH      : -1



Selection sort in Java

 
Selection sort is a combination of searching (search for smaller element) and sorting (Swap with first element) and move on. During each pass unsorted element with the smallest value will be swapped to its proper position. Number of times the loop passes through the array will be one less than the size of array (N-1 times). 
In selection sort we need to 2 loops as same as bubble sort, where here inner loop will find the smallest element and outer loop need to swap with the other element and need to place it in proper position. Now lets see simple Java code for selection sort.
Selection sort in Java


public class SelectionSort {

 public static void main(String[] args) {
  int array[] = {3,4,8,5,1,7,9,2,6};
  System.out.print("Array before sorting : ");
  printArray(array);
  
  selectionSort(array);
  
  System.out.print("Array after sorting : ");
  printArray(array);
 }

 public static void selectionSort(int[] values) {
  for (int i = values.length - 1; i > 0; i--) {
   int first = 0; 
   for (int j = 1; j <= i; j++) {
    if (values[j] > values[first])
     first = j;
   }
   int tmp = values[first]; 
   values[first] = values[i];
   values[i] = tmp;
  }
 }
 
 public static void printArray(int[] array) {
  for (int i : array) {
   System.out.print(i + ", ");
  }
  System.out.println();
 }
}



OUTPUT:


Array before sorting : 3, 4, 8, 5, 1, 7, 9, 2, 6, 
Array after sorting : 1, 2, 3, 4, 5, 6, 7, 8, 9, 



Encoding and Decoding

Base64 encoding is an algorithm which uses 64 printable characters to replace each character from original data in an algorithmic sequence, so that as same we can decode these data. In most of the places we need to Encode or even need to Encrypt most sensitive data when we transfer to other network. Encoding is not encryption. In all our below programs we use Base64 to encode a string that scrambles the output and it may appear to be unreadable binary data. But it can be easily decoded if some have knowledge on encoding algorithms. Most often encoding a string will end with "=" symbol. Apart from encoding there are lot of advanced encryption algorithms like MD5, RSA-SHA etc., which are all not easy to break it.
In java we have got function to encode and decode strings. Lets see simple example for encoding and decoding using sun.misc package classes,


public class EncodeDecodeTest {

 public static void main(String[] args) {

  String str = "Java Discover & Questions $$$";
  System.out.println("Input   : "+str);
  try{
   str = new sun.misc.BASE64Encoder().encode(str.getBytes("UTF8"));
   System.out.println("Encoded : "+str);
   
   str = new String((new sun.misc.BASE64Decoder().decodeBuffer(str)), "UTF8");
   System.out.println("Decoded : "+str);
  
  }catch (IOException e) {
   e.printStackTrace();
  }
 }
}


OUTPUT:


Input   : Java Discover & Questions $$$
Encoded : SmF2YSBEaXNjb3ZlciAmIFF1ZXN0aW9ucyAkJCQ=
Decoded : Java Discover & Questions $$$


sun.misc classes are not guaranteed to be consistent across different versions of JRE. In those cases we can use 3rd part open source code or jars to encode our data. There are lot of other mechanism to encode and decode our sensitive data and few are,
  • Using Apache Commons Codec
  • Using Java Mail API (MIME Utility)
  • Using MiGBase64



Using Apache Commons Codec - Link to Download 


import org.apache.commons.codec.binary.Base64;

public class EncodeDecodeTest {

 public static void main(String[] args) {

  String str = "Java Discover & Questions $$$";
  System.out.println("Input   : "+str);
  
  str = new String(Base64.encodeBase64(str.getBytes()));
  System.out.println("Encoded : "+str);

  str = new String(Base64.decodeBase64(str.getBytes()));
  System.out.println("Decoded : "+str);     
 }
}

OUTPUT:


Input  : Java Discover & Questions $$$
Encoded : SmF2YSBEaXNjb3ZlciAmIFF1ZXN0aW9ucyAkJCQ=
Decoded : Java Discover & Questions $$$



Using Java Mail API (MIME Utility) - Link to Download


import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;

import javax.mail.MessagingException;
import javax.mail.internet.MimeUtility;


public class EncodeDecodeTest {

 public static void main(String[] args){

  String str = "Java Discover & Questions $$$";
  System.out.println("Input   : "+str);
  try{
   ByteArrayOutputStream byteAOS = new ByteArrayOutputStream();
   OutputStream outStream = MimeUtility.encode(byteAOS, "base64");
   outStream.write(str.getBytes());
   outStream.close();
   System.out.println("Encoded : " + byteAOS.toString());

   ByteArrayInputStream byteAIS = new ByteArrayInputStream(byteAOS.toByteArray());
   InputStream intStream = MimeUtility.decode(byteAIS, "base64");
   byte[] tmp = new byte[byteAOS.toByteArray().length];
   int length = intStream.read(tmp);
   byte[] decoded = new byte[length];
   System.arraycopy(tmp, 0, decoded, 0, length);
   System.out.println("Decoded : " + new String(decoded));
      
  }catch (MessagingException  e) {
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  }
 }
}

OUTPUT:


Input   : Java Discover & Questions $$$
Encoded : SmF2YSBEaXNjb3ZlciAmIFF1ZXN0aW9ucyAkJCQ=

Decoded : Java Discover & Questions $$$



Using MiGBase64 - Link to Download

MiGBase64 is a simple and small java class which is fast and effective encoding and decoding algorithm. 


public class EncodeDecodeTest {

 public static void main(String[] args){

  String str = "Java Discover & Questions $$$";
  System.out.println("Input   : "+str);

  str = Base64.encodeToString(str.getBytes(), true);
  System.out.println("Encoded : " + str);

  str = new String(Base64.decode(str.getBytes()));
  System.out.println("Decoded : " + new String(str));
 }
}

OUTPUT:


Input   : Java Discover & Questions $$$
Encoded : SmF2YSBEaXNjb3ZlciAmIFF1ZXN0aW9ucyAkJCQ=
Decoded : Java Discover & Questions $$$

Difference between ClassNotFoundException and NoClassDefFoundError

When we see in general both ClassNotFoundException and NoClassDefFoundError are errors which comes when JVM or Class Loader not able to find appropriate class while loading at run-time. ClassNotFoundException is a checked exception and NoClassDefFoundError is an Error which comes under unchecked. 
There are different types of Class Loader loads classes from difference sources, sometimes it may cause library JAR files missing or incorrect class-path which causes loader not able to load the class at run-time. Even though both names sounds similar to class file missing there are difference between ClassNotFoundException and NoClassDefFoundError.
Difference between ClassNotFoundException and NoClassDefFoundError

ClassNotFoundException:
ClassNotFoundException comes when we try to load class at run-time using Reflection and if those class files are missing then application or program thrown with ClassNotFoundException Exception. There is nothing to check at compile time since its load those class at run-time. Best example is when we try to load JDBC driver class using reflection and we fail to point driver jars. Then program thrown with ClassNotFoundException as like below example.



import java.sql.Connection;
import java.sql.DriverManager;

public class ExceptionTest {

 public static void main(String[] args) {
  Connection conn = createConnection();
 }

 public static Connection createConnection() {

  Connection conn = null;

  try {
   Class.forName("com.mysql.jdbc.Driver");
   System.out.println("MySQL JDBC Driver Registered!");
   conn = DriverManager.getConnection(
     "jdbc:mysql://192.168.1.2:3306/mydatabase", "root", "root");

  } catch (Exception e) {
   System.err.println("Please configure mysql driver file !!!");
   e.printStackTrace();
  }
  return conn;
 }
}


OUTPUT:


Please configure mysql driver file !!!
java.lang.ClassNotFoundException: com.mysql.jdbc.Driver
 at java.net.URLClassLoader$1.run(Unknown Source)


These are the different class loaders from difference classes like,
forName method in class Class.
loadClass method in class ClassLoader.
findSystemClass method in class ClassLoader.


NoClassDefFoundError:

NoClassDefFoundError is thrown when a class has been compiled with a specific class from the class path but if same class not available during run-time. Missing JAR files are the most basic reason to get NoClassDefFoundError. As per Java API docs "The searched-for class definition existed when the currently executing class was compiled, but the definition can no longer be found."


Lets see simple example to get NoClassDefFoundError Error.


public class SecondTestClass {

 public SecondTestClass(){
  System.out.println("Hello Java");
 }
}



public class ErrorTest {

 public static void main(String[] args) {
  new SecondTestClass();
 } 
}


NOTE:
Once you create both java files compile SecondTestClass.java and ErrorTest.java classes separately. Next delete the generated class file called SecondTestClass.class. Next try to run ErrorTest.class file which will thrown with NoClassDefFoundError error message.

OUTPUT:


Exception in thread "main" java.lang.NoClassDefFoundError: SecondTestClass
 at com.db.ErrorTest.main(ErrorTest.java:7)
Caused by: java.lang.ClassNotFoundException: SecondTestClass