Queue data structure using Array in Java

Posted By: Java Examples - 3:52 PM
A queue is a linear list of elements in which deletions can take place only at one end, called the front of the stack, and insertion can take place only at the other end, called the rear. The term FRONT and REAR are used in describing a linear list only when it is implanted as queue. Queues are also called First in First out (FIFO) Lists. This makes the queue a First-In-First-Out (FIFO) data structure. 
In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once an element is added, all elements that were added before have to be removed before the new element can be invoked.

Generic Type in Java

Posted By: Java Examples - 10:16 PM
The term generics here means parameterized types. Parameterized types are important because they enable you to create
classes, interfaces, and methods in which the type of data upon which they operate is specified as a parameter. 
Using
generics, it is possible to create a single class, for example, that automatically works with different types of data. A class,
interface, or method that operates on a parameterized type is called generic, as in generic class or generic method.

Convert infix to postfix using stack in Java

Posted By: Java Examples - 9:14 PM

Infix Expression :

Any expression in the standard form like "2*3-4/5" is an Infix(Inorder) expression.

Postfix Expression :

The Postfix(Postorder) form of the above expression is "23*45/-".

Example : 

  • infix (1+2)*(3+4)
    • with parentheses: ((1+2)*(3+4))
    • in postfix: 12+34+*
    • in prefix: *+12+34
  • infix 1^2*3-4+5/6/(7+8)
    • paren.: ((((1^2)*3)-4)+((5/6)/(7+8)))
    • in postfix: 12^3*4-56/78+/+
    • in prefix: +-*^1234//56+78
  • Scan the Infix string from left to right.
  • Initialise an empty stack.
  • If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character tostack.
  • If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack(topStack). If topStack has higher precedence over the scanned character Popthe stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.
  • (After all characters are scanned, we have to add any character that the stackmay have to the Postfix string.) If stack is not empty add topStack to Postfix stringand Pop the stack. Repeat this step as long as stack is not empty.
  • Return the Postfix string.

Infix to Postfix Conversion : 

In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is abc*+. 
The algorithm for the conversion is as follows :
Repeat this step till all the characters are scanned.


Java version of infix to postfix  is given bellow :

/**
 * To change this template, choose Tools | Templates and open the template in
 * the editor.
 */
package stack;

import java.util.Scanner;

/**
 *
 * @author ACHCHUTHAN
 */
public class Infix2Postfix extends Stack {

    public Infix2Postfix(int x) {
        super(x);
    }

    /**
     *@return postfixString value
     */
   
    public String InToPost(String infixString) {
        String postfixString = " ";

        for (int index = 0; index < infixString.length(); ++index) {
            char chValue = infixString.charAt(index);
            if (chValue == '(') {
                push('(');
            } else if (chValue == ')') {
                Character oper = peek();
                while (!(oper.equals('(')) && !(isEmpty())) {
                    postfixString += oper.charValue();
                    pop();
                    oper = peek();
                }
                pop();
            } else if (chValue == '+' || chValue == '-') {
                //Stack is empty
                if (isEmpty()) {
                    push(chValue);
                    //current Stack is not empty
                } else {
                    Character oper = peek();
                    while (!(isEmpty() || oper.equals(new Character('(')) || oper.equals(new Character(')')))) {
                        pop();
                        postfixString += oper.charValue();
                    }
                    push(chValue);
                }
            } else if (chValue == '*' || chValue == '/') {
                if (isEmpty()) {
                    push(chValue);
                } else {
                    Character oper = peek();
                    while (!oper.equals(new Character('+')) && !oper.equals(new Character('-')) && !isEmpty()) {
                        pop();
                        postfixString += oper.charValue();
                    }
                    push(chValue);
                }
            } else {
                postfixString += chValue;
            }
        }
        while (!isEmpty()) {
            Character oper = peek();
            if (!oper.equals(new Character('('))) {
                pop();
                postfixString += oper.charValue();
            }
        }
        return postfixString;
    }

    public static void main(String[] args) {
        Infix2Postfix mystack = new Infix2Postfix(10);
        System.out.println("Type in an expression like (1+2)*(3+4)/(12-5)\n "
                + "with no monadic operators like in-5 or +5 followed by key");
        Scanner scan = new Scanner(System.in);
        String str = scan.next();
        System.out.println("The Expression you have typed in infix form :\n"+str);
        System.out.println("The Equivalent Postfix Expression is :\n"+mystack.InToPost(str));
    }
}
Output of this program :

run:
Type in an expression like (1+2)*(3+4)/(12-5)
 with no monadic operators like in-5 or +5 followed by <ENTER>key
(1+2)*(3+4)
The Expression you have typed in infix form :
(1+2)*(3+4)
The Equivalent Postfix Expression is :
 12+34+*
BUILD SUCCESSFUL (total time: 28 seconds)

Convert Decimal to octal using stack in java

Posted By: Java Examples - 1:04 PM
You all are aware of Stacks. It performs two basic operations push and pop. The push operation adds an element to the top of the list, or initializing the stack if it is empty and the pop operation removes an item from the top of the list. Using these operations, we have converted a decimal number into Octal.
  • Divide the decimal number by 8
  • Treat the division as an integer division. Write down the remainder (in Octal).
  • Divide the result again by 8.
  • Treat the division as an integer division. Repeat step 2 and 3 until result is 0.
  • The Oct value is the digit sequence of the remainders from the last to first.

Convert Decimal to Hexadecimal using stack in java

Posted By: Java Examples - 12:46 PM
You all are aware of Stacks. It performs two basic operations push and pop. The push operation adds an element to the top of the list, or initializing the stack if it is empty and the pop operation removes an item from the top of the list. Using these operations, we have converted a decimal number into Hexadecimal .
  • Divide the decimal number by 16
  •  Treat the division as an integer division. Write down the remainder (in hexadecimal). 
  • Divide the result again by 16. 
  •  Treat the division as an integer division. Repeat step 2 and 3 until result is 0. 
  • The hex value is the digit sequence of the remainders from the last to first.

From National Identity Card(NIC) print date of birth in java

Posted By: Java Examples - 11:09 AM
The following numbering system is followed in order to assign this number:
  • Digits 1 and 2: The year of birth
  • Digits 3-5: The number of the day in the year on which the person's birth date falls.
    • A male would be assigned the number 1-366 and a female the number 501-866. This is a way of confirming if the person's listed birth date is accurate. A male's birth date would be represented by the exact number of days, a female's birth date would be represented by the exact number of days + 500.
      •    Example: The first five digits of the NIC for a male born on 1 January 1997   would be 97001; however, a female born on that same date would be 97501.

Read values from a file and Sort the numbers using merge sort and quick sort algorithm in Java

Posted By: Java Examples - 9:34 PM

Merge sort algorithm

1. The length of the list is 0 or 1, and then it is considered as sorted.
2. Otherwise, divide the unsorted list into 2 lists each about half the size.
3. Sort each sub list recursively. Implement the step 2 until the two sub lists are sorted.
4. As a final step, combine (merge) both the lists back into one sorted list. 

FileReader -Java Read File Line by Line in Java

Posted By: Java Examples - 7:56 PM
The FileReader class makes it possible to read the contents of a file as a stream of characters. It works much like the FileInputStream except the FileInputStream reads bytes, whereas the FileReader reads characters. The FileReader is intended to read text, in other words. One character may correspond to one or more bytes depending on the character encoding scheme.

An Array of Linear list in java

Posted By: Java Examples - 8:48 PM
Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including stacks, queues, associative arrays, andsymbolic expressions, though it is not uncommon to implement the other data structures directly without using a list as the basis of implementation. 

Operation and interface on linear list in java

Posted By: Java Examples - 8:32 PM
Operations :
  1. isEmpty() - Returns true if the List is empty ,false other wise.
  2. size() - Give the number of element in the list.
  3. get(theIndex) - Give the element with gives index.
  4. indexOf(theElement) - Determines the index of a given element.
  5. remove(theIndex) - Removes element with a given index and returns it.
  6. add(theIndex,theElement) - Add a given element so that new element has a specified index. 

The n-queens problem in Java

Posted By: Java Examples - 10:38 PM
A classic combinatorial problem is to place n queens on an n × n chess board so that no queen threatens any other queen, that is, so that no two queens are on the same row, column, or diagonal. In order to reduce this solution space, it can now be assumed without loss of generality, that the ith queen is placed in the ith row, thereby avoiding those two queens can be in the same row. 

Knapsack Problem in Java

Posted By: Java Examples - 1:16 PM
Knapsack problem :
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.

Maximum and Minimum using Divide and Conquer in Java

Posted By: Java Examples - 10:00 PM
Divide-and-Conquer Min-Max
As we are dealing with sub problems, we state each sub problem as computing minimum and maximum of a sub array A[p . . q]. Initially, p = 1 and q = A.length, but these values change as we recursive  through sub problems.To compute minimum and maximum of A[p . . q]: Divide by splitting into two sub arrays A[p . .r] and A[r+1 . . q], where r is the halfway point of A[p . . q]. Conquer by recursively computing minimum and maximum of the two sub arrays A[p . .r] and A[r+1 . . q]. Combine by computing the overall minimum as the min of the two recursively computed minimum, similar for the overall maximum.

Recursive Binary Search in java

Posted By: Java Examples - 3:16 PM
Algorithm :
  •  Algorithm is quite simple. It can be done either recursively or iteratively: 
  •  get the middle element; 
  • if the middle element equals to the searched value, the algorithm stops; otherwise, two cases are possible: 
    • searched value is less, than the middle element. 
    • In this case, go to the step 1 for the part of the array, before middle element. searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.

QuickSort in java using divide and conquer algorithm

Posted By: Java Examples - 1:40 PM

Algorithm :


Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

The steps are:

  1. Pick an element, called a pivot, from the list.

Calculate age in java

Posted By: Java Examples - 8:13 PM
Here, you can calculate the age of a person easily through the given program. This program takes your complete date of birth (year, month and day of month) and gives you the exact age which determines the years, months and days of the calculated age of the person. Following program is fully validated. Because of this you can not enter any invalid year or month or day for your date of birth.

Convert decimal to binary using Stacks in Java

Posted By: Java Examples - 2:08 PM
How to convert decimal into binary using stacks. You all are aware of Stacks. It performs two basic operations push and pop. The push operation adds an element to the top of the list, or initializing the stack if it is empty and the pop operation removes an item from the top of the list. Using these operations, we have converted a decimal number into binary.

Mergesort in Java using divide and conquer

Posted By: Java Examples - 1:28 PM

Merge sort is a divide and conquer algorithm. The sorting elements are stored in a collection. This collection is divided into two collections and these are again sorted via mergesort. Once the two collections are sorted then the result is combined .Merge sort will take the middle of the collection and takes then the two collection for the next iteration of mergesort. In the merging part mergesort runs through the both collections and selects the lowest of the both to insert it into a new collection.In comparison to quicksort the divide part is simple in mergesort while the merging take is complex. In addition quicksort can work "inline", e.g. it does not have to create a copy of the collection while mergesort requires a copy.

Binary search in array in java using divide and conquer

Posted By: Java Examples - 10:04 PM

Let LIST be a list of elements that are sorted in non-decreasing order. Consider the problem of determining whether a given element x is present in the list. If x is present, we return the value j for which LIST[j]=x. If it is not in the list just return -1. The search begins by comparing x w ith the element in the middle of the list. If x equals this element, the search terminates. If x is smaller than this element, then we need only search the left half. If x is bigger than the middle element, only the right half needs to be searched
            

Stack Data Structure in Java

Posted By: Java Examples - 9:14 PM

Stack data structure :

A stack is a limited version of an array.  New elements or nodes as they are often Called, can be added to a stack and removed from a stack only from one end.  For this reason, a stack is referred to as a LIFO structure (Last-In First-Out).

Operations :

The main primitive operations of a stack are:
Push : adds a new node
Pop : removes a node



Stack (Last-In First-Out)

Additional primitives can be defined:
IsEmpty : reports whether the stack is empty
Peek : return the last element in the stack

Stack Implementation in java :

Consider a stack class stores data in an array (static structure). The array reference type is Object[] which means that it can contain any kind of Java object.

The java interface is:
public interface Stack  {
public boolean isEmpty();
public Object pop();
public Object peek();
public void push(Object TheElement);

}

Java version of the  Stack data structure  is given below: 


Output:

Contents of Stack :
1 | 2 | 3 | 4 | 5 | 
Remove the top of stack element : 5
Return the top stack element : 4
Contents of Stack :
1 | 2 | 3 | 4 | 

Copyright © 2016 Java Examples ACHCHUTHAN.ORG. Designed by Templateism .