FIFO based Queue implementation in Java

We know we have java.util.Stack as a data structure in Java. It has standard functions like pop(), push(), peek(). But  ever wondered what is analog for Queue in Java?

If you search for Queue class in java then you will wind such an interface java.util package.

public interface Queue<E> extends Collection<E>

And if you check classes implementing this interface you will find LinkedList in it. Yes LinkedList in java can be used for FIFO operations.  Actually LinkedList implements Deque which inturn implements Queue. If you see functions in Queue interface they are as follows -

1. element(): This method retrieves the head of the queue.
2. offer(E o): This inserts the specified element into the queue.
3. peek(): This method retrieves the head of this queue, returning null if this queue is empty.
4. poll(): This method retrieves and removes the head of this queue, or return null if this queue is empty.
5. remove(): This method retrieves and removes the head of this queue.

 Lets understand this better with a code -

Code -

import java.util.LinkedList;
import java.util.Queue;

public class FIFOTest {
    
    public static void main(String args[]){
        
        Queue<String> myQueue = new LinkedList<String>();
        myQueue.add("US");
        myQueue.add("Russia");
        myQueue.add("India");
        myQueue.offer("Canada");
        
        for(String element : myQueue){
            System.out.println("Element : " + element);
        }
        
        System.out.println("Queue : " + myQueue);
        System.out.println(myQueue.peek());
        System.out.println("After peek : " + myQueue);
        System.out.println(myQueue.poll());
        System.out.println("After poll : " + myQueue);
        System.out.println(myQueue.remove());
        System.out.println("After remove : " + myQueue);
            
    }
}

Output - 

Element : US
Element : Russia
Element : India
Element : Canada
Queue : [US, Russia, India, Canada]
US
After peek : [US, Russia, India, Canada]
US
After poll : [Russia, India, Canada]
Russia
After remove : [India, Canada]

Note : From usability point of view add() and offer() do the same thing. Same goes for poll() and remove().

Basic operations with Bitwise operators

Not a Java question as such but a more generic information that would be useful. Most of the interview questions consist of manipulations of bitwise operators. Some basic operations are listed below -

• OR can be used to set a bit to one: 11101010 OR 00000100 = 11101110
• AND can be used to set a bit to zero: 11101010 AND 11111101 = 11101000
• AND together with zero-testing can be used to determine if a bit is set:

11101010 AND 00000001 = 00000000 = 0

11101010 AND 00000010 = 00000010 ≠ 0

• XOR can be used to invert or toggle a bit:

11101010 XOR 00000100 = 11101110

11101110 XOR 00000100 = 11101010

• NOT can be used to invert all bits.

NOT 10110010 = 01001101

Find GCD of two numbers in Java?

Code :

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 6/12/13
 * Time: 4:46 PM
 * To change this template use File | Settings | File Templates.
 */
public class GCDFinder {

    public static int gcd(int a,int b){
        int temp = a % b;
        if(temp == 0)
            return b;
        else
            return gcd(b,temp);
        }

    public static void main(String args[]){
        System.out.println("GCD of 12 and 10 is : " + gcd(12,10));
    }
}

Output :

GCD of 12 and 10 is : 2

Note : You can calculate LCM as Number1*Number2/GCD

Find nth Fibonacci number in Java?

Fibonacci series is as follows

1 1 2 3 5 8 13 21 34...

You can read more about this sequence in Wiki.

Again for this we can have iterative approach as well as recursive. Recursive code is provided below

Recursive Code :

 /**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 6/12/13
 * Time: 3:25 PM
 * To change this template use File | Settings | File Templates.
 */
public class FibonacciFinder {

    public static int fibonacci(int number){

        if(number <= 2){
            return 1;
        }
        else{
            return  fibonacci(number - 1) + fibonacci(number - 2);
        }
    }

    public static void main(String args[]){

        System.out.println("8th fibonacci number is : " + fibonacci(8));


    }

}

Output :

8th fibonacci number is : 21

Iterative Code :

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 6/12/13
 * Time: 3:25 PM
 * To change this template use File | Settings | File Templates.
 */
public class FibonacciFinder {
    int prev = 1;
    int curr = 1;
    public int fibonacci(int number){

        if(number < 2){
            return curr;
        }
        else {
            int temp;
            for(int i = 0;i<number-2;i++){
                temp = curr;
                curr = curr + prev;
                prev = temp;
            }
            return curr;
        }
    }

    public static void main(String args[]){

        System.out.println("8th fibonacci number is : " + (new FibonacciFinder()).fibonacci(8));
    }

}

Output:

8th fibonacci number is : 21

 

Find Power of a number in Java?

There are two ways to find power of a number. One is iterative which is very simple(Just multiply the number power number of times) and other is recursive. Following is the code to get power of a number in recursive way.

Code : 

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 6/12/13
 * Time: 3:08 PM
 * To change this template use File | Settings | File Templates.
 */
public class PowerCalculator {

    public static int pow(int base, int power){

        if(power == 1){
            return base;
        }
        if(power % 2 == 0){
            return pow(base, power/2) * pow(base, power/2);
        }
        else {
            return pow(base, power/2) * pow(base, power/2) + base;
        }
    }

    public static void main(String args []){

        System.out.println("4 raise to 2 : " + PowerCalculator.pow(4,2));

    }

}

Output :

4 raise to 2 : 16