CareerCup

Take 2 stack lets say S1 and S2, 
Enqueue operation : Push in S1,
Dequeue Operation: 
if S2 is empty:
     pop every element from S1 and push into S2 one by one. 
pop from S2;

There is a detailed solution in the entry "Queue from two stacks" at code.google.com/p/elements-of-programming-interviews/wiki/Programs.

I got this from the book titled "Elements of Programming Interviews: 300 Questions and Solutions".

stackoverflow.com/questions/69192/how-to-implement-a-queue-using-two-stacks

Algorithm:

Suppose we have two stacks (stackOne & stackTwo).

Insert new item in queue (Enqueue):
if stackOne is empty
Push this item on stackOne.
else
if stackTwo is empty
then pop possible items from stackOne and push on stackTwo
then push new item on stackOne.
else
print mesaage queue is full

Remove item from queue (Dequeue):
if stackTwo is not empty
then Pop item from stackTwo
else
if stackOne in not empty
Pop all Items from stackOne any place them on stackTwo in poped order.
Pop top item from stackTwo.
else
print message queue is empty.

i am coding only push and pop part

template<typename T>
void push(T x) {
   stck.push(x);
}
T pop() {
       if (s.empty()) throw error; 
       T ret = pop_bottom(s); 
}
T pop_bottom(stack<T> s)
{
       T top = s.top(); s.pop();
       if (s.empty()) return top;
       else {
                T ret = pop_bottom(s);
                 s.push(top);
                 return ret;  
       }
}

suppose the functions in stack include:
void empty();
element pop();
void push(element);

then

class queue{

stack stack1;
stack stack2;

void push_back(element)
{stack2.push(element);
}

void push_front(element)
{stack1.push(element);
}

element pop_front()
{ if (stack1.empty())
restack(stack1, stack2);
if (stack1.empty()) return null; else return stack1.pop();
}

element pop_back()
{ if (stack2.empty())
restack(stack2, tack1);
if (stack2.empty()) return null; else return stack2.pop();
}

void restack(stack stack1, stack stack2)
{while (!stack2.empty())
{element = stack2.pop();
stack1.push(element);
}


}

class queue_using_stack
{
	stack<int> st1, st2;
public:
	queue_using_stack()
	{

	}
	~queue_using_stack()
	{

	}
	void enqueue(int d)
	{
		st1.push(d);
	}	
	int dequeue()
	{
		int val = -1;

		if(st1.empty() && st2.empty())
			return val;

		else if(!st2.empty())
		{
			val = st2.top();
			st2.pop();
			return val;
		}
		else
		{
			while(!st1.empty())
			{
				st2.push(st1.top());
				st1.pop();
			}
			val = st2.top();
			st2.pop();
			return val;
		}
	}
};

class queue_using_stack
{
	stack<int> st1, st2;
public:
	queue_using_stack()
	{

	}
	~queue_using_stack()
	{

	}
	void enqueue(int d)
	{
		st1.push(d);
	}	
	int dequeue()
	{
		int val = -1;

		if(st1.empty() && st2.empty())
			return val;

		else if(!st2.empty())
		{
			val = st2.top();
			st2.pop();
			return val;
		}
		else
		{
			while(!st1.empty())
			{
				st2.push(st1.top());
				st1.pop();
			}
			val = st2.top();
			st2.pop();
			return val;
		}
	}
};