CareerCup

I think we will need two stacks to implement queue :-
stack has operations top(),empty(),pop(),add()

lets take two stacks s1 and s2
keep a variable FRONT
nOw :-

1) Create queue :- create s1 and s2 and FRONT = NULL and REAR = NULL;
2) Enqueue (e) :- -----------O(1) 
                  if( s1.empty() ) then FRONT = e
                      REAR = e;
                      s1.add(e)
3) Dequeue() :-         ---------------------------------O (Num. elements)
                        if ( s1.empty() then UNDERFLOW 
                        else {
                             while( !s1.empty() )
                                     s2.add( s1.pop());
                             s2.pop();
                             if( !s2.empty() ) FRONT = s2.top(); Else REAR = NULL;
                             while( !s2.empty() ) s1.add( s2.pop() );
                        }

4) Front() :- return FRONT  ---- O(1)
5) Rear() :- return REAR --------O(1)

Using two stacks. One for adding, second for removing items.
Befor add/remove check where are items and pop them if needed.

O(n) for enqueue, O(n) for dequeue in worst case. Sequential adding - O(1).
Sequential dequeue - O(1).

Worst case for switching from/to enqueue/dequeue

Stack<int> stackAdd = new Stack<int>();
Stack<int> stackRemove = new Stack<int>();

public void Enqueue(int item)
{
	if (stackAdd.Count == 0) RevertStacks();	
	stackAdd.Push(item);
}

public int Dequeue()
{
	if (stackRemove.Count == 0) RevertStacks();	
	return stackRemove.Pop();
}

private void RevertStacks()
{
	if (stackAdd.Count > 0)
		while(stackAdd.Count > 0) stackRemove.Push(stackAdd.Pop());
	else if (stackRemove.Count > 0)
		while(stackRemove.Count > 0) stackAdd.Push(stackRemove.Pop());
}

we can do it using a single stack.
supported operations - top(), empty(), pop(), add()

for top() and pop() -
we recursively top or pop the elements until we get the last element. we will still be using two stacks.. one- the given stack and the other recursion stack.. but explicitly its just one stack!

wat say??

just one stack is fine.
insert - O(1)
dequeue - O(n)

All the above solutions are for implementing FIFO queues. In the question, its not mentioned which queue has to be implemented.

The solution needs to take this into account.
In case of a LIFO queue, we just need push() and pop() {can be named add() and remove() }. Both will have time complexity of O(1). We also do not need two queues.

In case of FIFO queue, we need to make a design decision. This can be done either using an extra internal queue, or by using recursion. Adding an element to this stack based queue can be O(1).

void add(operation op)
{
	push(op);
}

For removing, we can use a recursive method

Operation remove()
{
	Operation op = pop();
	if(stack.count == 0)
	{
		return op;
	}
	else
	{
		Operation ret = remove();
		push(op);
		rerturn ret;
	}	
}

The above solution assumes that the Stack implementation supports both push() and pop() methods.