Wednesday, February 18, 2015

Stack Implementaion in Java Using Integer Array

This is my first post on stack data structure. In this post I am sharing my code of a simple Stack of integers which is internally implemented using integer array.

Stack

A stack is a basic data structure that can be logically thought as linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack. The basic 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. 

                           Data stack.svg



Sections in this post: 
  1. Basic stack operations. 
    • Push and Pop
    • peek
    • is Full and is Empty
  2. My Stack Interface.
  3. Array Based Implementation.

Basic stack Operations:

 

Push and Pop

 

A stack has two fundamental operations - Push and Pop.
The Push operation stores something on the top of the stack and the Pop operation retrives something from the top of the stack. 

Peek

 

Peek operation  returns top element from the stack without removing it from the stack. Peek is not a fundamental stack operation but it is usually implemented in stack ADT.

Is Empty and Is Full 


When stack is empty and pop operation is called then stack should throw "Stack underflow error" and if stack is already full and pop operation is called then we should throw "Stack overflow error".

So as to avoid these two errors we implement Is Empty and Is Full methods. Similar to peek, "Is Empty" and "Is Full" are also not fundamental stack operation.

My Stack Interface 

I am creating Stack interface for my Stack ADT. Lets see the code:

public interface StackInterface {
 
  //Method to push data onto stack
  
 public boolean push(int data);
 
  //Method to pop topmost element from stack or most recently added element in stack
  
 public Integer pop();
 
  // This is not a basic stack operation
  // This method should allow a user to see the top most element in stack
  // it is similar to popping and pushing element again.
  
 public Integer peek();
 
  //method should return true if stack is empty else false
  
 public boolean isEmpty();
 
  //Method should return true if stack is full else false

 public boolean isFull();
}

Array Based Implementation

 In an array-based implementation we maintain the following fields:
  1.  an array A of a default size (≥ 1),
  2. the variable top that refers to the top element in the stack and
  3.  the capacity that refers to the array size. 
We say that a stack is empty when top = -1, and the stack is full when top = capacity-1. The variable top changes from -1 to capacity - 1.
              
                                               

Below is my code for implementing integer stack using array:

public class StackUsingIntArray implements StackInterface {
    // Every stack has a maximum capacity i.e. number of objects it can hold.
     private static final int CAPACITY = 10;
 
    //Top will always point to most recently added element in stack therefore
    //top * -1 implies stack is empty
  
    private int top = -1;
    // array to hold stack elemnts.lt is initialized to capacity of stack 
     private int[] stackArray = new int[CAPACITY];        
        
 @Override
 public boolean push(int data) {
  
    //Check if stack is fullIf it is full then we show Stack overflow message
   
     if (isFull()) {
         System.out.println("Stack overflow");
         return false;
     } else {
         stackArray[++top] = data;
         return true;
     }
 }

 @Override
 public Integer pop() {
  
   //Check if stack is empty If it is empty then we show Stack underflow message
   
  if (isEmpty()) {
     System.out.println("Stack underflow");
  } else {
   
    //decrementing top by one to make second element from top as top
   
     top--;

    //we will be returning top+1 value from array as we have already
    //made top to point second element in stack
    
     return (Integer) stackArray[top + 1];

  }
  return null;
 }

 @Override
 public Integer peek() {
     // we implement peek by first popping top element then pushing it back
      Integer element = null;
      if (!isEmpty()) {
         element = pop();
         push(element);
      }
       return element;
 } 
        
 @Override
 public boolean isEmpty() {
     return top == -1;
 }

 @Override
 public boolean isFull() {  
     return top == CAPACITY-1;
 }
        

  //This method just gives view of the stack. As there are only two operation
  //for stack i.e. push and pop so in theory we can never print a stack
  //without calling those two methods
  
 public void printStack() {
     System.out.print("[");
     for (int i = top; i >= 0; i--) {
        System.out.print(" " + stackArray[i]);
     }
     System.out.print(" ]");
 }
        
 public static void main(String[] args) {
  StackUsingIntArray stack = new StackUsingIntArray();
  stack.pop();
  stack.push(40);
  stack.pop();
  stack.push(50);
  stack.pop();
  stack.push(50);
  stack.push(11);
  stack.pop();
  stack.push(50);
  stack.push(32);
  stack.pop();
  stack.pop();
  stack.push(55);
  stack.pop();
  stack.push(68);
  stack.pop();
  stack.push(75);
  stack.push(-12);
  stack.printStack();
  System.out.println();
  System.out.println("=============================");
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  stack.push(1);
  stack.push(2);
  stack.push(3);
  stack.push(4);
  stack.push(5);
  stack.printStack();
 }
}


If we run the program we will get output like this:

Output
================================================================================
Stack underflow
[    -12    75    50    ]
====================
-12
75
50
Stack underflow
null
Stack underflow
null
Stack underflow
null
Stack underflow
null
[    5    4    3    2    1    ]

Please share your comments if you find anything incorrect, or you want to share more information about the topic discussed above.
 
For further reading:

Stack implementation using link list 
Stack implementation by link list node, 
Stack implementation using doubly link list 
Stack implementation by doubly link list node . 
For complete listing see data structure and algorithm page

 



Monday, February 16, 2015

Data structure Questions on Link List


In my previous posts we talked about single link list, doubly link list. In this post I am sharing my code solution for few practice question which are also frequently asked in interviews too.

Get Nth node value from end of link list

Given a Linked List and a number n, we need to write a method  that returns the value at the nth node from end of the Linked List.

Solution: We maintain two references say First and Second. First we move First to n nodes from head.After that we move both references one by one until First reaches end. Now Second will point to nth node from the end.
Lets see in the code now:
public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4);

  myProg.myList.insertAtStart(new Node(11));
  myProg.myList.insertAtStart(new Node(12));
  myProg.myList.insertAtStart(new Node(13));
  myProg.myList.insertAtStart(new Node(14));
  myProg.myList.printList(myProg.myList.getHead());
  System.out.println("Nth element form last is: "+myProg.getNthFromLast(5));
      }

      public Integer getNthFromLast(int n) {
  // Check if list is already Empty
  if (myList.isEmpty()) {
   System.out.println("List is empty returning null;");
   return null;
  }
  Node firstNode, secondNode;
  firstNode = secondNode = myList.getHead();
  for (int i = 0; i < n; i++) {
   firstNode = firstNode.getNext();
   if (firstNode == null) {
    System.out.println("invalid number given returning null");
    return null;
   }
  }
  while (firstNode != null) {
   firstNode = firstNode.getNext();
   secondNode = secondNode.getNext();
  }
  return secondNode.getData();
 }
}

If we run the program we will get output like this:

Output
========================================================================
List is: [    14    13    12    11    4    3    2    1    54    55    53    56    51    52    44    45    43    11    42    ]
Nth element form last is: 44

 

Print middle node value 

We traverse linked list using two pointers. Moving one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.

Lets see the code now:
public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4);

  myProg.myList.insertAtStart(new Node(11));
  myProg.myList.insertAtStart(new Node(12));
  myProg.myList.insertAtStart(new Node(13));
  myProg.myList.insertAtStart(new Node(14));
  myProg.myList.printList(myProg.myList.getHead());
                myProg.printMiddle();
      }

      /* method to get the middle of the linked list */
 public void printMiddle() {
 /*
 * We will Traverse linked list using two reference namely fastRef and
 * slowRef Move one first by one and other by two.When the fast ref
 * reaches end slow ref will reach middle of the linked listCheck if
 * list is already Empty
 */

      if (myList.isEmpty()) {
          System.out.println("List is empty");
      }
      Node fastRef, slowRef;
      fastRef = slowRef = myList.getHead();
      while (fastRef != null && fastRef.getNext() != null) {
         fastRef = fastRef.getNext().getNext();
  slowRef = slowRef.getNext();
     }
     System.out.println("Middle node is: " + slowRef.getData()); 
   }
}

If we run the program we will get output like this:

Output
========================================================================
List is: [    14    13    12    11    4    3    2    1    54    55    53    56    51    52    44    45    43    11    42    ]
Middle node is: 55

 

Get number of occurrence of a number in link list 

We are require to find how many time a number is present in the list.

Lets see the code now:
public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4);

  myProg.myList.insertAtStart(new Node(11));
  myProg.myList.insertAtStart(new Node(12));
  myProg.myList.insertAtStart(new Node(13));
  myProg.myList.insertAtStart(new Node(14));
  myProg.myList.printList(myProg.myList.getHead());
                System.out.println("occurrence is: "+myProg.getOccurrence(11));
      }

        /*
  * Counts the no. of occurrences of a node (search_for) in a linked list
  * (head)
  */
 Integer getOccurrence(int numTosearchFor) {
  // Check if list is already Empty
  if (myList.isEmpty()) {
   System.out.println("List is empty returning null;");
   return null;
  }
  Node currentNode = myList.getHead();
  int count = 0;
  while (currentNode != null) {
   if (currentNode.getData() == numTosearchFor) {
    count++;
   }
   currentNode = currentNode.getNext();
  }
  return count;
 }
}

If we run the program we will get output like this:

Output
========================================================================
List is: [    14    13    12    11    4    3    2    1    54    55    53    56    51    52    44    45    43    11    42    ]
occurrence is: 2

Floyd's Cycle-Finding Algorithm

Floyd's cycle-finding algorithm, also called the "tortoise and the hare algorithm" is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds.
 
                                              

Traverse linked list using two pointers.  Move one pointer by one and other pointer by two.  If these pointers meet at some node then there is a loop.  If pointers do not meet then linked list doesn’t have loop.

Lets see the code now:
public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4); 

               /*
               * Adding two nodes to make a cycle
               */ 
               Node nodeForLoop1 = new Node(22);
        Node nodeForLoop2 = new Node(23);
        nodeForLoop2.setNext(nodeForLoop1); 
                
        myProg.myList.insertAtEnd(nodeForLoop1);
  myProg.myList.insertAtEnd(nodeForLoop2);
      }

      /* Floyd's Cycle-Finding Algorithm */
 public boolean detectloop() {
  /*
   * The fastest way to detect the loop is to use Floyd's Cycle-Finding
   * Algorithm Move one pointer by one and other pointer by two. If these
   * pointers meet at some node then there is a loop. If pointers do not
   * meet then linked list doesn't have loop.
   */

  // Check if list is already Empty
  if (myList.isEmpty()) {
   System.out.println("List is empty returning false:");
   return false;
  }
  Node fastRef, slowRef;
  fastRef = slowRef = myList.getHead();
  while (fastRef != null && fastRef.getNext() != null) {   
   fastRef = fastRef.getNext().getNext();
   slowRef = slowRef.getNext();   
   if (slowRef == fastRef) {
                                //Below method will print node where cycle is present
    getLoopStart(slowRef, fastRef);
    return true;
   }
  }
  return false;
 }

 private void getLoopStart(Node slowRef, Node fastRef) {
  /*
   * Move slowRef to Head. Keep fastRef at Meeting Point. Each are k steps
   * /* from the Loop Start. If they move at the same pace, they must *
   * meet at Loop Start.
   */
  slowRef = myList.getHead();
  while (slowRef != fastRef) {
   slowRef = slowRef.getNext();
   fastRef = fastRef.getNext();
  }
  // Now n2 points to the start of the loop.
  System.out.println("loop at: " + fastRef.getData());
 }
}

If we run the program we will get output like this:

Output
============================================================================
loop at: 22
Is loop present: true

 

Richard Brent's Cycle-Finding Algorithm

In 1980, Brent invented an algorithm that not only worked in linear time, but required less stepping than Floyd's Tortoise and the Hare algorithm (however it is slightly more complex). 

Brent's algorithm features a moving rabbit and a stationary, then teleporting, turtle. Both turtle and rabbit start at the top of the list. The rabbit takes one step per iteration. If it is then at the same position as the stationary turtle, there is obviously a loop. If it reaches the end of the list, there is no loop.
Of course, this by itself will take infinite time if there is a loop. So every once in a while, we teleport the turtle to the rabbit's position, and let the rabbit continue moving. We start out waiting just 2 steps before teleportation, and we double that each time we move the turtle.
Why move the turtle at all? Well, the loop might not include the entire list; if a rabbit gets stuck in a loop further down, without the turtle, it will go forever. Why take twice as long each time? Eventually, the length of time between teleportations will become longer than the size of the loop, and the turtle will be there waiting for the rabbit when it gets back.
Note that like Floyd's Tortoise and Hare algorithm, this one runs in O(N). However you're doing less stepping than with Floyd's (in fact the upper bound for steps is the number you would do with Floyd's algorithm). According to Brent's research, his algorithm is 24-36% faster on average for implicit linked list algorithms.

                               

Lets see the code now:
public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4);

  myProg.myList.insertAtStart(new Node(11));
  myProg.myList.insertAtStart(new Node(12));
  myProg.myList.insertAtStart(new Node(13));
  myProg.myList.insertAtStart(new Node(14));
  myProg.myList.printList(myProg.myList.getHead());
                System.out.println(myProg.hasLLoop(myProg.myList.getHead()));
      }

     /*
  * Richard Brent's algo: Richard Brent described an alternative cycle
  * detection algorithm,which is pretty much like the hare and the tortoise
  * [Floyd’s cycle] except the slow node here doesn't move, but is later
  * " teleported" to the position of fast node at fixed intervals
  */
 public boolean hasLLoop(Node root) {
  if (root == null) {
   return false;
  }
  Node slow = root, fast = root;
  int taken = 0, limit = 2;
  while (slow.getNext() != null && fast.getNext() != null) {
   fast = fast.getNext();
   taken++;
   if (slow == fast) {
    return true;
   }

   if (taken == limit) {
    taken = 0;

    limit <<= 1; // equivalent to limit *= 2
    slow = fast; // teleporting the turtle to the hare's position
   }
  }
  return false;
 }
}

If we run the program we will get output like this:

Output
============================================================================
true

Please share your comments if you find anything incorrect, or you want to share more information about the topic discussed above.

I will keep adding more Question here :)