Stack Data Structure:

A stack is a basic data structure or abstract data type or collection. This
data type allows operations of PUSH and POP.

PUSH: Insert elements into the data structure.

POP: Remove elements from the data structure.

PIP: Displaying the elements of the stack.

PUSH and POP are major operations performed in this data
structure. These operations are performed only at one end of the stack that is
known as top of the stack. This means Stack follows LIFO (Last In First Out)
order and this data structure called as LIFO data structure.  Last element removed first and last element
added at the top of the stack. 

This concept can be illustrated by thinking of your data set as a stack of
plates or books where you can only take the top item off the stack in order to
remove things from it. This structure is used all throughout programming.





If a stack is full and does not contain enough space to accept an element to
be pushed then the stack is considered as over flow state. Stack may be
implemented with a bounded capacity over flow state occurs.



If stack is empty it goes to under flow state, this means that the stack has
no elements to be popped.



Efficiency of Stack: In the stack, the elements can be push or pop one at a
time in constant O(1) time. That is, the time is not dependent on how many
items are in the stack and is therefore very quick.

No comparisons or moves are
necessary.





Java Methods for Stack data structure:





Java provides these methods in Util package. if you want to write a program
in java to implement Stack must import the java.util package.

1.     
boolean empty() – It returns the boolean value if the
stack is empty it return true, otherwise false.

2.     
push(element) – Put the element into the stack.

3.     
pop() – Removes the elements from the stack.

4.     
peek() – It returns the top element of stack.

5.     
int search(element) - Searches for element in the
stack. If found, its offset from the top of the stack is returned. Otherwise,
.1 is returned.

Program for Stack Implementation in Java:



import java.util.*;

public class JavaStackExample {
    public static void main(String args[]){
        Stack st = new Stack();
        System.out.println("Check the status of the stack empty  T/F  --->"+st.isEmpty());
       
        st.push("Hi");
        st.push("java");
        st.push("world");
       
        System.out.println("All elements in the stack"+st);
        st.pop(); // It remove first element of the stack."hi" is removed
        System.out.println("After POP All elements in the stack"+st);
        System.out.println("Element to be searched at    "+st.search("hi"));
        System.out.println("First Element in the Stack:"+st.peek());
    }

}



Program Compilation:



D:>javaprograms>javac JavaStackExample.java



D:>javaprograms>java JavaStackExample









output of the above program:


Check the status of the stack empty  T/F  --->true
All elements in the stack[Hi, java, world]
After POP All elements in the stack[Hi, java]
Element to be searched  at   -1
First Element in the Stack:java

IP address representation:

In this blog I will discuss about What is IP address and how to represent it.

Generally IP address is represented in 32-bit format. In
expansion of IP is Internet protocol address.

Dot (.) is the decimal and this notation is used to
represent as number format data into string of decimal each is separated by a
dot operator.  Technically this
representation is noted as synonym of dotted notation. Or quad dotted notation,
specifically used to represent IP addresses. 

 An internet protocol
address has 32-bits. 

See the below example

          

These are separated by dot and the
bits divided into 4 octets that are in decimal numbers ranging from 0 to 255
and concatenate together by place dot between them.

There are two types of IP Protocols implemented
on systems today are IPv4 and IPv6. IPv4 is the 4^th version majority
of the systems worldwide support this. New version is IPv6 it improves the
limitations of IPv4. The gap in version sequence between IPv4 and IPv6
resulted from the assignment of number 5 to the experimental Internet Stream Protocol in 1979, which
however was never referred to as IPv5.

Systems can identify by using their
IP address only.   

For example consider
the IP address 172.16.254.1

Convert these individual values into
binary first

172 – 10101100

16 – 00010000

254 – 1111110

1 – 00000001

These are all can be represented in
the form of 8 –bit

Each individual called as octet or
byte or 8-bit. These are 4 so 4*8 = 32 so it is in 32 bit format.

Using binary arithmetic, it's easy to calculate the highest number that
a byte can represent. If you turn on all the bits in a byte (11111111)
and then convert that byte to a decimal number 

(128 + 64 + 32 + 16 + 8 +
4 + 2 + 1), those bits total 255.

Bubble sort also known as Sinking sort, it is a simple sort
algorithm that repeatedly steps through the list to be sorted, compares each
pair of adjacent items and swaps them if they are in the wrong order. The pass
through the list is repeated until no swaps are needed, which indicates that
the list is sorted.  First this algorithm
is named as comparison sort later it is bubble
sort.

Algorithm for Bubble sort:

for
i = 1:n,

    swapped = false

    for j = n:i+1,

        if a[j] < a[j-1],

            swap a[j,j-1]

            swapped = true

    → invariant: a[1..i] in final position

    break if not swapped

end

In
the case of nearly sorted data, bubble sort takes O(n) time, but requires at
least 2 passes through the data (whereas insertion sort requires something more
like 1 pass).

Bubble
sort has worst-case and average complexity both O(n²),
where n is the number of items being sorted. There exist many sorting
algorithms with substantially better worst-case or average complexity of O(n log n).
Even other О(n²) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore, bubble
sort is not a practical sorting algorithm when n is large.

Pseudo
code:

  procedure bubbleSort( A : list of sortable items )

   n = length(A)

   repeat

     swapped = false

     for i = 1 to n-1 inclusive do

       /* if this pair is out of order */

       if A[i-1] > A[i] then

         /* swap them and remember something changed */

         swap( A[i-1], A[i] )

         swapped = true

       end if

     end for

   until not swapped

end procedure



Time complexity of Bubble sort: O(n)

Average Performance: O(n²)

Worst case Performance: O(n²)

Best case performance: O(n)

Worst Case Space complexity: O(n) total, O(1) auxiliary.

Example for Bubble sort:

Let us take the array of numbers
"5 1 4 2 8", and sort the array from lowest number to greatest number
using bubble sort. In each step, elements written in bold are being
compared. Three passes will be required.

First Pass

( 5 1 4 2 8 ) → {\displaystyle \to } (
1 5 4 2 8 ), Here, algorithm compares the first two elements, and
swaps since 5 > 1.

( 1 5 4 2 8 ) →
{\displaystyle \to } (
1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) →
{\displaystyle \to } (
1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) →
{\displaystyle \to } (
1 4 2 5 8 ), Now, since these elements are already in order (8
> 5), algorithm does not swap them.

Second Pass

( 1 4 2 5 8 ) → {\displaystyle \to } (
1 4 2 5 8 )

( 1 4 2 5 8 ) →
{\displaystyle \to } (
1 2 4 5 8 ), Swap since 4 > 2

( 1 2 4 5 8 ) →
{\displaystyle \to } (
1 2 4 5 8 )

( 1 2 4 5 8 ) →
{\displaystyle \to } (
1 2 4 5 8 )

Now, the array is already sorted, but the algorithm does not know if it is
completed. The algorithm needs one whole pass without any swap to
know it is sorted.

Third Pass

( 1 2 4 5 8 ) → {\displaystyle \to } (
1 2 4 5 8 )

( 1 2 4 5 8 ) →
{\displaystyle \to } (
1 2 4 5 8 )

( 1 2 4 5 8 ) →
{\displaystyle \to } (
1 2 4 5 8 )

( 1 2 4 5 8 ) → {\displaystyle
\to } (
1 2 4 5 8 )

Program for Bubble sort:

import java.util.Scanner;



class BubbleSort {

  public static void main(String []args) {

    int n, c, d, swap;

    Scanner in = new Scanner(System.in);



    System.out.println("Input number of integers to sort");

    n = in.nextInt();



    int array[] = new int[n];



    System.out.println("Enter " + n + " integers");



    for (c = 0; c < n; c++)

      array[c] = in.nextInt();



    for (c = 0; c < ( n - 1 ); c++) {

      for (d = 0; d < n - c - 1; d++) {

        if (array[d] > array[d+1])

        {

          swap       = array[d];

          array[d]   = array[d+1];

          array[d+1] = swap;

        }

      }

    }



    System.out.println("Sorted list of numbers");



    for (c = 0; c < n; c++)

      System.out.println(array[c]);

  }

}

Output of the Program: