Question

Java

[(1)] Design a Stack that is composed ONLY of one or two Queue objects ergo the ONLY instance variables that exist in this stack are queues.

Stack class should contain the following methods:

Print, Pop, Push, Top, Size, isEmpty, copy

[(2)] Design a Queue that is composed ONLY of two Stacks objects ergo the ONLY instance variables that exist in this queue are stacks.

Queue class should contain the following methods:

Print, Enqueue, Dequeue, Front, Rear, Size, isEmpty, Copy

COMMENT YOUR CODE, VERY IMPORTANT!!!

Answer 1

Here is code for stack implementation using two queues in java :

/* Java Program to implement a stack using
two queue */
import java.util.*;

class StackSolution {

    static class Stack {
        // Two inbuilt queues
        static Queue<Integer> q1 = new LinkedList<Integer>();
        static Queue<Integer> q2 = new LinkedList<Integer>();

        // To maintain current number of
        // elements
        static int curr_size;

        Stack()
        {
            curr_size = 0;
        }

        static void push(int x)
        {
            curr_size++;

            // Push x first in empty q2
            q2.add(x);

            // Push all the remaining
            // elements in q1 to q2.
            while (!q1.isEmpty()) {
                q2.add(q1.peek());
                q1.remove();
            }

            // swap the names of two queues
            Queue<Integer> q = q1;
            q1 = q2;
            q2 = q;
        }

        static void pop()
        {

            // if no elements are there in q1
            if (q1.isEmpty())
                return;
            q1.remove();
            curr_size--;
        }

        static int top()
        {
            if (q1.isEmpty())
                return -1;
            return q1.peek();
        }

        static int size()
        {
            return curr_size;
        }
        static boolean isEmpty(){
            if(curr_size==0)
                return true;
            return false;
        }
    }

    // driver code
    public static void main(String[] args)
    {
        Stack s = new Stack();
        s.push(1);
        s.push(2);
        s.push(3);

        System.out.println("current size: " + s.size());
        System.out.println(s.top());
        s.pop();
        System.out.println(s.top());
        s.pop();
        System.out.println(s.top());

        System.out.println("current size: " + s.size());
    }
}

Here is a Code to implement queue using two stack in java:

// Java program to implement Queue using 
// two stacks with costly enQueue() 
import java.util.*; 

class QueueSolution
{ 
static class Queue 
{ 
        static Stack<Integer> s1 = new Stack<Integer>(); 
        static Stack<Integer> s2 = new Stack<Integer>(); 

        static void enQueue(int x) 
        { 
                // Move all elements from s1 to s2 
                while (!s1.isEmpty()) 
                { 
                        s2.push(s1.pop()); 
                        //s1.pop(); 
                } 

                // Push item into s1 
                s1.push(x); 

                // Push everything back to s1 
                while (!s2.isEmpty()) 
                { 
                        s1.push(s2.pop()); 
                        //s2.pop(); 
                } 
        } 

        // Dequeue an item from the queue 
        static int deQueue() 
        { 
                // if first stack is empty 
                if (s1.isEmpty()) 
                { 
                        System.out.println("Q is Empty"); 
                        System.exit(0); 
                } 

                // Return top of s1 
                int x = s1.peek(); 
                s1.pop(); 
                return x; 
        } 
}; 

// Driver code 
public static void main(String[] args) 
{ 
        Queue q = new Queue(); 
        q.enQueue(1); 
        q.enQueue(2); 
        q.enQueue(3); 

        System.out.println(q.deQueue()); 
        System.out.println(q.deQueue()); 
        System.out.println(q.deQueue()); 
} 
}