Coding Recipies

Two Stacks

Problem Statement:
Implement two stacks in an array.

Fig: Two Stack implementation

Source Code
Solution:

For implementing two stacks in an array efficiently we will take two TOP pointers which grow from opposite sides of the array.

PUSH , POP , PEEK takes the "StackNumber" argument which decides on which stack operation is to be performed.

 
 /**
  * Push Operation
  * @param stackNum 0: 1st stack  , 1: 2nd stack
  * @param data : data to be pushed
  * @throws InterruptedException 
  */
 public void push(int stackNum, int data) throws InterruptedException{
  Thread.sleep(10);
  if(stackNum==1){
   pushToStack1(data);
  }
  else if(stackNum==2)
   pushToStack2(data);
  else
   System.out.println("Invalid Stack Number");
 }
 
 public int pop(int stackNum) throws InterruptedException{
  Thread.sleep(10);
  if(stackNum==1)
   return popFromStack1();
  else if (stackNum==2)
   return popFromStack2();
  else{
   System.err.println("Invalid Stack");
   return -1;
  }
 }
 
 public int peek(int stackNum) throws InterruptedException{
  Thread.sleep(10);
  if(stackNum==1)
   return peekFromStack1();
  else if (stackNum==2)
   return peekFromStack2();
  else{
   System.err.println("Invalid Stack");
   return -1;
  }
 }

Please comment and post your suggestions.
Happy Coding!!:)

Three Stacks

Problem Statement:
Implement three stacks in a single array.

Fig: Implement three stacks in a given array

Source Code
Solution:
The concept is to divide the given array into three parts and using auxiliary space to store status of "Top" pointer of each stack.

Push and Pop operation accepts an extra argument , which specifies on which stack the operation is to be performed.

Below is the implementation of PUSH, POP and PEEK subroutines.

 private int stackSize=5;
 private int[] tops={-1,-1,-1};
 private int[] arr=new int[stackSize * 3];

 /**
  * Push operation
  * @param stackNum : specifies the stack number
  * @return: insertion status
  * @throws InterruptedException 
  */
 public boolean push(int stackNum, int item) throws InterruptedException{
  int index= stackNum * stackSize + tops[stackNum] + 1;
  if(tops[stackNum] < stackSize -1 ){
   tops[stackNum]++;
   arr[index]=item;
   Thread.sleep(10);
 System.out.println(Arrays.toString(arr));
   return true;
  }
  else{
   System.err.println("Stack Full");
   return false;
  }
 } 

 /**
  * Pop operation
  * @param stackNum: specifies the stack number
  * @return the poped item
  * @throws InterruptedException 
  */
 public int pop(int stackNum) throws InterruptedException{

  if(tops[stackNum]==-1)  {
   System.err.println("Stack is Empty");
   return -1;
  }
  int index= stackNum * stackSize + tops[stackNum];
  tops[stackNum]--;
  int item= arr[index];
  arr[index]=0;
  Thread.sleep(10);
  System.out.println(Arrays.toString(arr));
  return item;
 }

 /**
  * Peek operation
  * @param stackNum: specifies the stack number
  * @return top element of the specified stack
  */
 public int peek(int stackNum){
  if(tops[stackNum]==-1)  {
   System.out.println("Stack is Empty");
   return -1;
  }

  int index= stackNum * stackSize + tops[stackNum];
  return arr[index];
 }

Happy Coding !! :)

Queue with two Stacks

Problem Statement:
Implement Queue using two stacks.

Fig: Queue using two stacks

Source Code Link
Solution:

I expect you are aware of operations that ADTs(Abstract Data Types) Queue and Stack supports. All we have to do is implement Enqueue and Dequeue opertions using operations of a Stack, i.e. push, pop , peek , isEmpty and size.

1st Approach(inefficient):
Suppose we have two stacks say S1 and S2 , we use S1 to push elements , when en-queue operation of queue is called, and when de-queue is called we pop everything out of S1 and push to S2, and pop the top element from S2, and again push everything to S1 by popping out from S2.

Summarizing:
Enqueue Operation:
push to S1

Dequeue Operation:
1. Pop everything from S1 and push to S2.
2. Pop top element of S2 when S1 gets empty.
3. Push everything back to S1 from S2.

Here clearly our Dequeue operation is costly , and there lies one more approach by which we can improve on this.

2nd Approach: (Efficient)
This approach is slight modification to the above logic in order to achieve efficiency in the "dequeue"operation.
In the above approach we are unnecessarily pushing elements from S2 to S1 , i.e. Step 3 of Dequeue operation as shown above. The trick is to pick the top element of S2 if its not empty , if it is then push everything from S1 to S2 and return top element of S2.

Summary :
Enqueue Operation:
1. push to S1

Dequeue Operation:
1. If S2 is not Empty
- pop top element of S2
2. If S2 is empty
- push everything from S1 to S2 and pop top element of S2.

The link to the code is given above please refer to it.

Please post your comments and suggestions.
Happy Coding !!:)

26 Jan 2014

Two Stacks

Three Stacks

Queue with two Stacks