Question

using java write a program

As the title described, you should only use two stacks to implement a queue's actions. DO NOT use any other data structure and push, pop and top should be O(1) by AVERAGE.
The queue should support push(element), pop() and top() where pop is pop the first(a.k.a front) element in the queue.
Both pop and top methods should return the value of first element

example

push(1)
pop() // return 1 push(2)
push(3)
top() // return 2 pop() // return 2

Answer 1

Here the concept behind using the queue using two stacks is that this method makes sure that oldest entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, another stack tmp is used.

q_push is the push method of the queue. q_pop is the pop method of the queue. q_top is the top method of the queue. Here more time is used while doing the push operation while compared to the pop and top method. Both of the latter operation use O(1) time fo computing .

class queueUsingStack
{
Stack<Integer> s ;
Stack<Integer> tmp ;
public queueUsingStack()
{
s = new Stack<Integer>();
tmp = new Stack<Integer>();
}
public void q_push(int data)
{   
if (s.size() == 0)
s.push(data);
else
{   
int l = s.size();
for (int i = 0; i < l; i++)
tmp.push(s.pop());   
s.push(data);
for (int i = 0; i < l; i++)
s.push(tmp.pop());   
}
}
public int q_pop()
{
if (s.size() == 0)
throw new NoSuchElementException("Underflow Exception");
return s.pop();
}
public int q_top()
{
if (s.size() == 0)
throw new NoSuchElementException("Underflow Exception");
return s.peek();
}
public boolean isEmpty()
{
return s.size() == 0 ;
}
public int getSize()
{
return s.size();
}
}