Coding Recipies

Stack Reversal

Problem Statement:
In-place stack reversal using recursion.

Fig: In-place Stack Reversal

Source Code
Solution:
Using recursion start from the bottom most element in the stack using the 1st Function Call(reverse()) , push each element to the bottom of the stack through recursion using another function call(pushToBottom()).

Below is the implementation.

/**
 *  Inplace reversal of Stack
 * @author Prateek
 */
public class ReverseStackRecursion {
 /**
  * Subroutine to Reverse the element of stack 
  * @param stack : input stack
  */
 public void reverseStack(Stack<Integer> stack){
  if(stack.isEmpty())
   return ;

  int val= stack.pop();
  reverseStack(stack);

  pushToBottom(stack,val);
  return ;
 }

 /**
  * Pushes the incoming element or item to the bottom of the stack 
  */
 private void pushToBottom(Stack<Integer> stack,int item){
  if(stack.isEmpty()){
   stack.push(item);
   return ;
  }

  int val= stack.pop();
  pushToBottom(stack,item);
  stack.push(val);
 }
}

Happy Coding !! :)

Sort Stack

Problem Statement:

Recursive In-place Stack Sorting.

Fig: Sort given Stack in O(1)

Source Code

Solution:

In this problem we will empty the stack and hold in values in the function call Stack. Then each element from the Function Call Stack is picked and compared with the given stack elements, which again is handled by another nested Function Call Stack. No extra space is used in sorting the stack.

Sort() Subroutine empties the stack

Below is the implementation:

/**
 * Recursive Inplace Stack Sorting 
 * @author Prateek
 */
public class SortStack {
 //input stack
 private Stack<Integer> stack; 
 
 public SortStack(Stack<Integer> stack) {
 this.stack=stack;
 }
 
 /**
  * Sorting Subroutine 
  */
 public void sort(){
  if(stack.isEmpty())
   return;
  
  int item=stack.pop();
  sort();
  compareAndPush(item);
 }
 
 /**
  * Pushing each element of stack by recursion
  * @param item: each item of stack which is compared and pushed to stack
  */
 public void compareAndPush(int item){
  if(stack.isEmpty() || item <= stack.peek())
   stack.push(item);
  else {
   int val=stack.pop();
   compareAndPush(item);
   stack.push(val);
  }
 }
}

Please comment and post suggestions if any.
Happy Coding !! :)

Stack & Queues: Stack using Queues

Problem Statement:
Implement Stack using two Queues.

Fig: Stack And Queue

Source Code LINK
Solution:
We will be using two queues for achieving efficiency instead of one.
The code that we will be implementing will have pop operation with some over head compared to push.
Assume we two queues Q1 and Q2.

Push : enqueue item to Q1

Pop: dequeue all the element from Q1 and and enqueue them to Q2 except the last element, Flip the name of the queues and return the element of Q1.

Below is the implementation of PUSH and POP operations:

/**
	 * Push operation of Stack
	 * Item pushed into Queue1
	 */
	@Override
	public void push(Integer item) {
		System.out.println("Push : "+item);
		queue1.offer(item);
	}

	/**
	 * Pop operation of Stack
	 * last item of queue1 is returned, 
	 * order is reversed using queue2
	 */
	@Override
	public Integer pop() {
		Integer item=null;
		if(!queue1.isEmpty())
		{
			while (!queue1.isEmpty()) 
			{
				 item=queue1.poll();
				if(!queue1.isEmpty())
					queue2.add(item);
			}
			flip();
		}
		else
			System.out.println("Stack is Empty");
		System.out.println("Poped : "+ item);
		return item;
	}

The PEEK operation will be similar to POP operation, but all the items of Q1 will be pushed to Q2 , and names will be swapped.

/**
	 * Peek operation, similar to pop , 
	 * with slight modification
	 */
	@Override
	public Integer peek() {
		Integer item=null;
		while (!queue1.isEmpty()) {
			 item=queue1.poll();
				queue2.add(item);
		}
		flip();
		System.out.println("Peek : "+ item);
		return item;
	}

Other implementations is given below

         @Override
	public boolean isEmpty() {
		return queue1.isEmpty();
	}

	/**
	 * Flipping of Queues
	 */
	public void flip(){
		Queue<Integer> tQueue=  queue1;
		queue1=queue2;
		queue2 = tQueue;
	}

Please post your suggestions if any.

References: Stackoverflow
Happy Coding!! :)

26 Jan 2014

Stack Reversal

Sort Stack

Stack & Queues: Stack using Queues