Sunday, December 28, 2014

Implementing a queue using two stacks.

Q. Implement a MyQueue class which implements a queue using two stacks.

Algorithm:

1. There are two stacks stack1, stack2.
2. Suppose we are adding elements 1,3,4,5,2.
3. For adding them to the queue, we push them to stack 1.
4. For finding the min, we pop all of them to stack 2 and then pop form stack 2.
5. As long as there are elements in stack 2, finding min is easy, just pop from stack 2.
6. If stack 2 is empty and we need to find min, pop again all elements from stack 1 to stack 2 and pop from stack 2.

Source:

public class MyQueue<T>{
    Stack<T> stack1, stack2;
    int max;
    
    MyQueue(int size){
        max = size;
        stack1 = new Stack<>(size);
        stack2 = new Stack<>(size);
    }
    
    public int size(){
        return stack1.size() + stack2.size();
    }
    
    public void enqueue(T val){
        if(stack1.size() == max){
            if(stack2.isEmpty())shiftto2();
            else return;
        }
        stack1.push(val);
    }
    
    public T dequeue(){
        if(size() == 0)return null;
        if(stack2.isEmpty())shiftto2(); 
        return stack2.pop(); 
    }
    
    private void shiftto2(){
        while(!stack1.isEmpty())
            stack2.push(stack1.pop());
    }
    
    public T peek(){
        if(size() == 0)return null;
        if(stack2.isEmpty())shiftto2();
        return stack2.peek(); 
    } 
}

public class Code{
    public static void main(String[] args){
        MyQueue<Integer> mq = new MyQueue<>(5);
        for(int i=0;i<9;++i)mq.enqueue(i);
        System.out.println(mq.dequeue());
        for(int i=3;i<8;++i)mq.enqueue(i);
        for(int i=0;i<9;++i)System.out.println(mq.dequeue());
    }
}

Stack Class

public class Stack <T>{
    int top = -1; 
    T[] elements;
    
    public Stack(int size){  
        elements = (T[])new Object[size];  
    }
    
    public int size(){ 
        return top+1;
    }
    
    public void push(T element){ 
        if(top+1 == elements.length){
            System.out.println("Overflow.");
            return;
        }
        elements[++top] = element;
    }
    
    public T pop(){
        if(top<0){
            System.out.println("Underflow.");
            return null;
        }
        return elements[top--];
    }
        
    public T peek(){
        if(top < 0){
            System.out.println("Stack is empty!");
            return null;
        }
        return elements[top];
    }
    
    public boolean isEmpty(){
        return top==-1;
    } 
} 

Output:

0
1
2
3
4
5
6
7
8
3

No comments:

Post a Comment