Implement a Queue using two stacks.

Write and algorithm to implement a Queue using 2 Stacks.

Answer:

class Queue
{
    private:
        Stack s[2];
    public:
        Enqueue(T item)
        {
            if ( last operation was enqueue )
            {
                S[1].push(s[0].pop());
                s[0].push(item);
            }
            else
            {
                while( !s[0].isempty() )
                {
                    s[1].push( s[0].pop() );
                }
                s[0].push(item);
            }
        }

        Dequeue()
        {
            if( last operation was dequeue)
            {
                return s[0].pop();
            }
            else
            {
                while(!s[1].isempty())
                {
                    s[0].push( s[1].pop() );
                }
                return s[0].pop();
            }
        }

};