Moving elements from one stack to another

Suppose we have stack and want to move elements to another stack preserving element order, If we don't have any restrictions than it's very simple task, using temporary space we can achieve it with no extra effort.
Now let's solve this problem with restrictions, we are allowed to use only additional O(1) memory.  When I first stated this problem I thought that it was not solvable, but after few minutes of thinking I figured out simple algorithm.

Imagine that we already moved N-1 elements to new stack, they are ordered correctly and now we are going to move Nth element. We can do it in this way:

1. Pop Nth element from initial stack and save it in temporary variable
2. Move N-1 elements from destination stack to initial stack one by one.
3. Push the element saved in 1st step in destination stack.
4. Move N-1 elements from initial stack to destination stack -  those are elements which were moved in 2nd step.

And we got it, we have moved N elements in destination stack. Now we can use this approach to move all the elements and we'll be happy.

Here is the implementation of this algorithm:

    static public void main(String[] args) {
        Stack stack = new Stack();
        for (int i = 0; i < 31; i++) {
            stack.add(i);
        }
        Stack stack2 = new Stack();

        while (!stack.isEmpty()) {
            int temp = stack.pop();
            int counter = 0;
            while (!stack2.isEmpty()) {
                stack.push(stack2.pop());
                counter++;
            }
            stack2.push(temp);

            while (counter < 0) {
                stack2.push(stack.pop());
                counter--;
            }
        }


        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop() + " ");
        }


    }

The algorithm which I proposed is useful only in situations when there is strict memory restrictions,  because time complexity has grown and it is O(N^2).

Soft, Weak and Phantom references in Java

All object instances in Java are allocated on the heap and can only be accessed through object references. When we are creating object we are storing references for accessing objects in future

Object o = new Object();

Here “o” is strong reference,   beside this type of reference Java also has other types of references which  are implemented in java.lang.ref package, from Java 1.2   In this package we have three reference-object classes: Weak Reference, Phantom Reference and  Soft Reference.

Weak References:

Weak reference is a reference which doesn't have enough force to prevent Garbage Collector(GC) deleting object.  This type of references are useful when we are implementing caching functionality. Suppose we have cache of images and different threads of system are using it, when system no more needs some images, GC will not be able to delete object because cache has strong reference to it and object will stay in memory forever.  To  prevent such situations we can refer objects in cache with weak references  and  GC will delete it as soon as it detects its weakly reachability.

You can create weak reference like this:

WeakReference weakImage = new WeakReference(image);

And for accessing Image object you can use  weakImage.get()  which returns actual object, But It also can return null which means that there are no strong references to this object.

Another Way for creating WeakReference is:

ReferenceQueue q = new ReferenceQueue();

WeakReference weakImage = new WeakReference(image, q);

ReferenceQueue class gives us flexibility for tracking references,  When WeakReference starts returning null it means that object is garbage and reference will be added to the queue, which you can use for further cleanup.

Soft Reference:

Soft Reference behaves like weak references, except  when GC determines object is softly reachable, then it may clear this object or not. But we can be guaranteed that this object will be cleared before virtual machine throws OutOfMemoryError .  This mean that softly reachable objects will stay in memory until memory occupied be them is not critical and we have enough memory for creating other objects.

Phantom Reference:

Phantom references are different from soft and weak references,  it's get() method always returns null. The only use of this reference is to track when object is enqueued. But why we need it if we already have other references?

Let's introduce such class:

 public class SoftRef {  
   static SoftRef ref = null;  
   String t;  
   public SoftRef(String t) {  
     this.t = t;  
   }  
   static public void main(String[] args) {  
     SoftRef obj = new SoftRef("test Obj");  
     obj = null;  
     System.gc();  
   }  
   @Override  
   protected void finalize() throws Throwable {  
     super.finalize();  
     ref = this;  
     System.out.println("deleted");  
   }  
 }  

This class has weird finalize method, it is resurrecting itself – creating strong reference to itself therefore GC will not delete it.   Java Language Specification clams that finalize() method will be invoked maximum once, so it guarantee that object can't resurrect always.

In this case WeakReferences will be enqueued before object is really deleted and reference will become dead beside object stay alive.   Here  PhantomReferences can help,  Phantom references are enqueued when objects are deleted from memory and get() method always returns null to prevent resurrecting object.  So  phantom references are good for determining exactly when object is deleted from memory.